On the randomness of Rainbow signatures

Abstract

O esforço computacional necessário para enfraquecer algoritmos de criptografia assimétrica atualmente usados é proveniente de problemas da teoria de números e álgebra. Com o advento de computadores quânticos, tais problemas tornam-se passíveis de resolução em tempo polinomial. A área de pesquisa formada por criptossistemas assimétricos independentes de tais problemas é chamada de criptografia pós-quântica. Um exemplo de problema onde é desconhecido se sua resolução é acelerada por computadores quânticos é o problema de resolução de sistemas de equações, alicerce para a criptografia baseada em polinômios multivariados. Chaves públicas e privadas desses algoritmos são representadas por sistemas de equações proibitivamente extensos, mas operações com mensagens são demasiado eficientes. Este comportamento é facilmente identificável no esquema de assinatura digital Rainbow, atualmente finalista no processo de padronização de criptografia pós-quântica liderado pelo Instituto Nacional de Padrões e Tecnologia dos Estados Unidos. O esquema Rainbow é baseado em polinômios de ``óleo e vinagre'', que têm resistido a métodos criptanalíticos até o presente momento. Neste trabalho, um método para reduzir as chaves privadas do esquema Rainbow é proposto, baseado na substituição antecipada de valores em polinômios de chaves privadas, permitindo representações mais compactas. Uma consequência imediata deste fato é que assinaturas são geradas com um nível reduzido de aleatoriedade, mas são apresentados argumentos que mostram a insignificância estatística deste fato em comparações com assinaturas convencionais. O método proposto leva a redução de chaves privadas em até 6.5 vezes, e pode ser combinado com estratégias que reduzem chaves públicas. Entretanto, é exposto que tal método leva a um ataque de recuperação de chaves eficiente, que invalida totalmente a segurança do esquema de assinatura digital derivado. Este trabalho analisa como o ataque é implementado na prática, e demonstra que uma generalização do método proposto é ainda insegura para vários parâmetros do esquema.

Abstract: The computational difficulty of breaking public-key cryptographic algorithms in current use is based on problems from number theory and algebra. With the advent of quantum computers, it becomes feasible to solve such problems in polynomial time. The discipline formed by public-key cryptosystems independent of such problems is called post-quantum cryptography. One example of a problem that is not known to be solved more efficiently by quantum algorithms is the polynomial system solving problem, which is the basis for multivariate cryptography. Prohibitively large polynomial systems represent private and public keys of these algorithms, but operations on messages are very efficient. The Rainbow multivariate signature scheme, currently a finalist of the NIST Post-Quantum Cryptography Standardization Process, is no exception to this norm. Rainbow is based on Oil--Vinegar polynomials, which have resisted known cryptanalysis to this day. We propose a method to reduce Rainbow private keys based on the early substitution of values on the polynomials of private keys, allowing for their compact representation. A direct consequence of this fact is that signatures are generated with a smaller level of randomness, but we argue that this is not statistically discernible from conventional Rainbow signatures. Our method reduces private keys by up to a factor of 6.5 and can be combined with strategies that reduce public keys. However, we find out that our strategy leads to an efficient key recovery attack, which completely undermines the security of the scheme. By analyzing how the attack proceeds in practice, we further argue that a generalization of our previous method is still insecure for several parameter sets.