Algebraic attacks on block ciphers using quantum annealing
Elżbieta Burek, Michał Wroński, Krzysztof Mańk, Michał Misztal
Abstract
This paper presents the transformation method of the system of algebraic equations describing the symmetric cipher into the QUBO problem. After transformation of given equations <inline-formula><tex-math notation="LaTeX">$f_0, f_1, \ldots, f_{n-1}$</tex-math><alternatives><mml:math><mml:mrow><mml:msub><mml:mi>f</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>f</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:mo>...</mml:mo><mml:mo>,</mml:mo><mml:msub><mml:mi>f</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq1-3143152.gif"/></alternatives></inline-formula> to equations over integers <inline-formula><tex-math notation="LaTeX">$f^{\prime }_0, f^{\prime }_1, \ldots, f^{\prime }_{n-1}$</tex-math><alternatives><mml:math><mml:mrow><mml:msubsup><mml:mi>f</mml:mi><mml:mn>0</mml:mn><mml:mo>'</mml:mo></mml:msubsup><mml:mo>,</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mn>1</mml:mn><mml:mo>'</mml:mo></mml:msubsup><mml:mo>,</mml:mo><mml:mo>...</mml:mo><mml:mo>,</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mo>'</mml:mo></mml:msubsup></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq2-3143152.gif"/></alternatives></inline-formula>, one can linearize each, obtaining <inline-formula><tex-math notation="LaTeX">$f^{\prime }_{lin_i}=lin(f^{\prime }_i)$</tex-math><alternatives><mml:math><mml:mrow><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:msub><mml:mi>n</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow><mml:mo>'</mml:mo></mml:msubsup><mml:mo>=</mml:mo><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:mi>n</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mi>i</mml:mi><mml:mo>'</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq3-3143152.gif"/></alternatives></inline-formula>, for <inline-formula><tex-math notation="LaTeX">$i=\overline{0, n-1}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mover><mml:mrow><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:mo>¯</mml:mo></mml:mover></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq4-3143152.gif"/></alternatives></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$lin$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:mi>n</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq5-3143152.gif"/></alternatives></inline-formula> denotes linearization operation. Finally, one can obtain problem in the QUBO form as <inline-formula><tex-math notation="LaTeX">$(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen-C$</tex-math><alternatives><mml:math><mml:mrow><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:msub><mml:mi>n</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo>'</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mo>⋯</mml:mo><mml:mo>+</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:msub><mml:mi>n</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow><mml:mo>'</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>P</mml:mi><mml:mi>e</mml:mi><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mi>C</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq6-3143152.gif"/></alternatives></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$Pen$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>P</mml:mi><mml:mi>e</mml:mi><mml:mi>n</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq7-3143152.gif"/></alternatives></inline-formula> denotes penalties obtained during linearization of equations, <inline-formula><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="wronski-ieq8-3143152.gif"/></alternatives></inline-formula> is the number of equations and <inline-formula><tex-math notation="LaTeX">$C$</tex-math><alternatives><mml:math><mml:mi>C</mml:mi></mml:math><inline-graphic xlink:href="wronski-ieq9-3143152.gif"/></alternatives></inline-formula> is constant appearing in the polynomial <inline-formula><tex-math notation="LaTeX">$(f^{\prime }_{lin_0} )^2+\cdots +(f^{\prime }_{lin_{n-1}} )^2+Pen$</tex-math><alternatives><mml:math><mml:mrow><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:msub><mml:mi>n</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow><mml:mo>'</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mo>⋯</mml:mo><mml:mo>+</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msubsup><mml:mi>f</mml:mi><mml:mrow><mml:mi>l</mml:mi><mml:mi>i</mml:mi><mml:msub><mml:mi>n</mml:mi><mml:mrow><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:mrow><mml:mo>'</mml:mo></mml:msubsup><mml:mo>)</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>+</mml:mo><mml:mi>P</mml:mi><mml:mi>e</mml:mi><mml:mi>n</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="wronski-ieq10-3143152.gif"/></alternatives></inline-formula>. This paper presents the transformation method of SPN block ciphers to the QUBO problem. What is more, we present the results of the transformation of the complete AES-128 cipher to the QUBO problem, where the number of variables of the equivalent QUBO problem equals approximately 30,026. It is worth noting that AES-128 is much easier to solve using quantum annealing than the factorization problem and the discrete logarithm problem of a similar level of security. For example, factorizing a 3072 bit long RSA integer using quantum annealing requires a QUBO problem of about 2,360,000 variables.