GOST (karma işlevi) - GOST (hash function)

GOST karma işlevistandartlarda tanımlanmıştır GOST R 34.11-94 ve GOST 34.311-95 256 bit kriptografik karma işlevi. Başlangıçta Rus ulusal standardında tanımlandı GOST R 34.11-94 Bilgi Teknolojisi - Kriptografik Bilgi Güvenliği - Hash Fonksiyonu. Diğer üye devletler tarafından kullanılan eşdeğer standart BDT GOST 34.311-95.

Bu işlev, farklı bir Streebog standardın yeni revizyonunda tanımlanan karma işlevi GOST R 34.11-2012.^[2]

GOST hash işlevi, GOST blok şifresi.

Algoritma

GOST, değişken uzunluklu bir mesajı 256 bitlik sabit uzunlukta bir çıktı halinde işler. Giriş mesajı 256 bitlik bloklardan (sekiz adet 32 ​​bitlik) oluşan parçalara bölünmüştür. küçük endian tamsayılar); mesaj yastıklı mesajın uzunluğunu 256 bit'e getirmek için gerektiği kadar sıfır ekleyerek. Kalan bitler, önceden karma hale getirilmiş tüm blokların 256 bitlik tam sayı aritmetik toplamı ve ardından orijinal mesajın uzunluğunu bit cinsinden temsil eden 256 bitlik bir tam sayı ile doldurulur.

Temel gösterim

Algoritma açıklamaları aşağıdaki gösterimleri kullanır:

• ${ displaystyle { mathcal {f}} 0 { mathcal {g}} ^ {j}}$ - sıfırlarla dolu j-bit blok.
• ${ displaystyle { mathcal {j}} M { mathcal {j}}}$ - modulo 2 bit cinsinden M bloğunun uzunluğu²⁵⁶.
• ${ displaystyle { mathcal {k}}}$ - iki bloğun birleştirilmesi.
• ${ displaystyle +}$ - modulo 2 iki bloğun aritmetik toplamı²⁵⁶
• ${ displaystyle oplus}$ - iki bloğun mantıksal xoru

Ayrıca, küçük dereceli bitin bir bloğun solunda ve yüksek dereceli bitin sağda bulunduğunu düşünüyoruz.

Açıklama

Giriş mesajı ${ displaystyle M}$ 256 bitlik bloklara bölünmüştür ${ displaystyle m_ {n}, m_ {n-1}, m_ {n-2}, ..., m_ {1}}$Son blok durumunda ${ displaystyle m_ {n}}$ 256 bitten daha az içerir, istenen uzunluğa ulaşmak için başına sıfır bit bırakılır.

Her blok, adım karma işlevi tarafından işlenir ${ displaystyle H_ {out} = f (H_ {in}, m)}$,nerede ${ displaystyle H_ {çıkış}}$, ${ displaystyle H_ {in}}$, ${ displaystyle m}$ 256 bitlik bloklardır.

Birincisinden başlayan her mesaj bloğu, adım karma işlevi tarafından işlenir. ${ displaystyle f}$, ara hash değerini hesaplamak için
${ displaystyle ! H_ {i + 1} = f (H_ {i}, m_ {i})}$
${ displaystyle H_ {1}}$ değer isteğe bağlı olarak seçilebilir ve genellikle ${ displaystyle 0 ^ {256}}$.

Sonra ${ displaystyle H_ {n + 1}}$ hesaplanır, nihai hash değeri aşağıdaki şekilde elde edilir

• ${ displaystyle H_ {n + 2} = f (H_ {n + 1}, L)}$burada L - M mesajının modulo bit cinsinden uzunluğu ${ displaystyle 2 ^ {256}}$
• ${ displaystyle h = f (H_ {n + 2}, K)}$, burada K - M'nin 256 bitlik kontrol toplamıdır: ${ displaystyle m_ {1} + m_ {2} + m_ {3} + ... + m_ {n}}$

