“Oops, i did it again” – Security of one-time signatures under two-message attacks

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Uittreksel

One-time signatures (OTS) are called one-time, because the accompanying security reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport’s scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport’s scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.

TaalEngels
TitelSelected Areas in Cryptography – SAC 2017
Subtitel24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers
RedacteurenCarlisle Adams , Jan Camenisch
Plaats van productieCham
UitgeverijSpringer
Hoofdstuk15
Pagina's299-322
Aantal pagina's24
ISBN van elektronische versie978-3-319-72565-9
ISBN van geprinte versie978-3-319-72564-2
DOI's
StatusGepubliceerd - 2018
Evenement24th International Conference on Selected Areas in Cryptography (SAC 2017) - Ottawa, Canada
Duur: 16 aug 201718 aug 2017
Congresnummer: 24

Publicatie series

NaamLecture Notes in Computer Science
UitgeverijSpringer
Volume10719
ISSN van geprinte versie0302-9743
NaamSecurity and Cryptology
UitgeverijSpringer

Congres

Congres24th International Conference on Selected Areas in Cryptography (SAC 2017)
Verkorte titelSAC 2017
LandCanada
StadOttawa
Periode16/08/1718/08/17

Vingerafdruk

Standardization
Signature
Attack
Degradation
Imply
Building Blocks
Reuse
Scenarios

Trefwoorden

    Citeer dit

    Groot Bruinderink, L., & Hülsing, A. T. (2018). “Oops, i did it again” – Security of one-time signatures under two-message attacks. In C. Adams , & J. Camenisch (editors), Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers (blz. 299-322). (Lecture Notes in Computer Science; Vol. 10719), (Security and Cryptology). Cham: Springer. DOI: 10.1007/978-3-319-72565-9_15
    Groot Bruinderink, L. ; Hülsing, A.T./ “Oops, i did it again” – Security of one-time signatures under two-message attacks. Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers. redacteur / Carlisle Adams ; Jan Camenisch. Cham : Springer, 2018. blz. 299-322 (Lecture Notes in Computer Science). (Security and Cryptology).
    @inproceedings{37619df38e9f48b0a8220e2afbd300be,
    title = "“Oops, i did it again” – Security of one-time signatures under two-message attacks",
    abstract = "One-time signatures (OTS) are called one-time, because the accompanying security reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport’s scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport’s scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.",
    keywords = "Few-time signatures, Hash-based signatures, One-time signatures, Post-quantum cryptography, Two-message attacks",
    author = "{Groot Bruinderink}, L. and A.T. H{\"u}lsing",
    year = "2018",
    doi = "10.1007/978-3-319-72565-9_15",
    language = "English",
    isbn = "978-3-319-72564-2",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "299--322",
    editor = "{Adams }, {Carlisle } and Jan Camenisch",
    booktitle = "Selected Areas in Cryptography – SAC 2017",
    address = "Germany",

    }

    Groot Bruinderink, L & Hülsing, AT 2018, “Oops, i did it again” – Security of one-time signatures under two-message attacks. in C Adams & J Camenisch (redactie), Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10719, Security and Cryptology, Springer, Cham, blz. 299-322, Ottawa, Canada, 16/08/17. DOI: 10.1007/978-3-319-72565-9_15

    “Oops, i did it again” – Security of one-time signatures under two-message attacks. / Groot Bruinderink, L.; Hülsing, A.T.

    Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers. redactie / Carlisle Adams ; Jan Camenisch. Cham : Springer, 2018. blz. 299-322 (Lecture Notes in Computer Science; Vol. 10719), (Security and Cryptology).

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    TY - GEN

    T1 - “Oops, i did it again” – Security of one-time signatures under two-message attacks

    AU - Groot Bruinderink,L.

    AU - Hülsing,A.T.

    PY - 2018

    Y1 - 2018

    N2 - One-time signatures (OTS) are called one-time, because the accompanying security reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport’s scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport’s scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.

    AB - One-time signatures (OTS) are called one-time, because the accompanying security reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport’s scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport’s scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.

    KW - Few-time signatures

    KW - Hash-based signatures

    KW - One-time signatures

    KW - Post-quantum cryptography

    KW - Two-message attacks

    UR - http://www.scopus.com/inward/record.url?scp=85041804020&partnerID=8YFLogxK

    U2 - 10.1007/978-3-319-72565-9_15

    DO - 10.1007/978-3-319-72565-9_15

    M3 - Conference contribution

    SN - 978-3-319-72564-2

    T3 - Lecture Notes in Computer Science

    SP - 299

    EP - 322

    BT - Selected Areas in Cryptography – SAC 2017

    PB - Springer

    CY - Cham

    ER -

    Groot Bruinderink L, Hülsing AT. “Oops, i did it again” – Security of one-time signatures under two-message attacks. In Adams C, Camenisch J, redacteurs, Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers. Cham: Springer. 2018. blz. 299-322. (Lecture Notes in Computer Science). (Security and Cryptology). Beschikbaar vanaf, DOI: 10.1007/978-3-319-72565-9_15