Problem
Solution
After launching our challenge instance, we’re given the following source code:
import secrets
import hashlib
from Crypto.Cipher import ChaCha20_Poly1305
flag = open("flag.txt").read().strip()
def shasum(x):
return hashlib.sha256(x).digest()
key = shasum(shasum(secrets.token_bytes(32) + flag.encode()))
# Generate a random nonce to be extra safe
nonce = secrets.token_bytes(12)
messages = [
"Did you know that ChaCha20-Poly1305 is an authenticated encryption algorithm
?",
"That means it protects both the confidentiality and integrity of data!"
]
goal = "But it's only secure if used correctly!"
def encrypt(message):
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ciphertext, tag = cipher.encrypt_and_digest(message)
return ciphertext + tag + nonce
def decrypt(message_enc):
ciphertext = message_enc[:-28]
tag = message_enc[-28:-12]
nonce = message_enc[-12:]
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
plaintext = cipher.decrypt_and_verify(ciphertext, tag)
return plaintext
for message in messages:
print("Plaintext: " + repr(message))
message = message.encode()
print("Plaintext (hex): " + message.hex())
ciphertext = encrypt(message)
print("Ciphertext (hex): " + ciphertext.hex())
print()
print()
user = bytes.fromhex(input("What is your message? "))
user_message = decrypt(user)
print("User message (decrypted): " + repr(user_message))
if goal in repr(user_message):
print(flag)Background
ChaCha20-Poly1305 is an authenticated encryption algorithm which combines the ChaCha20 stream cipher with the Poly1305 MAC. The security for ChaCha20-Poly1305 relies on choosing a unique nonce for every message encrypted1, but note that in the above code, both messages are encrypted using the same key and nonce. And according to the RFC2:
Quote
If a nonce is repeated, then both the one-time Poly1305 key and the keystream are identical between the messages. This reveals the XOR of the plaintexts, because the XOR of the plaintexts is equal to the XOR of the ciphertexts.
Not only can the XOR of the plaintexts be revealed, but an attacker can also forge new messages using the same nonce3. This is what we want to achieve.
But in order to do so, we’ll have to first take a look at the algorithm itself4:
Since the key and nonce are reused, the one-time key produced by Poly1305_Key_Gen and the keystream produced by ChaCha20 will be identical between ciphertexts.
, so if we have both encrypted by the same , then . But since, in this case, we know both and , we can recover (e.g. by computing ) and subsequently encrypt a new message as .
As for the authentication tag , there is no associated data (AD) here, so the input to Poly1305 is simply:
| C | pad(C) | len(C) |
From the pairs the one-time key can be recovered by finding the roots of the polynomial5.
Thus, nonce and key reuse may allow an attacker to discover both and . From which, the attacker can encrypt a new message as and forge a tag by running Poly1305 on C3 | pad(C3) | len(C3) with .
Script
In researching this problem, I came across the repository AEAD-Nonce-Reuse-Attacks by tl2cents which implements this kind of message forgery already. I used chacha_poly1305_forgery.py in my solution, so full credit goes to the original author!
Now all that was left was to plug in the values that we observed in running the original source code.
m1 = b"Did you know that ChaCha20-Poly1305 is an authenticated encryption algorithm?"
e1 = bytes.fromhex("028dae4777beee769d7e37cf5bf8081fcaecaa21ec9a4daedc59d5e7410dd985f1f9ca1a5caa6d611f5a493d3af057d59ef73c9888325f915aa8bc786f2d00a54b850382c694638aef524f1c328a79eef0b7497d71eb810949906e94f5511ba9de0a2aa48358a266ed")
c1 = e1[:-28]
t1 = e1[-28:-12]
n1 = e1[-12:]
ad1 = b""
m2 = b"That means it protects both the confidentiality and integrity of data!"
e2 = bytes.fromhex("128cab132ebcfe37986378d10fac100cd1b88c2af9aa05ad811d90975a09c594a1a6915c5cbd286e0513492427ec4b9b8bf03bd995394fd458b4b67e6f7d1baa048f4297cbd220f8985b1461025143e6800a2c0ee8db511ba9de0a2aa48358a266ed")
c2 = e2[:-28]
t2 = e2[-28:-12]
n2 = e2[-12:]
ad2 = b""
assert n1 == n2
m3 = b"But it's only secure if used correctly!"
ad3 = b""
# CREDIT: https://github.com/tl2cents/AEAD-Nonce-Reuse-Attacks/blob/main/chacha-poly1305/chacha_poly1305_forgery.py
from chacha_poly1305_forgery import chachapoly1305_forgery_attack
res = chachapoly1305_forgery_attack(
ad1,
c1,
t1,
ad2,
c2,
t2,
m1,
m3,
ad3
)
for i in res:
c3, t3 = i
print(c3.hex() + t3.hex() + n1.hex())