${ displaystyle h}$ M mesajının hash fonksiyonunun istenen değeridir.

Dolayısıyla, algoritma aşağıdaki gibi çalışır.

1. Başlatma:
   1. ${ displaystyle h : = ilk}$ - Kullanıcı tarafından belirlenen, karma işlevinin ilk 256 bit değeri.
   2. ${ displaystyle Sigma : = 0}$ - Kontrol toplamı
   3. ${ displaystyle L : = 0}$ - Mesaj uzunluğu
2. Dahili yinelemelerin sıkıştırma işlevi: i = 1… n - 1 için aşağıdakileri yapın ( ${ displaystyle | M |> 256}$):
   1. ${ displaystyle h : = f (h, m_ {i})}$ - adım karma işlevi uygulayın
   2. ${ displaystyle L : = L + 256}$ - mesaj uzunluğunu yeniden hesapla
   3. ${ displaystyle Sigma : = Sigma + m_ {i}}$ - kontrol toplamını hesapla
3. Son yinelemenin sıkıştırma işlevi:
   1. ${ displaystyle L : = L + { mathcal {j}} m_ {n} { mathcal {j}}}$ - tam mesaj uzunluğunu bit cinsinden hesaplayın
   2. ${ displaystyle m_ {n} : = {0} ^ {256 - { mathcal {j}} m_ {n} { mathcal {j}}} { mathcal {k}} m_ {n} }$ - son mesajı sıfırlarla doldurun
   3. ${ displaystyle Sigma : = Sigma + m_ {n}}$ - güncelleme kontrol toplamı
   4. ${ displaystyle h : = f (h, m_ {n})}$ - son mesaj bloğunu işle
   5. ${ displaystyle h : = f (h, L)}$ - MD - ileti uzunluğuna hashing uygulayarak güçlendirin
   6. ${ displaystyle h : = f (h, Sigma)}$ - hash kontrol toplamı
4. Çıkış değeri ${ displaystyle h}$.

Adım karma işlevi

Adım karma işlevi ${ displaystyle f}$ 256 bitlik iki bloğu tek bir blok halinde eşler: ${ displaystyle H_ {out} = f (H_ {in}, m)}$Üç bölümden oluşur:

• Anahtarların oluşturulması ${ displaystyle K_ {1}, K_ {2}, K_ {3}, K_ {4}}$
• Şifreleme dönüşümü ${ displaystyle H_ {in}}$ tuşları kullanmak ${ displaystyle K_ {1}, K_ {2}, K_ {3}, K_ {4}}$
• Karışık dönüştürme

Anahtar oluşturma

Algoritma üreten anahtarlar şunları kullanır:

• 256 bitlik blokların iki dönüşümü:
  • dönüşüm ${ displaystyle A (Y) = A (y_ {4} { mathcal {k}} y_ {3} { mathcal {k}} y_ {2} { mathcal {k}} y_ {1}) = (y_ {1} oplus y_ {2}) { mathcal {k}} y_ {4} { mathcal {k}} y_ {3} { mathcal {k} } y_ {2}}$, nerede ${ displaystyle y_ {1}, y_ {2}, y_ {3}, y_ {4}}$ 64 bitlik alt bloklardır Y.
  • dönüşüm ${ displaystyle P (Y) = P (y_ {32} { mathcal {k}} y_ {31} { mathcal {k}} dots { mathcal {k}} y_ {1}) = y _ { varphi (32)} { mathcal {k}} y _ { varphi (31)} { mathcal {k}} dots { mathcal {k}} y _ { varphi (1)}}$, nerede ${ displaystyle varphi (ben + 1 + 4 (k-1)) = 8i + k, i = 0, noktalar, 3, k = 1, noktalar, 8}$, ve ${ displaystyle y_ {32}, y_ {31}, noktalar, y_ {1}}$ 8 bitlik alt bloklardır Y.
• Üç sabit:
  • C₂ = 0
  • C₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
  • C₄ = 0

Algoritma:

1. ${ displaystyle U : = H_ {in}, quad V : = m, quad W : = U oplus V, quad K_ {1} = P (W)}$
2. İçin j = 2,3,4 aşağıdakileri yapın:

   ${ displaystyle U: = A (U) oplus C_ {j}, quad V: = A (A (V)), dört W: = U oplus V, dört K_ {j} = P (W )}$

Şifreleme dönüşümü

Anahtar üretiminden sonra, ${ displaystyle H_ {in}}$ kullanılarak yapılır GOST 28147-89 anahtarlar üzerinde basit değiştirme modunda ${ displaystyle K_ {1}, K_ {2}, K_ {3}, K_ {4}}$Şifreleme dönüşümünü E olarak gösterelim (Not: E dönüşümü, 256-bit anahtar kullanarak 64-bit veriyi şifreler). Şifreleme için ${ displaystyle H_ {in}}$ dört 64 bit bloğa bölünmüştür: ${ displaystyle H_ {in} = h_ {4} { mathcal {k}} h_ {3} { mathcal {k}} h_ {2} { mathcal {k}} h_ {1}}$ve bu blokların her biri şu şekilde şifrelenir:

• ${ displaystyle s_ {1} = E (h_ {1}, K_ {1})}$
• ${ displaystyle s_ {2} = E (h_ {2}, K_ {2})}$
• ${ displaystyle s_ {3} = E (h_ {3}, K_ {3})}$
• ${ displaystyle s_ {4} = E (h_ {4}, K_ {4})}$

Bundan sonra, sonuç blokları 256 bitlik bir bloğa birleştirilir: ${ displaystyle S = s_ {4} { mathcal {k}} s_ {3} { mathcal {k}} s_ {2} { mathcal {k}} s_ {1}}$.

Karışık dönüştürme

Son adımda, karıştırma dönüşümü şuna uygulanır: ${ displaystyle H_ {in}}$, S ve m kullanarak Doğrusal geri besleme kaydırma yazmacı. Sonuç olarak, ara hash değeri ${ displaystyle H_ {çıkış}}$ elde edildi.

İlk önce ψ işlevini tanımlıyoruz, LFSR 256 bitlik bir blokta: ${ displaystyle psi (Y) = psi (y_ {16} { mathcal {k}} y_ {15} { mathcal {k}} ... { mathcal {k}} y_ {2} { mathcal {k}} y_ {1}) = (y_ {1} oplus y_ {2} oplus y_ {3} oplus y_ {4} oplus y_ {13} oplus y_ {16}) { mathcal {k}} y_ {16} { mathcal {k}} y_ {15} { mathcal {k}} ... { mathcal {k}} y_ {3} { mathcal {k}} y_ {2 }}$, nerede ${ displaystyle y_ {16}, y_ {15}, ..., y_ {2}, y_ {1}}$ 16 bitlik alt bloklardır. Y.

Karışık dönüşümü ${ displaystyle H_ {out} = { psi} ^ {61} (H_ {in} oplus psi (m oplus { psi} ^ {12} (S)))}$, nerede ${ displaystyle { psi} ^ {i}}$ i-inci gücünü gösterir ${ displaystyle psi}$ işlevi.

Başlangıç ​​değerleri

GOST R 34.11 94 için yaygın olarak kullanılan iki ilk parametre seti vardır. Her iki set için de başlangıç ​​vektörü

${ displaystyle H_ {1}}$= 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

GOST R 34.11 94 standardının kendisi algoritma başlangıç ​​değerini belirtmese de ${ displaystyle H_ {1}}$ ve S-kutusu şifreleme dönüşümünün ${ displaystyle E}$, ancak örnekler bölümlerinde aşağıdaki "test parametrelerini" kullanır.^[3]

"Test parametreleri" S kutusu

