TP4 Oracle de parité pour RSA

L’objectif de ce TP est de montrer les conséquences des fuites de d’information sur le cas artificiel de l’oracle de parité du texte en clair dans le cas de RSA naïf (textbook RSA), c’est-à-dire RSA sans hardening/padding. Ce type d’attaque existe et a été exploitée sur les premières versions de SSL/TLS en 1998 puis remise au goût du jour en 2017.

On va considérer la situation artificielle d’un service appelé oracle qui à chaque chiffré retourne la parité du texte clair. L’attaquant ne dispose initialement que d’un chiffré $c$ dont il veut retrouver le clair et de l’accès à l’oracle.

Consult The Oracle

Il est clair qu’il y a une fuite d’information avec cet oracle : si on détient un secret, il ne faut rien révéler à son sujet, et certainement pas le dernier bit du message clair correspondant. Ce qui est moins clair en revanche, c’est qu’on peut retrouver l’intégralité du texte clair bit à bit à partir de l’oracle de parité. En revanche, on ne peut pas pour autant retrouver la clef privée : juste le message.

Il faudra donner dans Tomuss le message secret de votre serveur pour un bonus de +0.25 sur la note de CC.

Changelog

2024-06-04 : ajout référence machine challenge-64
2024-05-16 : correction de get_parity dans le fichier de départ.

Principe de l’attaque

L’attaque repose sur la malléabilité de RSA naïf. Extrait de L’article Malleability de Wikipedia :

In the RSA cryptosystem, a plaintext $m$ is encrypted as $E(m) = m^{e} \pmod{n}$, where $(e, n)$ is the public key. Given such a ciphertext, an adversary can construct an encryption of $m \cdot t$ for any $t$, as $E(m) \cdot t^e \pmod{n} = ( m \cdot t ) ^ e \mod{n}$. For this reason, RSA is commonly used together with padding methods such as OAEP or PKCS1.

La malléabilité et l’oracle de parité permettent de diviser par deux l’espace de recherche du message clair. En effet, comme on peut produire un nouveau chiffré $c'$ à partir du chiffré $c$, on va calculer le chiffré du double du message clair avec $c' = E(2 \cdot m) = (2 \cdot m)^e = 2^e \cdot m^e = 2^e \cdot c$. Ainsi, en analysant la parité de $2 \cdot m$ deux cas sont possibles, selon que l’on dépasse le module $n$ ou pas :

Soit l’oracle répond impair ({answer = "Odd"} dans l’implémentation), quand $2 \cdot m \pmod{n}$ est impair,
- c’est le cas quand $2 \cdot m \gt n$, comme $n$ est impair par définition, $2 \cdot m \pmod{n} = 2 \cdot m - n$ est nécessairement impair également ;
Soit l’oracle répond 0 ({answer = "Even"} dans l’implémentation), quand $2 \cdot m \pmod{n}$ est pair,
- c’est le cas quand $2 \cdot m \lt n$, $2 \cdot m \pmod{n} = 2 \cdot m$ est pair, car on a pas dépassé le module $n$ après avoir multiplié par $2$.

