Counting equations in algebraic attacks on block ciphers

Lars Ramkilde Knudsen, Charlotte Vikkelsø Miolane

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper is about counting linearly independent equations for so-called algebraic attacks on block ciphers. The basic idea behind many of these approaches, e.g., XL, is to generate a large set of equations from an initial set of equations by multiplication of existing equations by the variables in the system. One of the most difficult tasks is to determine the exact number of linearly independent equations one obtain in the attacks. In this paper, it is shown that by splitting the equations defined over a block cipher (an SP-network) into two sets, one can determine the exact number of linearly independent equations which can be generated in algebraic attacks within each of these sets of a certain degree. While this does not give us a direct formula for the success of algebraic attacks on block ciphers, it gives some interesting bounds on the number of equations one can obtain from a given block cipher. Our results are applied to the AES and to a variant of the AES, and the exact numbers of linearly independent equations in the two sets that one can generate by multiplication of an initial set of equations are given. Our results also indicate, in a novel way, that the AES is not vulnerable to the algebraic attacks as defined here.
    Original languageEnglish
    JournalInternational Journal of Information Security
    Volume9
    Issue number2
    Pages (from-to)127-135
    ISSN1615-5262
    DOIs
    Publication statusPublished - 2010

    Keywords

    • AES
    • Block ciphers
    • XL
    • Cryptology
    • Algebraic attacks

    Cite this

    @article{bb6f813665b04e40ae13a25c555e46e5,
    title = "Counting equations in algebraic attacks on block ciphers",
    abstract = "This paper is about counting linearly independent equations for so-called algebraic attacks on block ciphers. The basic idea behind many of these approaches, e.g., XL, is to generate a large set of equations from an initial set of equations by multiplication of existing equations by the variables in the system. One of the most difficult tasks is to determine the exact number of linearly independent equations one obtain in the attacks. In this paper, it is shown that by splitting the equations defined over a block cipher (an SP-network) into two sets, one can determine the exact number of linearly independent equations which can be generated in algebraic attacks within each of these sets of a certain degree. While this does not give us a direct formula for the success of algebraic attacks on block ciphers, it gives some interesting bounds on the number of equations one can obtain from a given block cipher. Our results are applied to the AES and to a variant of the AES, and the exact numbers of linearly independent equations in the two sets that one can generate by multiplication of an initial set of equations are given. Our results also indicate, in a novel way, that the AES is not vulnerable to the algebraic attacks as defined here.",
    keywords = "AES, Block ciphers, XL, Cryptology, Algebraic attacks",
    author = "Knudsen, {Lars Ramkilde} and Miolane, {Charlotte Vikkels{\o}}",
    year = "2010",
    doi = "10.1007/s10207-009-0099-9",
    language = "English",
    volume = "9",
    pages = "127--135",
    journal = "International Journal of Information Security",
    issn = "1615-5262",
    publisher = "Springer",
    number = "2",

    }

    Counting equations in algebraic attacks on block ciphers. / Knudsen, Lars Ramkilde; Miolane, Charlotte Vikkelsø.

    In: International Journal of Information Security, Vol. 9, No. 2, 2010, p. 127-135.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Counting equations in algebraic attacks on block ciphers

    AU - Knudsen, Lars Ramkilde

    AU - Miolane, Charlotte Vikkelsø

    PY - 2010

    Y1 - 2010

    N2 - This paper is about counting linearly independent equations for so-called algebraic attacks on block ciphers. The basic idea behind many of these approaches, e.g., XL, is to generate a large set of equations from an initial set of equations by multiplication of existing equations by the variables in the system. One of the most difficult tasks is to determine the exact number of linearly independent equations one obtain in the attacks. In this paper, it is shown that by splitting the equations defined over a block cipher (an SP-network) into two sets, one can determine the exact number of linearly independent equations which can be generated in algebraic attacks within each of these sets of a certain degree. While this does not give us a direct formula for the success of algebraic attacks on block ciphers, it gives some interesting bounds on the number of equations one can obtain from a given block cipher. Our results are applied to the AES and to a variant of the AES, and the exact numbers of linearly independent equations in the two sets that one can generate by multiplication of an initial set of equations are given. Our results also indicate, in a novel way, that the AES is not vulnerable to the algebraic attacks as defined here.

    AB - This paper is about counting linearly independent equations for so-called algebraic attacks on block ciphers. The basic idea behind many of these approaches, e.g., XL, is to generate a large set of equations from an initial set of equations by multiplication of existing equations by the variables in the system. One of the most difficult tasks is to determine the exact number of linearly independent equations one obtain in the attacks. In this paper, it is shown that by splitting the equations defined over a block cipher (an SP-network) into two sets, one can determine the exact number of linearly independent equations which can be generated in algebraic attacks within each of these sets of a certain degree. While this does not give us a direct formula for the success of algebraic attacks on block ciphers, it gives some interesting bounds on the number of equations one can obtain from a given block cipher. Our results are applied to the AES and to a variant of the AES, and the exact numbers of linearly independent equations in the two sets that one can generate by multiplication of an initial set of equations are given. Our results also indicate, in a novel way, that the AES is not vulnerable to the algebraic attacks as defined here.

    KW - AES

    KW - Block ciphers

    KW - XL

    KW - Cryptology

    KW - Algebraic attacks

    U2 - 10.1007/s10207-009-0099-9

    DO - 10.1007/s10207-009-0099-9

    M3 - Journal article

    VL - 9

    SP - 127

    EP - 135

    JO - International Journal of Information Security

    JF - International Journal of Information Security

    SN - 1615-5262

    IS - 2

    ER -