RFC 5831 yalnızca bu parametreleri belirtir, ancak RFC 4357 bunları "test parametreleri" olarak adlandırır ve üretim uygulamalarında kullanılmalarını tavsiye etmez.

CryptoPro S-kutusu

CryptoPro S-kutusu CryptoPro şirketi tarafından geliştirilen "üretime hazır" parametre setinden gelir, ayrıca RFC 4357 bölüm 11.2.

Kriptanaliz

2008'de, tam kapsamlı GOST hash işlevini bozan bir saldırı yayınlandı. Kağıt bir çarpışma saldırısı 2'de¹⁰⁵ zaman ve birinci ve ikinci ön görüntü saldırıları 2'de¹⁹² zaman (2ⁿ zaman, algoritmanın saldırıda yaklaşık kaç kez hesaplandığını ifade eder).^[1]

GOST hash testi vektörleri

"Test parametreleri" için karmalar

256-bit (32-bayt) GOST hash değerleri tipik olarak 64-digit hexadecimal sayılar olarak temsil edilir. Burada GOST hash için "test parametreleri" ile test vektörleri bulunmaktadır.

GOST ("Hızlı kahverengi tilki tembelin üzerinden atlar dog ") = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

Mesajdaki küçük bir değişiklik bile, çok büyük olasılıkla, nedeniyle tamamen farklı bir hash ile sonuçlanacaktır. çığ etkisi. Örneğin, değiştirme d -e c:

GOST ("Hızlı kahverengi tilki tembelin üzerinden atlar cog ") = a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

GOST R 34.11-94 standardından gelen iki örnek:^[3]

GOST ("Bu mesajdır, uzunluk = 32 bayt") = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffaGOST ("Orijinal mesajın uzunluğunun = 50 bayta sahip olduğunu varsayalım") = 471aba57a60a770d3a55420ae30635c1f51

Daha fazla test vektörü:

GOST ( "") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dGOST ( "a") = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddGOST ( "mesaj" sindirmek) = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dGOST = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4GOST ( 'U' 128 karakter) ( 'a' 1000000 karakter)

CryptoPro parametreleri için karmalar

CryptoPro S-box ile GOST algoritması, farklı hash değerleri kümesi üretir.

= 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

GOST ( "a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011GOST ( "abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cGOST ( "mesaj özeti") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0GOST ( "Hızlı kahverengi tilki tembel köpeğin üstünden atlar") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76GOST ( "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61GOST ( "12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90GOST = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebGOST ( "orijinal mesaj uzunluğu = 50 bayt olduğunu varsayalım") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8GOST = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011GOST ( "U" 128) (1000000 "a") 869 = ( "Bu mesaj, uzunluk = 32 bayttır") 3287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

Ayrıca bakınız

• Kupyna
• Karma işlevi güvenlik özeti
• GOST standartları
• Karma işlevlerin listesi

Referanslar

daha fazla okuma

• "GOST R 34.11-94: Hash Fonksiyonu Algoritması". IETF. Mart 2010.
• "Bilgi teknolojisi. Kriptografik veri güvenliği. Hashing işlevi". 2010-02-20. GOST R 34.11-94 standardının tam metni (Rusça).

Dış bağlantılar

• C uygulama ve test vektörleri Markku-Juhani Saarinen'den GOST hash işlevi için, GOST 28147-89 ve GOST R 34.11-94 standartlarının İngilizce'ye taslak çevirileri de içerir. Hata düzeltilmiş sürüm, bkz. [1].
• STL akışlarıyla C ++ uygulaması^{[kalıcı ölü bağlantı ]}.
• RHash, bir açık kaynak GOST karmasını hesaplayabilen ve doğrulayabilen komut satırı aracı (her iki parametre setini de destekler).
• GOST R 34.11-94'ün uygulanması JavaScript (CryptoPro parametreleri )
• GOST Hash Function Ecrypt sayfası
• Çevrimiçi GOST Hesaplayıcı