Known-plaintext attack | EPFL Graph Search

The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib) and its encrypted version (ciphertext). These can be used to reveal further secret information such as secret keys and code books. The term "crib" originated at Bletchley Park, the British World War II decryption operation, where it was defined as:A plain language (or code) passage of any length, usually obtained by solving one or more cipher or code messages, and occurring or believed likely to occur in a different cipher or code message, which it may provide a means of solving. History The usage "crib" was adapted from a slang term referring to cheating (e.g., "I cribbed my answer from your test paper"). A "crib" originally was a literal or interlinear translation of a foreign-language text—usually a Latin or Greek text—that students might be assigned to translate from the original language. The idea behind a crib is that cryptologists

Misuse Attacks on Post-quantum Cryptosystems

Ciprian Baetu, Fatma Betül Durak, Loïs Evan Huguenin-Dumittan, Abdullah Talayhan, Serge Vaudenay

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NISI) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NISI. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.

SPRINGER INTERNATIONAL PUBLISHING AG2019

Cryptanalysis of LowMC instances using single plaintext/ciphertext pair

Subhadeep Banik, Khashayar Barooti, Fatma Betül Durak, Serge Vaudenay

Arguably one of the main applications of the LowMC family ciphers is in the post-quantum signature scheme PICNIC. Although LowMC family ciphers have been studied from a cryptanalytic point of view before, none of these studies were directly concerned with the actual use case of this cipher in PICNIC signature scheme. Due to the design paradigm of PICNIC, an adversary trying to perform a forgery attack on the signature scheme instantiated with LowMC would have access to only a single given plaintext/ciphertext pair, i.e. an adversary would only be able to perform attacks with data complexity 1 in a known-plaintext attack scenario. This restriction makes it impossible to employ classical cryptanalysis methodologies such as differential and linear cryptanalysis. In this paper we introduce two key-recovery attacks, both in known-plaintext model and of data complexity 1 for two variants of LowMC, both instances of the LowMC cryptanalysis challenge.

RUHR-UNIV BOCHUM, HORST GORTZ INST IT-SICHERHEIT2020

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Fatma Betül Durak, Serge Vaudenay

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS~2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity

O(N^5\log(N))

, which is much larger than the code book (but using many tweaks), where

N^2

is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

O(N^{5})

. Our attack was successfully tested with

N\leq2^9

. It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4-round Feistel network. Biryukov et. al. already gave a 4-round Feistel structure attack in SAC~2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

O(N^{3})

. Our 4-round attack is simple to extend to five and more rounds with complexity

N^{(r-5)N+o(N)}

. It shows that FF1 with

N=7

and FF3 with

7\leq N\leq10

do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our

O(N^{5})

attack.

2017