dilithium_bug.py

"""
This gist is a minimal example showing that the KAT data for Dilithiuim
does not seem to match the specification.

KAT data was downloaded from:
https://pq-crystals.org/dilithium/data/dilithium-submission-nist-round3.zip

On Friday the 16th of September, 2022

We consider here the first set of data for Dilithium2

count = 0
seed = 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1
mlen = 33
msg = D81C4D8D734FCBFBEADE3D3F8A039FAA2A2C9957E835AD55B22E75BF57BB556AC8
pk = # SNIP
sk = 1C0EE1111B08003F28E65E8B3BDEB037CF8F221DFCDAF5950EDB38D506D85BEFB60E7FB7708849FEDB54F41A68314805A5C0766ACC9F338A46B29EAAC00087AD561C09A9B820B9EB1984C894463A7DFB5D21C0BA7CAA9DEF40A1E60A535026334A459818E6C1334884F90FC2B455747463C650C41842C3A80104324520152D08346448284944C68401322252B63191166640A82C51A020CA322AC8A88C40964C9404480A125018B42181308DCAB41063180C91464AD9868C443860DA226AD1360201440A0AA52C13294C03150E04313191A61020A16D11094C22043001168153B60CA414900345886096710C1571E40448CBA680A4B460024312E0A625C13871142680A4942522A94C20982101C2280994201C474258A8515B48624B088004B18123498221258E11128223498DA3184A5C86215C344560844C08824C50465123251114952009170A5816410909714A182CA4360208B2251BC18918362D5298708A02109A96681C897102A149D09250522805E0C26CD110711116004916700AC121C2282DC0428024096908C70194A631114631E002410041659C8851E0C26D842822E0C4041987308042914C420A21803191028D18248A90380C08A58552888001380AA4300959241208B74008C18C22924C01212008B7001A89840AB66190002A1A12490241441313489AA44C8440895C4680D9902C01194D6442251B32801B01510BC12024214493222A19A565D2A4505B146AA03862E32652019510C4122D190891199271C84402C43804A1A41010B448C2C40480286563A8445CC6500A17311BA76CA1006142206E82482C18922918258A22167211425048026CC1B03024498404440603336CC20228032128E2280003262281082C5C364A1C47051A106903B64DD89265533208D2129109C590E0348A24C0909CC01091A04903C64123B14CE1404009A97053A44584A22D59105202370610C208910872C31208049251184082A01811DA1041889404C92066E2A45000A080019989CC0226D8A24184088D000022D33020DB148C22C42C23C7918BC809CA066091A465DB36654B1871139308149125519829620805D1408D220208C9B249D3244814030519A0201110249948809186691CC7048B8010E0C825132909E01224582449604046E31685E0A4211A8764091381189669994648480672E4326DD0806504C42509B181DB92285112464186098318289298410824259B906D9252A9A8A8684A3437AF7948FD8C0A02145FE29752E4B81661CEE502EA3AEC573642E361FCE0D0AC02E3264D77B0234D508B35AEDBF0C8834F11FFA293E816563ADA2A7CD4FCC08EBE074F6BC095BE4EF2EEF7D96E9A404855177E7D26C0967694BD289D4F993E8B992AF4278D1D429EDC0B4055305A5A96C65B7361A848AC6843E91E4B1D404404D3708F8E8F867638BCF6F2B6D0E09971C454F53B15C1D889C85991D300BE3FC635240394B5A8A2C34594C0264D014F70137B996AD9336F4AFBB07E0B7FA68B241863AADFB7B22F125EB990B340B9F6A273CFFCFA012AAE2A9E8B95FF0932A3E46723852CB35B02F1A95533C54A40C3C6322B83C33F3C4E198A74CA7D98D546B84791CB5C1CCCA5ED8A06E1D57890033F72A57C66D02FC6A855C4C717D100765511E2549544A21CB19D436632D461BD0C9592D7D7C802809438ED99F93B3E8D0D3893D6A735664F74F2F4327F11BB66861EAE447505E71676AE07A8489267F27D7188F00CC7F98ECEDBF79AD0EDA7F9C4595D06A10A25E7E832171C21465EED64C8A989E0EF61F033321E3160B6CBC25A74E04FD950CB0DF381B342BC3C648F808387284D2BE4B8A61C3DF74A13664D9AEBDAEDD428F883D03BD5DAB39CD84B63437E9D70AE41636661DBB7B9C74EF8AB88B67E456AFAAC54628E43CC98774FD91586C1F0384584211D983EE31D40753CADCA797F40E918D61EE58B78E344A70FB756A4791D4A89F0C3F405186DF5260BEFE6A5ACB77B5A8F85EA0EA1FC5E15AEB434E6DC9ACC8E4160CB7ED527C1D64A5B2831728B022510D24C8EA1783D841D433C75B217DDC3A5336D337425ABEE6B3C4B98DBE139B9DA2B73C8280287C672AC3BEA9EE9FCA1C0EA891F59CD05A3D52234A651F021D9A63E53B1DA3B0B74775769F6A3AC02175957D7BAD9CD05B79C037FDC6CF47AF2A30E95AAE0C460C7C81A999CFD8C8271800A4D58C034EEECC58FBBB82F356C7B5C5A718229C718CEED5DBF2361FA6984EC5615A497AE40196511E192F433144835FD12CB9303D822DC79E2CE583F9897D6BCD2BFC7CBED00D3452FDA67FD67946AA188F4BFD71A66183FEC548FF9BFF74F18BEA5D5530C8746C57CD3B2C2796C23E4F1B591695AF443C99ACEE2F731FF0AE16E9624B7314C38608EB76F951A89BFEC9A71AF9D9E9822030ACD0D665AAE837A8076527D08CAFAB757C95F4923A3FBE04189971116CFD9ECFB543E35BAB4C757CE376DCEFEE4CC47F3F8AA5248D8A959122242183AF5819D377B882E1D823F219BA35DD4419377E60F0AF61169C2A5D27AE882B326679272B9A374416A32F7221A430499830293B601573B2C4EE561FDE5ABEB97B4E11D704A09D538BC07BC1016B993A097EAF6BCFD11E8EDC481E3548DB94C3C5F07D74B3E0B3D643E7D3D655B8E9F920DB47D9347441A91B8208FF051BA1C896588ABD8AEEDBE4C20D989DE08659000E77573118567AB9BF4CDC54607233F5380A62F12F2CE2485A9A790F058ECC34F4CC35B05A1C266C48763AC29DBCC9FE14B5AACFDE788EE8E9A0AD7C695C808A54559C7AB2EE6FAF5A9C5A52661FDD81866189EBE1CB95F6D12704BE9091092075E3414995978ADFA72AA5182BAA17CA2D6A8635BA481FC3E6AE2074D8403D0B28E042EA353F35EC755F143E204C893AAEFFE722B433113263C4BDFED4399D737C8237556DA6FE08CCF6A124CF9185BF6F87A854474FABB862510A176FCE5F5493810E7549163DC9E4BDFFADC1FB375E678D4F965AC02A3AFCB540B2E5AC452390D7E584A980CCEB0789563353805370FE1694AE25A575330628628E599A293CF507132BFE41FF5909F17C12055D08FDD87818145B60F96C916F109F1D88DE81A65FD475E3EFD151FB4406C59F7DC9F94497241EF00E78EC22C8C78796475C50452EF85B2EAC4E9477428AFD087D85887A18438A5E454EE939C90F742FE791FBCC78E8092830F684ADC52C145FBBACA694A57871BD82405E992D016648EC1C0117577146BDC9E4078A3F64A33712E9C80FCA6C6D98DFBA052C93BDEE454D2E1FA09532A822277113DD26F3999597D012735929CE794633D28760615945FF58EDF8BDE61CCE9DDE251C61F3AA508E5BEFBE66DFA9923C8373621C5FAA7FF5817B3C656C8DD00FD4AF5E9735254300E52FE149721056FD428EA84600FD2B390699F540B95F2035639B966BDC5C3143C412A08056DB040E0333EDED06289ED381FFC051FF85C3937C8DB39722BA60429D98C7B3E25C6E99B107063F093996A2D9634BF6DF35C2D2DE86E475E7E2843797712BA6384438BE44B182EF49489A61309F09A6E02FC44FF6234DBAE54
smlen = 2453
sm = # SNIP

To do this check we need a AES-256 CTR DRGB.

I used a custom DRGB which doesn't lend itself to being used "minimally"
but that's ok as enough of this works to know the DRGB is not the issue.

from aes256_crt_drgb import AES256_CRT_DRGB

kat_seed = "061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1"
kat_seed = bytes.fromhex(kat_seed)
drgb = AES256_CRT_DRGB(kat_seed)
zeta = drgb.random_bytes(32)
print(zeta.hex())
7c9935a0b07694aa0c6d10e4db6b1add2fd81a25ccb148032dcd739936737f2d
"""

# Let's derive out key material
zeta = bytes.fromhex("7c9935a0b07694aa0c6d10e4db6b1add2fd81a25ccb148032dcd739936737f2d")
seed_material = shake_256(zeta).digest(128)

# According to the specification
# rho has 256 bits, rho_prime has 512 bits and key has 256 bits
rho = seed_material[:32]
rho_prime = seed_material[32:96]
key = seed_material[96:]

# The sk is packed (rho, key, tr, ...)
# Lets just snip out the first 64 bytes
kat_sk_first_64_bytes = "1C0EE1111B08003F28E65E8B3BDEB037CF8F221DFCDAF5950EDB38D506D85BEFB60E7FB7708849FEDB54F41A68314805A5C0766ACC9F338A46B29EAAC00087AD"
kat_sk_first_64_bytes = bytes.fromhex(kat_sk_first_64_bytes)
rho_kat = kat_sk_first_64_bytes[:32]
key_kat = kat_sk_first_64_bytes[32:]

# However, the collected key from the KAT is wrong!
assert rho == rho_kat
assert key != key_kat

# Some bug searching later, I found the key,
# but it's in the wrong place
broken_key = seed_material[64:96]
# This shouldn't be our key, but it is...
assert broken_key == key_kat