Vidéo pédagogique

5.3. Attacks against the CFS Scheme

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

In this session, we willhave a look at the attacks against the CFS signature scheme. As for public-keyencryption, there are two kinds of attacks against signature schemes. First kind of attack iskey recovery attacks where an attacker tries torecover the secret key from the knowledge of the publickey. These attacks are exactly the same as against the McEliececryptosystem that you have seen last week. The only difference isthe parameters. Here in the signature, we have asmall t and a large n but the algorithm remains the same. So, we won't go intodetails in this session. The second kind ofattacks are forgery attacks. These attacks try to createa valid document-signature pair that is a pair ofdocumented signature that a verifier will be ableto verify successfully. They are similar to messageattacks against McEliece but with one very simpledifference, that is, the attacker has a complete control onthe documents he wants to sign. Whereas in the McEliecescheme, the attacker is given some ciphertexts andtries to decrypt them. Depending on the version ofthe CFS signature scheme, the forgery attack willbe slightly different. In the counter version ofCFS, the attacker will choose a document, pick a counteri, compute the hash of the document and the counterand 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 thecomplete decoding version, the attacker will choose adocument, compute this hash and try to decode it as anerror of weight t + δ. In both cases the attacker has tosolve an instance of syndrome decoding. And there are two mainalgorithms to do this: Information Set Decoding orGeneralized Birthday Attack. The only difference is, aswe said, the attacker has a complete control on the document. So, instead of focusingon a single document, the attacker can focus onmany documents at a time. Instead of choosing thedocument and picking one counter, he can pick many countersto obtain many different hash values, and among these hashvalues, some will be decodable. In the complete decodingversion, the same thing, the attacker can choose manydocuments and try to forge a signature for any of these documents.

Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 5.3. Attacks against the CFS Scheme. [Vidéo]. Canal-U. (Consultée le 20 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème