HPC (šifra)
HPC ( Hasty Pudding Cipher ) je blokově symetrický kryptoalgoritmus vytvořený slavným americkým kryptologem a matematikem Richardem Schreppelem z Arizona State University v roce 1998 . První dvě slova názvu kryptoalgoritmu lze přeložit jako "moučný pudink " . HPC získalo takové zvláštní jméno, zjevně kvůli množství „mazaných“ numerických transformací, což výrazně komplikuje jeho analýzu .
Obecná struktura
HPC je založeno na Feistelově buňce a má zajímavou vlastnost – velikost jak šifrovaného bloku, tak šifrovacího klíče není ničím omezena. Ve skutečnosti se algoritmus HPC skládá z pěti různých (ale souvisejících) dílčích algoritmů, z nichž každý je navržen pro šifrování bloků různých délek:
| název | Velikost bloku v bitech |
|---|---|
| HPC Tiny | 0-35 |
| HPC Short | 36-64 |
| HPC střední | 65-128 |
| HPC Long | 129-512 |
| Rozšířené HPC | 513 a více |
Struktura kola HPC-Medium [1] [2]
Šifrování probíhá v 8 kolech. Zašifrovaný 128bitový blok je zapsán do dvou 64bitových registrů a , načež se na nich provádí velké množství různých matematických operací:
| Označení | Úkon |
|---|---|
| modulo 2 přidání | |
| modulo přidání | |
| modulo odečítání | |
| otočit doleva o n bitů | |
| otočit doprava o n bitů | |
| vynulování dolního bajtu 64bitového bloku | |
| bitově logické "a" |
Kromě toho se kola účastní i některé konstanty :
-
- - velikost šifrovaného bloku v bitech
- - " pseudonáhodná " konstanta
- - hodnoty, které určují počet bitů cyklického posunu :
-
- - aktuální hodnota registru v době provedení
- - číslo aktuálního kola, počínaje nulou
- - rozšířený klíčový fragment :
- [3]
-
- - rozšířený klíč ( pole 256 64bitových slov)
- - fragmenty dalšího klíče:
-
- - další klíč ( pole 8 64bitových slov)
![{\displaystyle k_{1}=K[<S_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04883ba641ce4594f0ef0ade42c09925ff1f7dbd)
![{\displaystyle k_{2}=K[<S_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0d932134433a89a384e5202ae6595eb607a9845)
![{\displaystyle k_{3}=K[(<S_{0}>\A 255)+3*i+1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c19f7d5c8920ed700ddf8e245600b5dd7d73014)
![{\displaystyle k_{4}=K[b+16+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2495cc3185496f7c2bda0a26ec8314f8ab800898)
![{\displaystyle Sp_{1}=Spice[i\oplus 4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28345dbcffb189a101c3515b5b2dfce0e66b5406)
![{\displaystyle Sp_{2}=Spice[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e289a771930295314d8c0e88b8f786aa9846c1ec)
![{\displaystyle Sp_{3}=Spice[i\oplus 7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27329e4949fedeae101f552c59aae2bcded1d20b)
![{\displaystyle Sp_{4}=Spice[i\oplus 2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1abe08fe1ec023a615e9a7230bfbc7482ea81044)
![{\displaystyle Sp_{5}=Spice[i\oplus 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eade896bdc57e24af5c0fe61cf5c3bc48803beda)
Po dokončení 8 kol transformace se provedou další 2 operace:
![{\displaystyle S_{0res}'=S_{0}'+K[b+8]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/293206577b6cc8e1f0d1883757fd5db3ed032bc7)
![{\displaystyle S_{1res}'=S_{1}'+K[b+9]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89249d79acc42f0cfca45fdbb1e408b7d0196449)
Dešifrování se provádí provedením inverzních operací v opačném pořadí.
Postup rozšíření klíče
Úkolem procedury rozšíření klíče je vygenerovat rozšířený klíč , což je pole 256 64bitových slov. Je jasné, že každý z podalgoritmů musí mít svůj vlastní postup. Znalost jednoho z polí rozšířených klíčů neumožňuje vypočítat další pole ani samotný šifrovací klíč . Při pevné velikosti zašifrovaných bloků však stačí pro tento podalgoritmus vygenerovat rozšířený klíč jednou.
Fáze 1: Inicializace
-
- , - podobné " pseudonáhodné " konstanty
- - velikost šifrovacího klíče v bitech
- - číslo podalgoritmu (3 pro HPC-Medium)
![{\displaystyle K[0]=PI19+Nc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffc7d825425a76894f7a39c6d7312f5ed27f00e2)
![{\displaystyle K[1]=E19+L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eaadc7fd8c17f62049ffc613ec60dedea0d05258)
![{\displaystyle K[2]=R220<<Nc}](https://wikimedia.org/api/rest_v1/media/math/render/svg/accd843923192ed2107b865d44ccd133b0b39887)
Zbývajících 253 slov klíče je inicializováno následovně:
![{\displaystyle K[i]=K[i-1]+(K[i-2]\oplus (K[i-3]>>23)\oplus (K[i-3]<<41))mod2 ^{64}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e4808bcebfd07f601e7cd27c0632ec05d538f5)
Fáze 2: Přidání
Provede se bitové modulo 2 přidání šifrovacího klíče a inicializovaného pole rozšířených klíčů , ale ne více než 128 slov.
Fáze 3: Míchání
Provede se funkce promíchání dat rozšířeného klíče , která zajistí, že každý bit klíče ovlivní každý bit rozšířeného klíče :
Krok 1Registry se inicializují :
![{\displaystyle S_{0}=K[255],S_{1}=K[254],...,S_{7}=K[248]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/191eeb1a8ccea22f2b61c7a2e85b79d41721d5b1)
Pro každé slovo rozšířeného klíče se provede operace znázorněná na obrázku. Pro posílení efektu autor algoritmu doporučuje 3 kola míchání.
- - bitové logické "nebo"
- - číslo počítaného slova rozšířeného klíče
- - zamíchat číslo
- - aktuální hodnoty rozšířených klíčových slov :
![{\displaystyle kc_{1}=K[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55f99304739f743c0c20b808535773204e63fd86)
![{\displaystyle kc_{2}=K[(i+83)\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae54acb6d0ec7c7f0e8d94dd16c6bdd74f1fa434)
![{\displaystyle kc_{3}=K[<R_{0}>\And 255]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11aef067e306a8a1760415c56f3806f096cac713)
Fáze 4: Přidání
Pokud velikost klíče přesáhne 128 64bitových slov, pak se pro každý blok 128 slov opakují kroky 2 a 3. Postup pro míchání klíčů v pořadí podle složitosti je tedy přibližně podobný samotnému šifrování .
Další klíč
Jeho účelem je upravit výsledek šifrování se stejnými vstupními bloky a klíči . Dodatečný klíč může být tajný, což zvyšuje skutečné množství klíčových informací, ale v algoritmu s neomezenou délkou klíče může být tato možnost zbytečná. V takových případech můžete jednoduše resetovat přídavný klíč .
Výhody a nevýhody
- Jedno kolo šifrování algoritmu HPC sestává z velkého počtu základních operací. Ve srovnání například s domácím algoritmem GOST 28147-89 , který se skládá pouze ze 4 základních operací, se HPC zdá být extrémně složité a těžkopádné. Vzhledem k tomu, že všechny operace jsou prováděny na 64bitových slovech, vykazovalo HPC překvapivě vysokou rychlost na 64bitových platformách. V soutěži šifrovacích standardů AES bylo HPC z hlediska rychlosti šifrování 128bitových bloků na druhém místě za algoritmem DFC a HPC šifrovalo 512bitové a 1024bitové bloky 2-3krát rychleji než všichni jeho konkurenti.
- Zjevné nevýhody algoritmu zahrnují kromě složitosti nemožnost paralelizace procesů šifrování a míchání a také obrovské požadavky kladené algoritmem na energeticky nezávislou paměť a paměť s náhodným přístupem, což značně ztěžuje použití. to v čipových kartách .
- Algoritmus se nedostal do druhé fáze AES . Autor se ve svém článku [4] ohradil na experty AES v domnění, že priority byly v soutěži nastaveny špatně. Podle Richarda Schreppela je nutné volit algoritmy přizpůsobené pro 64bitové platformy jako světový standard, protože na nich je budoucnost. Autor HPC navíc tvrdil, že je nemožné vyvinout algoritmus, který by fungoval stejně dobře jak na výkonných vícejádrových 64bitových serverech, tak na slabých a levných 8bitových čipových kartách . Toto umístění však neovlivnilo výsledky soutěže.
Kryptoanalýza
- Aby podnítil zájem o kryptoanalýzu svého vynálezu, zavázal se autor odměnit každého kryptoanalytika lahví slavného šampaňského Dom Pérignon . Ceny budou udělovány do otevření kódu nebo do prázdné krabice (10 lahví). [5]
- Podle autora šifry má HPC úroveň zabezpečení 400 bitů , to znamená, že úspěšný útok na šifru bude vyžadovat testování. Takové prohlášení je založeno na počítání počtu přechodných stavů v procesu šifrování a také na velikosti rozšířeného klíče [6] .
Zranitelnosti
David Wagner zranitelnost v šifře [ 7] později Carl D'Halluin, Gert Bijnens, Bart Presnel a Vincent Rayman publikovali článek [8] , který to potvrdil. Ukázalo se, že přibližně každý 256. klíč algoritmu má 230 ekvivalentních klíčů . Tento nedostatek však autor ještě před sečtením výsledků prvního kola soutěže promptně napravil.
Attack "Chosen Spice"
S tímto typem útoku může útočník, který má přístup k párům holého textu a šifrovaného textu, pomocí manipulace s polem dodatečného klíče „Spice“ sledovat, jak se holý text nebo šifrovaný text mění v následujících šifrováních . Útoky tohoto typu však podle autora dosud nebyly pozorovány a práce v této oblasti vyžaduje úsilí kryptoanalytické komunity. [2]
Poznámky
- ↑ Šifrovací algoritmy Panasenko S.P. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - 576 s. — ISBN 978-5-9775-0319-8
- ↑ 1 2 Richard Schroeppel, "Hasty Pudding Cipher Specification", květen 1999 (odkaz není k dispozici) . Získáno 31. října 2010. Archivováno z originálu 17. července 2011.
- ↑ a mají stejný tvar, ale obecně řečeno se bude jednat o různá čísla, protože závisí na aktuální hodnotě .
- ↑ Rich Schroeppel, Puddingmeister, "The Hasty Pudding Cipher: One Year Later", 12. června 1999 (odkaz není k dispozici) . Získáno 31. října 2010. Archivováno z originálu dne 30. listopadu 2021.
- ↑ "BEZPEČNOSTNÍ SYSTÉMY KOMUNIKACÍ A TELEKOMUNIKACE", 1999 . Datum přístupu: 30. října 2010. Archivováno z originálu 3. července 2011.
- ↑ Rich Schroeppel, Hilarie Orman, „An Overview of the Hasty Pudding Cipher“, červenec 1998 (odkaz není dostupný) . Získáno 31. října 2010. Archivováno z originálu dne 30. listopadu 2021.
- ↑ Richard Schroeppel, „Tweaking the Hasty Pudding Cipher“ 14. května 1999 (odkaz není dostupný) . Získáno 31. října 2010. Archivováno z originálu dne 30. listopadu 2021.
- ↑ "Ekvivalentní klíče HPC", 1999
| Symetrické kryptosystémy | |
|---|---|
| Streamové šifry | |
| Síť Feistel | |
| Síť SP | |
| jiný | |