In this challenge, we are given a zip file containing 10 .png images.
By opening the images, we can tell that these are some form of QR-codes.
I began by scanning them with the command-line tool zbarimg
└─$ zbarimg *.png
QR-Code:HC1:NCFOXN*TS0BIO DQP4FWRAN9I6T5XH4PIQJAZGA+1V2:U:PI/E2$4JY/K:*K9OV$/G0NN7Y4HBT*Q0ROFRW0:Q89Y431TSGO/UI2YUJ12ZD5CC9G%85$0CPN-XIN6R%E5IWMAK8S16A65K342/4N7MW84-C6W47E16O47D280DNIZ6$S4L35BD7UJ8+YMHBQ:YM/D7JSPAEQLD4RCH+SGU.SKV9KDC.A5:S9395F48V+H0 28X2+36R/S09T./0LWTKD3323EJ0SU9ZIEQKERQ8IY1I$HH%U8 9PS5TK96L6SR9MU9DV5 R13PI%F1PN1/T1%%HN9GQWU-:0Z0OTNJI+AR$C66P-7P*3G64SQJIQ3LB$FI2DQTQXJ24GB3HVR$9HLLK2NPCKIUSEFO/P3WCW/BJEQO.HQK6D +SM1N.2IK2S9493H0$8M3BF
[...]
QR-Code:HC1:NCFOXN*TS0BIO DQP4$VQAN9I6T5XH4PIQJAZGA+1V2:U:PI/E2$4JY/KT-K-EFEHN7Y4HBT*Q0ROFRW0:Q89Y431TR58/UI2YUF52ZD5CC9G%85$0CPN-XIN6R%E5IWMAK8S16A65K342/4N7MW84-C6W47E16O47D280DNZV2ZH91JAA/CHLFEEA+ZA%DBU2LKHG3ZA5N0:BCYE9.OVMBEIMI4UUIMI$I9XZ2ZA8DS9++9LK9Q$95:UENEUW6646936ORPC-4A+2XEN QT QTHC31M3+E35S4CZKHKB-43.E3KD3OAJ5%IKTCMD3QHBZQJLIF172*VPZAOZGT52J-42ED6++F-8KNOV-OE$-EGUMBDW$B71RCOSPY%N9Z37 93%8V7WGYF*.7.YMGL9SS3Y:NMZPBE9HJ6OMIHGR2RRDF7-201:3I1
scanned 10 barcode symbols from 10 images in 0.41 seconds
This output data seemed rather peculiar. Noticing every line of output started with HC1:NCFOXN..., I googled the prefix and was then led to EU Green Pass QR Codes. This site was particularly helpful: https://gir.st/blog/greenpass.html.
The challenge title is a play on Covid19.
With the help of ChatGPT, I generated a script that performed the Base45 -> Zlib -> CBOR -> COSE -> JSON decoding. I got the following output:
{
"QR_1": {
"-260": {
"1": {
"ver": "1.3.0",
"nam": {
"fn": "BLITZEN",
"gn": "REINSDYR",
"fnt": "BLITZEN",
"gnt": "REINSDYR"
},
"dob": "2001-01-01",
"v": [
{
"is": "Nordpolens Vaksinasjonssenter",
"ci": "urn:uvci:01:XX:XXXXXXXXXXXXXXXXXXXXXXXX",
"co": "Nordpolen",
"dn": 2,
"dt": "2021-01-01",
"sd": 2,
"ma": "ORG-100030215",
"mp": "EU/1/20/1528",
"tg": "840539006",
"vp": "1119349007"
}
]
}
}
},
[...]
"QR_10": {
"-260": {
"1": {
"ver": "1.3.0",
"nam": {
"fn": "VIXEN",
"gn": "REINSDYR",
"fnt": "VIXEN",
"gnt": "REINSDYR"
},
"dob": "2001-01-01",
"v": [
{
"is": "Nordpolens Vaksinasjonssenter",
"ci": "urn:uvci:01:XX:XXXXXXXXXXXXXXXXXXXXXXXX",
"co": "Nordpolen",
"dn": 2,
"dt": "2021-01-01",
"sd": 2,
"ma": "ORG-100030215",
"mp": "EU/1/20/1528",
"tg": "840539006",
"vp": "1119349007"
}
]
}
}
}
}
The data was all-round rather unassuming.
However, in addition to the data from the payload, we had a corresponding signature for each pass.
--- Signatur 1 for QR-kode 1 ---
Heksadesimal: 23bdbe836ca88268155e7f5e63f3c78691093c7f87b3097062ddc8226ad60fb2956c7fb6b710829195519108a5fcd09a3401c1414cbb935a86760883bb27c4df
--- Signatur 1 for QR-kode 2 ---
Heksadesimal: ae05c829232f7f9c4be40bbf9ae92d92cf6e1e483f423747125adbdba6d18430cc9639a59fdb38815c5113fe28085e4b4db08060d5bca30d1c5f515579e5847b
--- Signatur 1 for QR-kode 3 ---
Heksadesimal: 2cf43577802efec717ba36a1ec214391fbc4e5eaf241824e0bfed80273e9f9de220b580ee62ae4df76c7d9a6fbf47011647816c9d4c87fd08fdd7240d3fbdd35
--- Signatur 1 for QR-kode 4 ---
Heksadesimal: a9ab217770dc137843b7fe30de77b5dda4d289add8e2611a610615985423d9afac5f1e7a531afba8f875590b59b8256112e41c021a2b84a0d5a9d5f4640fd15a
--- Signatur 1 for QR-kode 5 ---
Heksadesimal: e92eb0b92f8211dbaaa99de8a446a723dd000b076a9b1705b9274b9e1802be15786fd8a554b0fd6a17fbfafe30ff23df61b0a67918098fd5fcfbab6d0c5be8d3
--- Signatur 1 for QR-kode 6 ---
Heksadesimal: 220145e1b4e58078246fe52f03e3adb0b6faabced8ad20948f4b8a0f24d0118929f5dd561419dd30dd5d32e2f43ae8f3a8f6678b40f4159dd028d6d2b82b6a98
--- Signatur 1 for QR-kode 7 ---
Heksadesimal: 7db8336ca9b5d0421bf4cd890052592608ce0ddf989e836835931166bd01dc5a64a1e5950bd5525105cc206eff545b34820075f6b435c0209f947caed5c3f398
--- Signatur 1 for QR-kode 8 ---
Heksadesimal: 69c971efe85e4f84f80fd116652d04b1279529cd46fa20f80cae55defa31d27ba228071fffa61cd0147710e1240bfcc99376bc56f6e44ed35987275aa3e1efbe
--- Signatur 1 for QR-kode 9 ---
Heksadesimal: 7db8336ca9b5d0421bf4cd890052592608ce0ddf989e836835931166bd01dc5a0275047d4b104e071211fa1f22c32134cc524cdfcd5c13b96f150c4757741a41
--- Signatur 1 for QR-kode 10 ---
Heksadesimal: a785f6e888a665205f289647bafca36f319de1883304d7f2d369b15d24d16efd88af3433150efd48f43bc142aa5a19ce00deb3a6fe190501da18a182cb351b6e
One thing I noticed is that the first half of the signature for QR-code 7 and QR-code 9 are identical:
7db8336ca9b5d0421bf4cd890052592608ce0ddf989e836835931166bd01dc5a64a1e5950bd5525105cc206eff545b34820075f6b435c0209f947caed5c3f398
7db8336ca9b5d0421bf4cd890052592608ce0ddf989e836835931166bd01dc5a0275047d4b104e071211fa1f22c32134cc524cdfcd5c13b96f150c4757741a41
Also, the codes correspond to Santa and Rudolph, the two most important characters of the bunch.
During some earlier research, I found this GitHub issue addressing the private key leak of the Covid19 Green Pass codes: https://github.com/ehn-dcc-development/eu-dcc-hcert-spec/issues/103
This tells me that we are working with the Elliptic Curve Digital Signing Algorithm (ECDSA), and that we are most likely working with the curve secp256r1.
This is very interesting, because the signatures consist of two values, r and s. Since the value r is identical for codes, it means the nonce has been reused. In ECDSA, the private key can be recovered if two different messages are signed with the same nonce!
With the identification of QR-code 7 and QR-code 9 sharing the same r value, we can exploit the nonce reuse vulnerability in ECDSA to recover the private key. In ECDSA, each signature is generated using a unique nonce k. The signature consists of two components, r and s, who are generated in the following fashion:
If two messages $m_1$ and $m_2$ are signed with the same private key and the same nonce, then we can recover the private key with:
\[\large privkey = \frac{s_2 \cdot Sha256(m_1) - s_1 \cdot Sha256(m_2)}{r(s_1-s_2)}\]We already have the values for $r$, $s_1$ and $s_2$, but we need to find the exact values for $m_1$ and $m_2$. We can recover the exact payloads based on the standard for COSE (RFC8152)
Sig_structure = [
context : "Signature" / "Signature1" / "CounterSignature",
body_protected : empty_or_serialized_map,
? sign_protected : empty_or_serialized_map,
external_aad : bstr,
payload : bstr
]
We will use Signature1, the protected header \xa1\x01& (retrieved from CBORTag dump), no external_aad and the main payload
sig_struct7 = cbor2.dumps(["Signature1", b'\xa1\x01&', b'', payload1])
sig_struct9 = cbor2.dumps(["Signature1", b'\xa1\x01&', b'', payload2])
These values can then be hashed to get $h_1$ and $h_2$.
We can then recover the private key $d$ using the equation above, but we have to calculate the modular inverse instead of performing division:
d = (s2*h1 - s1*h2) * pow((r*(s1-s2)), -1, n) % n
import base45, zlib, cbor2, hashlib
# Order of P-256 curve
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
qr_codes = [
"HC1:NCFOXN*TS0BIO DF+O/*G:ZH6I1$4JV7J$%25I3KC3183/9TL4T.B9NVPBLUD1VVY9C9Q $UQN1X1FIN9 UP.509Y4KCTSGO*LAHRIU-HOV1TU1+ZELX9JUPY0B3ZCH4BEWVN:2%S2ZCT-3TPM5YW46/2C4TK$2+2T:T27ALD-I:Z2ZW4:.AN4JX:S:+IZW4PHBO332Y8H00M:EJZIX4K*/6395J4I-B5ET42HPPEP58R8YG-LH/CJ/IE%TE6UG+ZEAT1HQ1:EG:0LPHN6D7LLK*2HG%89UV-0LZ 2UZ4+FJE 4Y3LL/II 0OC9JU0D0HT0HB2PR78DGFJQ8V*1ZZJXNB957Y3GFZRL12$KL0GE FV6YHZ-PS2L6X0Q5V:5S/H9JIVJJ5D0R%88GK61JFYO8L 983309O5A6DBK64GG0Q UL038000*DC .E",
"HC1:NCFOXN*TS0BIO DQP4EVPAN9I6T5XH4PIQJAZGA+1V2:U:PI/E2$4JY/KZ%KY+GJLVQCN /KUYC7KNFRVFUN/Y06AL3*I+*GYZQFG9RQS7NV*CBCY0K1HJ9CHABVCNAC5ADNL3RL7OH*KC:7IZ6G6BIQ53UN8L68IM1L5T9MY47G6MQ+MN95ZTM9:N7755QLQQ5%YQ+GOVE5IE07EM2%KD+V-DN9B92FF9B9-V4WK1WAKT 456LQZ4D-4HRVUMNMD3323R13C C SI5K1*TB3:U-1VVS1UU15%HAMI PQVW5/O16%HAT1Z%PHOP+MMBT16Y5+Z9XV7N31$PRU2PVN5B.BAQIQME0RIH458.HRT3%:V$ZU$L65.4S4LY%CLM2GWAWLA:Z558PEU4YN9JOT3QK5GJ5AK73DQXGO6T UUG6H*59HB0:DCMHE",
]
signatures = {}
for idx, qr in enumerate(qr_codes, 1):
decoded = cbor2.loads(zlib.decompress(base45.b45decode(qr[4:])))
if isinstance(decoded, cbor2.CBORTag) and decoded.tag == 18:
_, _, payload, sig = decoded.value
r = int(sig.hex()[:64], 16)
s = int(sig.hex()[64:], 16)
signatures[idx] = {'r': r, 's': s, 'payload': payload}
qr_items = list(signatures.items())
r1, s1, payload1 = qr_items[0][1]['r'], qr_items[0][1]['s'], qr_items[0][1]['payload']
r2, s2, payload2 = qr_items[1][1]['r'], qr_items[1][1]['s'], qr_items[1][1]['payload']
# Reconstruct Sig_structure based on RFC8152
sig_struct7 = cbor2.dumps(["Signature1", b'\xa1\x01&', b'', payload1])
sig_struct9 = cbor2.dumps(["Signature1", b'\xa1\x01&', b'', payload2])
# hash payloads (m1, m2)
h1 = int.from_bytes(hashlib.sha256(sig_struct7).digest(), 'big')
h2 = int.from_bytes(hashlib.sha256(sig_struct9).digest(), 'big')
# Recover d
d = (s2*h1 - s1*h2) * pow((r*(s1-s2)), -1, n) % n
print(f"Flag: {bytes.fromhex(hex(d)[2:]).decode()}")