Partitioning oracle attacks against variants of AES-GCM and ChaCha20-Poly1305

Abstract: We investigate so-called partitioning oracle attacks against AES-GCM and ChaCha20-Poly1305 along with some improvements. Such attacks against these two cryptosystems are efficient because they can be reduced to solving linear systems of equations over finite fields. We show, with some randomness assumptions, that such linear systems must have at least as many columns as rows. We have also chosen two finite (non-field) rings, as replacement for the respective fields used by AES-GCM and ChaCha20-Poly1305 for message authentication. These rings make the problem of linear system arrangement in a partitioning oracle attack extremely hard for large linear system dimensions.