Ainsi, initialement on sait seulement que $m \in [ 0\ldots n [$, mais avec la réponse de l’oracle on peut réduire cet intervalle à :

$m \in [n/2\ldots n[$ si $2 \cdot m \pmod{n}$ est impair ($2 \cdot m \gt n$),
$m \in [0\ldots n/2[$ si $2 \cdot m \pmod{n}$ est pair ($2 \cdot m \lt n$).

En répétant cette opération autant de fois que la longueur en bits de $n$, on réduit progressivement l’intervalle de la recherche à un singleton : l’entier qui correspond au message d’origine. Au fur et à mesure que l’espace de recherche se réduit, on va graduellement voir le message cherché apparaître, voir la trace d’exécution en annexe.

Le schéma suivant illustre cette attaque.

sequenceDiagram
    participant A as Attaquant
    participant O as Oracle
    O-->>O: choose (n=p*q, e, d)
    O-->>O: choose (m) (message secret)
    O-->>A: ciphertext c=E(m)
    Note over A,O: phase préparatoire terminée
    loop Tant que m n'est pas trouvé
        A->>O: ciphertext c' (calculé depuis c)
        O->>A: parity(m') = m' % 2 avec m'=D(c')
    end

Questions préparatoires

Question 1.1 expliquer pourquoi si on sait que le message $m$ à retrouver est de taille au plus $k$ bits, alors, on peut commencer l’attaquant en multipliant par $m$ par $2^{\lambda - k}$ où $\lambda$ est la longueur de la clef RSA en bits. 💡 Le faire dans la suite, cela rendra les tests plus rapides si vous savez que le message recherché est court.

Question 1.2 si votre message $m=b_1 \dots b_k$ est une séquence de $k$ bits, alors après combien de tours d’attaques, le message envoyé à l’oracle aura pour clair $m'=b_1 \dots b_k, \mathtt{0x00}$ (le message d’origine suivi de 8 zéros) ?

Question 1.3 Pourquoi l’attaque de ce TP ne fonctionnera pas en l’état avec le padding RSAES-PKCS1-v1.5 (obsolète) ni avec RSAES-OAEP (recommandé).

Préparation de l’attaque

Pour ce TP, on fournit l’oracle sous la forme d’un service web dont le nom DNS est donné dans Tomuss. L’API web est la suivante :

http://${SERVER}:8080 : la page HTML racine du serveur.
http://${SERVER}:8080/parity/ciphered : le message secret à décoder.
http://${SERVER}:8080/parity/pubkey : la clef publique RSA 1024 bits utilisée pour chiffrer le message précédent avec textbook RSA (sans padding).
http://${SERVER}:8080/parity/ : l’oracle de parité du clair. Vous devez envoyer à ce service une requête POST ayant comme contenu le codage base64 du tableau de bytes du chiffré.

On donne comme exemple le message attack at dawn! encodé en utf-8 dans le fichier example.b64. Avec https://httpie.io/, on peut demander à l’oracle la parité du chiffré de départ en lui donnant un message encodé dans un corps JSON comprenant un unique champ base64, ici l’exemple avec https://httpie.io/ :

SERVER="challenge-xx.mif29.os.univ-lyon1.fr"
http POST http://${SERVER}:8080/parity/ base64=@example.b64

⚠️ Remplacer challenge-xx par le numéro de votre machine. ⚠️

Si tout est OK, on doit recevoir une réponse HTTP semblable à la suivante, où on voit que le message d’origine est impair, en effet le dernier caractère du message clair est !, qui en utf-8 ou ASCII vaut 33 et qui est impair.

http -vv POST http://${SERVER}:8080/parity/ base64=@example.b64
POST /parity/ HTTP/1.1
Accept: application/json, */*;q=0.5
Accept-Encoding: gzip, deflate, br
Connection: keep-alive
Content-Length: 188
Content-Type: application/json
Host: challenge-64.mif29.os.univ-lyon1.fr:8080
User-Agent: HTTPie/3.2.1

{
    "base64": "Xzcu66Jq7gbbczelEucj7c4Fiv9MAlkTGZCnW3fe/uqSNwGSWdpFmlD9PCyhTlROlJBr6GuC+oNEUT6ejcvCppfDj3WE9z6wBTdF8S6KvVD2n6PEdnc82Ji0SBFEMyo1spCLA5gTSV16BI5//9IPE34jHWhIuXwtOg/B0Rf1DJ8="
}


HTTP/1.1 200 OK
content-length: 202
content-type: application/json
date: Tue, 07 May 2024 11:20:31 GMT
server: uvicorn

{
    "answer": "Odd",
    "base64": "Xzcu66Jq7gbbczelEucj7c4Fiv9MAlkTGZCnW3fe/uqSNwGSWdpFmlD9PCyhTlROlJBr6GuC+oNEUT6ejcvCppfDj3WE9z6wBTdF8S6KvVD2n6PEdnc82Ji0SBFEMyo1spCLA5gTSV16BI5//9IPE34jHWhIuXwtOg/B0Rf1DJ8="
}

Encodage

⚠️ Attention à l’encodage, car on va devoir jongler entre les types

str pour les données à transmettre, encodé en utf-8,
bytes pour représenter les entiers longs,
- soit sous forme de tableaux d’octets,
- soit sous forme de texte encodé au format Base64,
int pour l’implémentation de RSA naïf,

On passe ainsi, lors du chiffrement :

de str à bytes avec str.encode
de bytes à bytes en encodant en Bas64 avec binascii.b2a_base64
de bytes à int avec int.to_bytes()
là, on travaille sur les entiers pour le chiffrement RSA avec pow(m, e, n)
de int à bytes avec int.from_bytes()
de bytes à bytes en encodant en Base64 avec binascii.b2a_base64

Réalisation de l’attaque

On donne un fichier de départ start.py, le but est de retrouver le secret http://${SERVER}:8080/parity/ciphered de votre VM.

Vous disposez des fonctions suivantes déjà implémentées :

download_content() : télécharge un contenu et l’enregistre dans un fichier
get_parity() : détermine la parité du clair avec l’Oracle
encrypt() : chiffre naïvement avec RSA

Question 2.1 à quoi le message YXR0YWNrIGF0IGRhd24h en Base64 correspond-il ?

Question 2.2 donner l’entier correspondant à ce message en big endian.

Question 3.3 vérifier que le chiffré avec la clef publique est bien celui de example.b64.

Question 2.4 vérifier que le clair de ce message est bien impair, get_parity() doit renvoyer True.

Question 2.5 reprendre encrypt() pour implémenter multiply_cleartext_by_2() qui multiplie le clair par 2 sans le connaître en utilisant le chiffré comme indiqué précédemment.

Question 2.6 implémenter find_message() qui va progressivement réduire l’intervalle [low, high[ en utilisant multiply_cleartext_by_2.

⚠️ Quand vous arrivez au moment où l’espace de recherche est réduit à quelques bits, passez en recherche exhaustive, cela ne prendra pas de temps et évitera de devoir gérer les cas limites des arrondis supérieurs ou inférieurs.

⚠️ Vous pouvez tester votre code sur la machine challenge-64.mif29.os.univ-lyon1.fr. Le message est 0x47676f31717345414a677363747a6e4e en hexadécimal qui correspond à la chaîne tirée aléatoirement Ggo1qsEAJgsctznN.

Saisissez le secret décrypté dans la colonne Parity-Oracle-Reponse de Tomuss.

L’attaque de Bleichenbacher et ROBOT

Dans la section 12.8.3 de A Graduate Course in Applied Cryptography, Boneh & Shoup 2023 on peut lire :

Bleichenbacher’s attack on the RSA-PKCS1 encryption scheme: RSA-PKCS1 encryption is not secure against chosen ciphertext attacks. We describe an attack, due to Bleichenbacher, as it applies to the SSL 3.0 protocol used to establish a secure session between a client and a server. The SSL 3.0 protocol was later replaced by an improved protocol called TLS 1.0 that defends against this attack, as discussed below. The latest version of TLS, called TLS 1.3, has moved away from RSA encryption altogether (see Section 21.10).

Le principe du padding PKCS1 est illustré ci-dessous. Le problème se situe dans les 16 premiers bits d’en-tête du message chiffré qui doivent être égaux à 0x0002 : si ce n’est pas le cas, les versions vulnérables de SSL renvoient une erreur ce qui conduit à une fuite d’information, non pas sur le bit de poids faible comme avec l’oracle de parité, mais sur les 16 bits de poids forts, car on sait qu’on a réussi à obtenir un chiffré plausible. On remarque qu’avec RSA-PKCS1, on ne peut pas chiffrer des messages aussi longs qu’avec textbook RSA, car il faut environ 11 octets (2 d’en-tête + 8 du nombre aléatoire + 1 séparateur) pour le padding.

Padding PKCS1, Boneh & Shoup 2023

L’attaque est un peu plus compliquée à mettre en œuvre, parce qu’il faut chercher des messages et l’information obtenue est moins simple que diviser l’espace de recherche en deux, mais elle est réalisable.

Plus récemment, cette attaque de 1998 a eu un retour sur la scène avec Return Of Bleichenbacher’s Oracle Threat, voir le site https://robotattack.org/, voir les références suivantes pour aller plus loin, voire implémenter cette attaque :

Annexe trace d’exécution

Le déroulé de l’attaque pas à pas sur le chiffré du message attack at dawn!. On voit que progressivement le message apparait au fur et à mesure que

File ../example.b64 read
File rsa_parity_public.pem read (e=65537)
#step=01/120 parity=False (1110064352038451634140911624050605831=2**119.740 bits <->)
  0x0 < 0x6ae532f4f2391c5ae298ea63e53f83
  b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' < b'j\xe52\xf4\xf29\x1cZ\xe2\x98\xeac\xe5?\x83'
#step=02/120 parity=True (555032176019225817070455812025302915=2**118.740 bits <->)
  0x3572997a791c8e2d714c7531f29fc2 < 0x6ae532f4f2391c5ae298ea63e53f83
  b'5r\x99zy\x1c\x8e-qLu1\xf2\x9f\xc2' < b'j\xe52\xf4\xf29\x1cZ\xe2\x98\xeac\xe5?\x83'
#step=03/120 parity=True (277516088009612908535227906012651457=2**117.740 bits <->)
  0x502be637b5aad54429f2afcaebefa3 < 0x6ae532f4f2391c5ae298ea63e53f83
  b'P+\xe67\xb5\xaa\xd5D)\xf2\xaf\xca\xeb\xef\xa3' < b'j\xe52\xf4\xf29\x1cZ\xe2\x98\xeac\xe5?\x83'
#step=04/120 parity=True (138758044004806454267613953006325728=2**116.740 bits <->)
  0x5d888c9653f1f8cf8645cd17689793 < 0x6ae532f4f2391c5ae298ea63e53f83
  b']\x88\x8c\x96S\xf1\xf8\xcf\x86E\xcd\x17h\x97\x93' < b'j\xe52\xf4\xf29\x1cZ\xe2\x98\xeac\xe5?\x83'
#step=05/120 parity=False (69379022002403227133806976503162864=2**115.740 bits <->)
  0x5d888c9653f1f8cf8645cd17689793 < 0x6436dfc5a3158a95346f5bbda6eb8b
  b']\x88\x8c\x96S\xf1\xf8\xcf\x86E\xcd\x17h\x97\x93' < b'd6\xdf\xc5\xa3\x15\x8a\x954o[\xbd\xa6\xeb\x8b'
#step=06/120 parity=True (34689511001201613566903488251581432=2**114.740 bits <->)
  0x60dfb62dfb83c1b25d5a946a87c18f < 0x6436dfc5a3158a95346f5bbda6eb8b
  b'`\xdf\xb6-\xfb\x83\xc1\xb2]Z\x94j\x87\xc1\x8f' < b'd6\xdf\xc5\xa3\x15\x8a\x954o[\xbd\xa6\xeb\x8b'
#step=07/120 parity=False (17344755500600806783451744125790716=2**113.740 bits <->)
  0x60dfb62dfb83c1b25d5a946a87c18f < 0x628b4af9cf4ca623c8e4f81417568d
  b'`\xdf\xb6-\xfb\x83\xc1\xb2]Z\x94j\x87\xc1\x8f' < b'b\x8bJ\xf9\xcfL\xa6#\xc8\xe4\xf8\x14\x17V\x8d'
#step=08/120 parity=False (8672377750300403391725872062895358=2**112.740 bits <->)
  0x60dfb62dfb83c1b25d5a946a87c18f < 0x61b58093e56833eb131fc63f4f8c0e
  b'`\xdf\xb6-\xfb\x83\xc1\xb2]Z\x94j\x87\xc1\x8f' < b'a\xb5\x80\x93\xe5h3\xeb\x13\x1f\xc6?O\x8c\x0e'
#step=09/120 parity=True (4336188875150201695862936031447679=2**111.740 bits <->)
  0x614a9b60f075faceb83d2d54eba6cf < 0x61b58093e56833eb131fc63f4f8c0e
  b'aJ\x9b`\xf0u\xfa\xce\xb8=-T\xeb\xa6\xcf' < b'a\xb5\x80\x93\xe5h3\xeb\x13\x1f\xc6?O\x8c\x0e'
#step=10/120 parity=False (2168094437575100847931468015723839=2**110.740 bits <->)
  0x614a9b60f075faceb83d2d54eba6cf < 0x61800dfa6aef175ce5ae79ca1d996e
  b'aJ\x9b`\xf0u\xfa\xce\xb8=-T\xeb\xa6\xcf' < b'a\x80\r\xfaj\xef\x17\\\xe5\xaey\xca\x1d\x99n'
#step=11/120 parity=True (1084047218787550423965734007861919=2**109.740 bits <->)
  0x616554adadb28915cef5d38f84a01f < 0x61800dfa6aef175ce5ae79ca1d996e
  b'aeT\xad\xad\xb2\x89\x15\xce\xf5\xd3\x8f\x84\xa0\x1f' < b'a\x80\r\xfaj\xef\x17\\\xe5\xaey\xca\x1d\x99n'
#step=12/120 parity=True (542023609393775211982867003930959=2**108.740 bits <->)
  0x6172b1540c50d0395a5226acd11cc7 < 0x61800dfa6aef175ce5ae79ca1d996e
  b'ar\xb1T\x0cP\xd09ZR&\xac\xd1\x1c\xc7' < b'a\x80\r\xfaj\xef\x17\\\xe5\xaey\xca\x1d\x99n'
#step=13/120 parity=False (271011804696887605991433501965479=2**107.740 bits <->)
  0x6172b1540c50d0395a5226acd11cc7 < 0x61795fa73b9ff3cb2000503b775b1a
  b'ar\xb1T\x0cP\xd09ZR&\xac\xd1\x1c\xc7' < b'ay_\xa7;\x9f\xf3\xcb \x00P;w[\x1a'
#step=14/120 parity=False (135505902348443802995716750982739=2**106.740 bits <->)
  0x6172b1540c50d0395a5226acd11cc7 < 0x6176087da3f862023d293b74243bf0
  b'ar\xb1T\x0cP\xd09ZR&\xac\xd1\x1c\xc7' < b'av\x08}\xa3\xf8b\x02=);t$;\xf0'
#step=15/120 parity=True (67752951174221901497858375491369=2**105.740 bits <->)
  0x61745ce8d824991dcbbdb1107aac5c < 0x6176087da3f862023d293b74243bf0
  b'at\\\xe8\xd8$\x99\x1d\xcb\xbd\xb1\x10z\xac\\' < b'av\x08}\xa3\xf8b\x02=);t$;\xf0'
#step=16/120 parity=False (33876475587110950748929187745684=2**104.740 bits <->)
  0x61745ce8d824991dcbbdb1107aac5c < 0x617532b33e0e7d90047376424f7426
  b'at\\\xe8\xd8$\x99\x1d\xcb\xbd\xb1\x10z\xac\\' < b'au2\xb3>\x0e}\x90\x04svBOt&'
#step=17/120 parity=False (16938237793555475374464593872842=2**103.740 bits <->)
  0x61745ce8d824991dcbbdb1107aac5c < 0x6174c7ce0b198b56e81893a9651041
  b'at\\\xe8\xd8$\x99\x1d\xcb\xbd\xb1\x10z\xac\\' < b'at\xc7\xce\x0b\x19\x8bV\xe8\x18\x93\xa9e\x10A'
#step=18/120 parity=False (8469118896777737687232296936421=2**102.740 bits <->)
  0x61745ce8d824991dcbbdb1107aac5c < 0x6174925b719f123a59eb225cefde4e
  b'at\\\xe8\xd8$\x99\x1d\xcb\xbd\xb1\x10z\xac\\' < b'at\x92[q\x9f\x12:Y\xeb"\\\xef\xdeN'
#step=19/120 parity=False (4234559448388868843616148468210=2**101.740 bits <->)
  0x61745ce8d824991dcbbdb1107aac5c < 0x617477a224e1d5ac12d469b6b54555
  b'at\\\xe8\xd8$\x99\x1d\xcb\xbd\xb1\x10z\xac\\' < b'atw\xa2$\xe1\xd5\xac\x12\xd4i\xb6\xb5EU'
#step=20/120 parity=True (2117279724194434421808074234105=2**100.740 bits <->)
  0x61746a457e833764ef490d6397f8d9 < 0x617477a224e1d5ac12d469b6b54555
  b'atjE~\x837d\xefI\rc\x97\xf8\xd9' < b'atw\xa2$\xe1\xd5\xac\x12\xd4i\xb6\xb5EU'
#step=21/120 parity=True (1058639862097217210904037117052=2**99.740 bits <->)
  0x617470f3d1b28688810ebb8d269f17 < 0x617477a224e1d5ac12d469b6b54555
  b'atp\xf3\xd1\xb2\x86\x88\x81\x0e\xbb\x8d&\x9f\x17' < b'atw\xa2$\xe1\xd5\xac\x12\xd4i\xb6\xb5EU'
#step=22/120 parity=True (529319931048608605452018558526=2**98.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x617477a224e1d5ac12d469b6b54555
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'atw\xa2$\xe1\xd5\xac\x12\xd4i\xb6\xb5EU'
#step=23/120 parity=False (264659965524304302726009279263=2**97.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x617475f6901601e32e62fe2c519bc5
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'atu\xf6\x90\x16\x01\xe3.b\xfe,Q\x9b\xc5'
#step=24/120 parity=False (132329982762152151363004639631=2**96.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x61747520c5b017febc2a48671fc6fd
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'atu \xc5\xb0\x17\xfe\xbc*Hg\x1f\xc6\xfd'
#step=25/120 parity=False (66164991381076075681502319815=2**95.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x617474b5e07d230c830ded8486dc99
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'att\xb5\xe0}#\x0c\x83\r\xed\x84\x86\xdc\x99'
#step=26/120 parity=False (33082495690538037840751159907=2**94.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x617474806de3a893667fc0133a6767
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'att\x80m\xe3\xa8\x93f\x7f\xc0\x13:gg'
#step=27/120 parity=False (16541247845269018920375579953=2**93.740 bits <->)
  0x6174744afb4a2e1a49f192a1edf236 < 0x61747465b496eb56d838a95a942cce
  b'attJ\xfbJ.\x1aI\xf1\x92\xa1\xed\xf26' < b'atte\xb4\x96\xebV\xd88\xa9Z\x94,\xce'
#step=28/120 parity=True (8270623922634509460187789976=2**92.740 bits <->)
  0x6174745857f08cb891151dfe410f82 < 0x61747465b496eb56d838a95a942cce
  b'attXW\xf0\x8c\xb8\x91\x15\x1d\xfeA\x0f\x82' < b'atte\xb4\x96\xebV\xd88\xa9Z\x94,\xce'
#step=29/120 parity=True (4135311961317254730093894988=2**91.740 bits <->)
  0x6174745f0643bc07b4a6e3ac6a9e28 < 0x61747465b496eb56d838a95a942cce
  b'att_\x06C\xbc\x07\xb4\xa6\xe3\xacj\x9e(' < b'atte\xb4\x96\xebV\xd88\xa9Z\x94,\xce'
#step=30/120 parity=False (2067655980658627365046947494=2**90.740 bits <->)
  0x6174745f0643bc07b4a6e3ac6a9e28 < 0x617474625d6d53af466fc6837f657b
  b'att_\x06C\xbc\x07\xb4\xa6\xe3\xacj\x9e(' < b'attb]mS\xafFo\xc6\x83\x7fe{'
#step=31/120 parity=True (1033827990329313682523473747=2**89.740 bits <->)
  0x61747460b1d887db7d8b5517f501d2 < 0x617474625d6d53af466fc6837f657b
  b'att`\xb1\xd8\x87\xdb}\x8bU\x17\xf5\x01\xd2' < b'attb]mS\xafFo\xc6\x83\x7fe{'
#step=32/120 parity=False (516913995164656841261736873=2**88.740 bits <->)
  0x61747460b1d887db7d8b5517f501d2 < 0x6174746187a2edc561fd8dcdba33a6
  b'att`\xb1\xd8\x87\xdb}\x8bU\x17\xf5\x01\xd2' < b'atta\x87\xa2\xed\xc5a\xfd\x8d\xcd\xba3\xa6'
#step=33/120 parity=True (258456997582328420630868436=2**87.740 bits <->)
  0x617474611cbdbad06fc47172d79abc < 0x6174746187a2edc561fd8dcdba33a6
  b'atta\x1c\xbd\xba\xd0o\xc4qr\xd7\x9a\xbc' < b'atta\x87\xa2\xed\xc5a\xfd\x8d\xcd\xba3\xa6'
#step=34/120 parity=True (129228498791164210315434218=2**86.740 bits <->)
  0x617474615230544ae8e0ffa048e731 < 0x6174746187a2edc561fd8dcdba33a6
  b'attaR0TJ\xe8\xe0\xff\xa0H\xe71' < b'atta\x87\xa2\xed\xc5a\xfd\x8d\xcd\xba3\xa6'
#step=35/120 parity=False (64614249395582105157717109=2**85.740 bits <->)
  0x617474615230544ae8e0ffa048e731 < 0x617474616ce9a108256f46b7018d6b
  b'attaR0TJ\xe8\xe0\xff\xa0H\xe71' < b'attal\xe9\xa1\x08%oF\xb7\x01\x8dk'
#step=36/120 parity=True (32307124697791052578858554=2**84.740 bits <->)
  0x617474615f8cfaa98728232ba53a4e < 0x617474616ce9a108256f46b7018d6b
  b'atta_\x8c\xfa\xa9\x87(#+\xa5:N' < b'attal\xe9\xa1\x08%oF\xb7\x01\x8dk'
#step=37/120 parity=False (16153562348895526289429277=2**83.740 bits <->)
  0x617474615f8cfaa98728232ba53a4e < 0x61747461663b4dd8d64bb4f15363dc
  b'atta_\x8c\xfa\xa9\x87(#+\xa5:N' < b'attaf;M\xd8\xd6K\xb4\xf1Sc\xdc'
#step=38/120 parity=True (8076781174447763144714638=2**82.740 bits <->)
  0x6174746162e424412eb9ec0e7c4f15 < 0x61747461663b4dd8d64bb4f15363dc
  b'attab\xe4$A.\xb9\xec\x0e|O\x15' < b'attaf;M\xd8\xd6K\xb4\xf1Sc\xdc'
#step=39/120 parity=False (4038390587223881572357319=2**81.740 bits <->)
  0x6174746162e424412eb9ec0e7c4f15 < 0x61747461648fb90d0282d07fe7d978
  b'attab\xe4$A.\xb9\xec\x0e|O\x15' < b'attad\x8f\xb9\r\x02\x82\xd0\x7f\xe7\xd9x'
#step=40/120 parity=False (2019195293611940786178659=2**80.740 bits <->)
  0x6174746162e424412eb9ec0e7c4f15 < 0x6174746163b9eea7189e5e47321446
  b'attab\xe4$A.\xb9\xec\x0e|O\x15' < b'attac\xb9\xee\xa7\x18\x9e^G2\x14F'
#step=41/120 parity=True (1009597646805970393089329=2**79.740 bits <->)
  0x61747461634f097423ac252ad731ae < 0x6174746163b9eea7189e5e47321446
  b'attacO\tt#\xac%*\xd71\xae' < b'attac\xb9\xee\xa7\x18\x9e^G2\x14F'
#step=42/120 parity=False (504798823402985196544664=2**78.740 bits <->)
  0x61747461634f097423ac252ad731ae < 0x6174746163847c0d9e2541b904a2fa
  b'attacO\tt#\xac%*\xd71\xae' < b'attac\x84|\r\x9e%A\xb9\x04\xa2\xfa'
#step=43/120 parity=True (252399411701492598272332=2**77.740 bits <->)
  0x617474616369c2c0e0e8b371edea54 < 0x6174746163847c0d9e2541b904a2fa
  b'attaci\xc2\xc0\xe0\xe8\xb3q\xed\xeaT' < b'attac\x84|\r\x9e%A\xb9\x04\xa2\xfa'
#step=44/120 parity=False (126199705850746299136166=2**76.740 bits <->)
  0x617474616369c2c0e0e8b371edea54 < 0x6174746163771f673f86fa957946a7
  b'attaci\xc2\xc0\xe0\xe8\xb3q\xed\xeaT' < b'attacw\x1fg?\x86\xfa\x95yF\xa7'
#step=45/120 parity=False (63099852925373149568083=2**75.740 bits <->)
  0x617474616369c2c0e0e8b371edea54 < 0x61747461637071141037d703b3987d
  b'attaci\xc2\xc0\xe0\xe8\xb3q\xed\xeaT' < b'attacpq\x14\x107\xd7\x03\xb3\x98}'
#step=46/120 parity=False (31549926462686574784041=2**74.740 bits <->)
  0x617474616369c2c0e0e8b371edea54 < 0x61747461636d19ea7890453ad0c168
  b'attaci\xc2\xc0\xe0\xe8\xb3q\xed\xeaT' < b'attacm\x19\xeax\x90E:\xd0\xc1h'
#step=47/120 parity=False (15774963231343287392020=2**73.740 bits <->)
  0x617474616369c2c0e0e8b371edea54 < 0x61747461636b6e55acbc7c565f55de
  b'attaci\xc2\xc0\xe0\xe8\xb3q\xed\xeaT' < b'attacknU\xac\xbc|V_U\xde'
#step=48/120 parity=True (7887481615671643696010=2**72.740 bits <->)
  0x61747461636a988b46d297e426a019 < 0x61747461636b6e55acbc7c565f55de
  b'attacj\x98\x8bF\xd2\x97\xe4&\xa0\x19' < b'attacknU\xac\xbc|V_U\xde'
#step=49/120 parity=True (3943740807835821848005=2**71.740 bits <->)
  0x61747461636b037079c78a1d42fafc < 0x61747461636b6e55acbc7c565f55de
  b'attack\x03py\xc7\x8a\x1dB\xfa\xfc' < b'attacknU\xac\xbc|V_U\xde'
#step=50/120 parity=False (1971870403917910924002=2**70.740 bits <->)
  0x61747461636b037079c78a1d42fafc < 0x61747461636b38e313420339d1286d
  b'attack\x03py\xc7\x8a\x1dB\xfa\xfc' < b'attack8\xe3\x13B\x039\xd1(m'
#step=51/120 parity=True (985935201958955462001=2**69.740 bits <->)
  0x61747461636b1e29c684c6ab8a11b5 < 0x61747461636b38e313420339d1286d
  b'attack\x1e)\xc6\x84\xc6\xab\x8a\x11\xb5' < b'attack8\xe3\x13B\x039\xd1(m'
#step=52/120 parity=False (492967600979477731000=2**68.740 bits <->)
  0x61747461636b1e29c684c6ab8a11b5 < 0x61747461636b2b866ce364f2ad9d11
  b'attack\x1e)\xc6\x84\xc6\xab\x8a\x11\xb5' < b'attack+\x86l\xe3d\xf2\xad\x9d\x11'
#step=53/120 parity=False (246483800489738865500=2**67.740 bits <->)
  0x61747461636b1e29c684c6ab8a11b5 < 0x61747461636b24d819b415cf1bd763
  b'attack\x1e)\xc6\x84\xc6\xab\x8a\x11\xb5' < b'attack$\xd8\x19\xb4\x15\xcf\x1b\xd7c'
#step=54/120 parity=False (123241900244869432750=2**66.740 bits <->)
  0x61747461636b1e29c684c6ab8a11b5 < 0x61747461636b2180f01c6e3d52f48c
  b'attack\x1e)\xc6\x84\xc6\xab\x8a\x11\xb5' < b'attack!\x80\xf0\x1cn=R\xf4\x8c'
#step=55/120 parity=True (61620950122434716375=2**65.740 bits <->)
  0x61747461636b1fd55b509a746e8321 < 0x61747461636b2180f01c6e3d52f48c
  b'attack\x1f\xd5[P\x9atn\x83!' < b'attack!\x80\xf0\x1cn=R\xf4\x8c'
#step=56/120 parity=False (30810475061217358187=2**64.740 bits <->)
  0x61747461636b1fd55b509a746e8321 < 0x61747461636b20ab25b68458e0bbd6
  b'attack\x1f\xd5[P\x9atn\x83!' < b'attack \xab%\xb6\x84X\xe0\xbb\xd6'
#step=57/120 parity=True (15405237530608679093=2**63.740 bits <->)
  0x61747461636b204040838f66a79f7c < 0x61747461636b20ab25b68458e0bbd6
  b'attack @@\x83\x8ff\xa7\x9f|' < b'attack \xab%\xb6\x84X\xe0\xbb\xd6'
#step=58/120 parity=False (7702618765304339546=2**62.740 bits <->)
  0x61747461636b204040838f66a79f7c < 0x61747461636b2075b31d09dfc42da9
  b'attack @@\x83\x8ff\xa7\x9f|' < b'attack u\xb3\x1d\t\xdf\xc4-\xa9'
#step=59/120 parity=True (3851309382652169773=2**61.740 bits <->)
  0x61747461636b205af9d04ca335e693 < 0x61747461636b2075b31d09dfc42da9
  b'attack Z\xf9\xd0L\xa35\xe6\x93' < b'attack u\xb3\x1d\t\xdf\xc4-\xa9'
#step=60/120 parity=False (1925654691326084886=2**60.740 bits <->)
  0x61747461636b205af9d04ca335e693 < 0x61747461636b20685676ab417d0a1e
  b'attack Z\xf9\xd0L\xa35\xe6\x93' < b'attack hVv\xabA}\n\x1e'
#step=61/120 parity=False (962827345663042443=2**59.740 bits <->)
  0x61747461636b205af9d04ca335e693 < 0x61747461636b2061a8237bf2597858
  b'attack Z\xf9\xd0L\xa35\xe6\x93' < b'attack a\xa8#{\xf2YxX'
#step=62/120 parity=True (481413672831521221=2**58.740 bits <->)
  0x61747461636b205e50f9e44ac7af76 < 0x61747461636b2061a8237bf2597858
  b'attack ^P\xf9\xe4J\xc7\xafv' < b'attack a\xa8#{\xf2YxX'
#step=63/120 parity=True (240706836415760610=2**57.740 bits <->)
  0x61747461636b205ffc8eb01e9093e7 < 0x61747461636b2061a8237bf2597858
  b'attack _\xfc\x8e\xb0\x1e\x90\x93\xe7' < b'attack a\xa8#{\xf2YxX'
#step=64/120 parity=True (120353418207880305=2**56.740 bits <->)
  0x61747461636b2060d2591608750620 < 0x61747461636b2061a8237bf2597858
  b'attack `\xd2Y\x16\x08u\x06 ' < b'attack a\xa8#{\xf2YxX'
#step=65/120 parity=True (60176709103940152=2**55.740 bits <->)
  0x61747461636b20613d3e48fd673f3c < 0x61747461636b2061a8237bf2597858
  b'attack a=>H\xfdg?<' < b'attack a\xa8#{\xf2YxX'
#step=66/120 parity=True (30088354551970076=2**54.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b2061a8237bf2597858
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack a\xa8#{\xf2YxX'
#step=67/120 parity=False (15044177275985038=2**53.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b20618d6a2f351cea11
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack a\x8dj/5\x1c\xea\x11'
#step=68/120 parity=False (7522088637992519=2**52.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b2061800d88d67ea2ed
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack a\x80\r\x88\xd6~\xa2\xed'
#step=69/120 parity=False (3761044318996259=2**51.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b2061795f35a72f7f5b
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack ay_5\xa7/\x7f['
#step=70/120 parity=False (1880522159498129=2**50.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b206176080c0f87ed92
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack av\x08\x0c\x0f\x87\xed\x92'
#step=71/120 parity=False (940261079749064=2**49.740 bits <->)
  0x61747461636b206172b0e277e05bca < 0x61747461636b2061745c7743b424ae
  b'attack ar\xb0\xe2w\xe0[\xca' < b'attack at\\wC\xb4$\xae'
#step=72/120 parity=True (470130539874532=2**48.740 bits <->)
  0x61747461636b20617386acddca403c < 0x61747461636b2061745c7743b424ae
  b'attack as\x86\xac\xdd\xca@<' < b'attack at\\wC\xb4$\xae'
#step=73/120 parity=True (235065269937266=2**47.740 bits <->)
  0x61747461636b206173f19210bf3275 < 0x61747461636b2061745c7743b424ae
  b'attack as\xf1\x92\x10\xbf2u' < b'attack at\\wC\xb4$\xae'
#step=74/120 parity=False (117532634968633=2**46.740 bits <->)
  0x61747461636b206173f19210bf3275 < 0x61747461636b2061742704aa39ab91
  b'attack as\xf1\x92\x10\xbf2u' < b"attack at'\x04\xaa9\xab\x91"
#step=75/120 parity=True (58766317484316=2**45.740 bits <->)
  0x61747461636b2061740c4b5d7c6f03 < 0x61747461636b2061742704aa39ab91
  b'attack at\x0cK]|o\x03' < b"attack at'\x04\xaa9\xab\x91"
#step=76/120 parity=True (29383158742158=2**44.740 bits <->)
  0x61747461636b20617419a803db0d4a < 0x61747461636b2061742704aa39ab91
  b'attack at\x19\xa8\x03\xdb\rJ' < b"attack at'\x04\xaa9\xab\x91"
#step=77/120 parity=True (14691579371079=2**43.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b2061742704aa39ab91
  b'attack at VW\n\\n' < b"attack at'\x04\xaa9\xab\x91"
#step=78/120 parity=False (7345789685539=2**42.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b20617423ad80a203ff
  b'attack at VW\n\\n' < b'attack at#\xad\x80\xa2\x03\xff'
#step=79/120 parity=False (3672894842769=2**41.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b2061742201ebd63036
  b'attack at VW\n\\n' < b'attack at"\x01\xeb\xd606'
#step=80/120 parity=False (1836447421384=2**40.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b206174212c21704652
  b'attack at VW\n\\n' < b'attack at!,!pFR'
#step=81/120 parity=False (918223710692=2**39.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b20617420c13c3d5160
  b'attack at VW\n\\n' < b'attack at \xc1<=Q`'
#step=82/120 parity=False (459111855346=2**38.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b206174208bc9a3d6e7
  b'attack at VW\n\\n' < b'attack at \x8b\xc9\xa3\xd6\xe7'
#step=83/120 parity=False (229555927673=2**37.740 bits <->)
  0x61747461636b2061742056570a5c6e < 0x61747461636b2061742071105719aa
  b'attack at VW\n\\n' < b'attack at q\x10W\x19\xaa'
#step=84/120 parity=True (114777963836=2**36.740 bits <->)
  0x61747461636b2061742063b3b0bb0c < 0x61747461636b2061742071105719aa
  b'attack at c\xb3\xb0\xbb\x0c' < b'attack at q\x10W\x19\xaa'
#step=85/120 parity=False (57388981918=2**35.740 bits <->)
  0x61747461636b2061742063b3b0bb0c < 0x61747461636b206174206a6203ea5b
  b'attack at c\xb3\xb0\xbb\x0c' < b'attack at jb\x03\xea['
#step=86/120 parity=False (28694490959=2**34.740 bits <->)
  0x61747461636b2061742063b3b0bb0c < 0x61747461636b20617420670ada52b3
  b'attack at c\xb3\xb0\xbb\x0c' < b'attack at g\n\xdaR\xb3'
#step=87/120 parity=False (14347245479=2**33.740 bits <->)
  0x61747461636b2061742063b3b0bb0c < 0x61747461636b20617420655f4586df
  b'attack at c\xb3\xb0\xbb\x0c' < b'attack at e_E\x86\xdf'
#step=88/120 parity=False (7173622739=2**32.740 bits <->)
  0x61747461636b2061742063b3b0bb0c < 0x61747461636b2061742064897b20f5
  b'attack at c\xb3\xb0\xbb\x0c' < b'attack at d\x89{ \xf5'
#step=89/120 parity=True (3586811369=2**31.740 bits <->)
  0x61747461636b20617420641e95ee01 < 0x61747461636b2061742064897b20f5
  b'attack at d\x1e\x95\xee\x01' < b'attack at d\x89{ \xf5'
#step=90/120 parity=True (1793405684=2**30.740 bits <->)
  0x61747461636b20617420645408877b < 0x61747461636b2061742064897b20f5
  b'attack at dT\x08\x87{' < b'attack at d\x89{ \xf5'
#step=91/120 parity=False (896702842=2**29.740 bits <->)
  0x61747461636b20617420645408877b < 0x61747461636b20617420646ec1d438
  b'attack at dT\x08\x87{' < b'attack at dn\xc1\xd48'
#step=92/120 parity=True (448351421=2**28.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b20617420646ec1d438
  b'attack at dae-\xda' < b'attack at dn\xc1\xd48'
#step=93/120 parity=False (224175710=2**27.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b206174206468138109
  b'attack at dae-\xda' < b'attack at dh\x13\x81\t'
#step=94/120 parity=False (112087855=2**26.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b206174206464bc5771
  b'attack at dae-\xda' < b'attack at dd\xbcWq'
#step=95/120 parity=False (56043927=2**25.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b20617420646310c2a5
  b'attack at dae-\xda' < b'attack at dc\x10\xc2\xa5'
#step=96/120 parity=False (28021963=2**24.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b2061742064623af83f
  b'attack at dae-\xda' < b'attack at db:\xf8?'
#step=97/120 parity=False (14010981=2**23.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b206174206461d0130c
  b'attack at dae-\xda' < b'attack at da\xd0\x13\x0c'
#step=98/120 parity=False (7005490=2**22.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b2061742064619aa073
  b'attack at dae-\xda' < b'attack at da\x9a\xa0s'
#step=99/120 parity=False (3502745=2**21.740 bits <->)
  0x61747461636b206174206461652dda < 0x61747461636b2061742064617fe726
  b'attack at dae-\xda' < b'attack at da\x7f\xe7&'
#step=100/120 parity=True (1751372=2**20.740 bits <->)
  0x61747461636b206174206461728a80 < 0x61747461636b2061742064617fe726
  b'attack at dar\x8a\x80' < b'attack at da\x7f\xe7&'
#step=101/120 parity=False (875686=2**19.740 bits <->)
  0x61747461636b206174206461728a80 < 0x61747461636b2061742064617938d3
  b'attack at dar\x8a\x80' < b'attack at day8\xd3'
#step=102/120 parity=True (437843=2**18.740 bits <->)
  0x61747461636b20617420646175e1aa < 0x61747461636b2061742064617938d3
  b'attack at dau\xe1\xaa' < b'attack at day8\xd3'
#step=103/120 parity=False (218921=2**17.740 bits <->)
  0x61747461636b20617420646175e1aa < 0x61747461636b206174206461778d3e
  b'attack at dau\xe1\xaa' < b'attack at daw\x8d>'
#step=104/120 parity=True (109460=2**16.740 bits <->)
  0x61747461636b20617420646176b774 < 0x61747461636b206174206461778d3e
  b'attack at dav\xb7t' < b'attack at daw\x8d>'
#step=105/120 parity=True (54730=2**15.740 bits <->)
  0x61747461636b206174206461772259 < 0x61747461636b206174206461778d3e
  b'attack at daw"Y' < b'attack at daw\x8d>'
#step=106/120 parity=True (27365=2**14.740 bits <->)
  0x61747461636b2061742064617757cc < 0x61747461636b206174206461778d3e
  b'attack at dawW\xcc' < b'attack at daw\x8d>'
#step=107/120 parity=False (13682=2**13.740 bits <->)
  0x61747461636b2061742064617757cc < 0x61747461636b206174206461777285
  b'attack at dawW\xcc' < b'attack at dawr\x85'
#step=108/120 parity=True (6841=2**12.740 bits <->)
  0x61747461636b206174206461776529 < 0x61747461636b206174206461777285
  b'attack at dawe)' < b'attack at dawr\x85'
#step=109/120 parity=True (3420=2**11.740 bits <->)
  0x61747461636b206174206461776bd7 < 0x61747461636b206174206461777285
  b'attack at dawk\xd7' < b'attack at dawr\x85'
#step=110/120 parity=False (1710=2**10.740 bits <->)
  0x61747461636b206174206461776bd7 < 0x61747461636b206174206461776f2e
  b'attack at dawk\xd7' < b'attack at dawo.'
#step=111/120 parity=True (855=2**9.740 bits <->)
  0x61747461636b206174206461776d83 < 0x61747461636b206174206461776f2e
  b'attack at dawm\x83' < b'attack at dawo.'
#step=112/120 parity=False (427=2**8.738 bits <->)
  0x61747461636b206174206461776d83 < 0x61747461636b206174206461776e58
  b'attack at dawm\x83' < b'attack at dawnX'
#step=113/120 parity=True (213=2**7.735 bits <->)
  0x61747461636b206174206461776dee < 0x61747461636b206174206461776e58
  b'attack at dawm\xee' < b'attack at dawnX'
#step=114/120 parity=False (106=2**6.728 bits <->)
  0x61747461636b206174206461776dee < 0x61747461636b206174206461776e23
  b'attack at dawm\xee' < b'attack at dawn#'
#step=115/120 parity=True (53=2**5.728 bits <->)
  0x61747461636b206174206461776e09 < 0x61747461636b206174206461776e23
  b'attack at dawn\t' < b'attack at dawn#'
#step=116/120 parity=True (26=2**4.700 bits <->)
  0x61747461636b206174206461776e16 < 0x61747461636b206174206461776e23
  b'attack at dawn\x16' < b'attack at dawn#'
#step=117/120 parity=True (13=2**3.700 bits <->)
  0x61747461636b206174206461776e1d < 0x61747461636b206174206461776e23
  b'attack at dawn\x1d' < b'attack at dawn#'

hex(msg)='0x61747461636b206174206461776e21' decoded = b'attack at dawn!'