Informations pratiques

Description de la ressource

Résumé

In this session, we will have a look at the attacks against the CFS signature scheme. As for public-key encryption, there are two kinds of attacks against signature schemes. First kind of attack is key recovery attacks where an attacker tries to recover the secret key from the knowledge of the public key. These attacks are exactly the same as against the McEliece cryptosystem that you have seen last week. The only difference is the parameters. Here in the signature, we have a small t and a large n but the algorithm remains the same. So, we won't go into details in this session. The second kind of attacks are forgery attacks. These attacks try to create a valid document-signature pair that is a pair of documented signature that a verifier will be able to verify successfully. They are similar to message attacks against McEliece but with one very simple difference, that is, the attacker has a complete control on the documents he wants to sign. Whereas in the McEliece scheme, the attacker is given some ciphertexts and tries to decrypt them. Depending on the version of the CFS signature scheme, the forgery attack will be slightly different. In the counter version of CFS, the attacker will choose a document, pick a counter i, compute the hash of the document and the counter and try to decode this hash as an error of weight t. But, be careful, hash is probably not decodable, only one out of t! is decodable. In the complete decoding version, the attacker will choose a document, compute this hash and try to decode it as an error of weight t + ?. In both cases the attacker has to solve an instance of syndrome decoding. And there are two main algorithms to do this: Information Set Decoding or Generalized Birthday Attack. The only difference is, as we said, the attacker has a complete control on the document. So, instead of focusing on a single document, the attacker can focus on many documents at a time. Instead of choosing the document and picking one counter, he can pick many counters to obtain many different hash values, and among these hash values, some will be decodable. In the complete decoding version, the same thing, the attacker can choose many documents and try to forge a signature for any of these documents.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Domaine(s)

• Cette ressource fait partie de
  • 5: Other cryptographic constructions relying on coding theory