Алдын ала шабуыл - Preimage attack

Жылы криптография, а алдын-ала шабуыл қосулы криптографиялық хэш функциялары а табуға тырысады хабар нақты хэш мәні бар. Криптографиялық хэш-функция шабуылдарға қарсы тұруы керек алдын-ала түсіру (мүмкін енгізулер жиынтығы).

Шабуыл аясында алдын-ала қарсылықтың екі түрі бар:

  • алдын-ала қарсылық: іс жүзінде барлық алдын-ала көрсетілген нәтижелер үшін осы нәтижеге сәйкес келетін кез-келген кірісті табу мүмкін емес; яғни берілген ж, табу қиын х осындай сағ(х) = ж.[1]
  • алдын-ала қарсылық: берілген кірістің нәтижесімен бірдей кез келген екінші кірісті табу есептеу мүмкін емес; яғни берілген х, екінші алдын-ала көріністі табу қиын х′ ≠ х осындай сағ(х) = сағ(х′).[1]

Оларды a-мен салыстыруға болады соқтығысуға төзімділік, онда кез-келген екі нақты кірісті табу мүмкін емес х, хOutput сол нәтижеге хэш; яғни, осылай сағ(х) = сағ(х′).[1]

Соқтығысуға қарсы тұру екінші кезектегі қарсылықты білдіреді,[1] бірақ алдын-ала қарсылыққа кепілдік бермейді.[1] Керісінше, екінші алдын-ала шабуыл соқтығысу шабуылын білдіреді (тривиальды, өйткені, қосымша) х′, х қазірдің өзінде белгілі).

Алдын ала шабуыл шабуылдары

Анықтама бойынша, идеалды хэш-функция бірінші немесе екінші алдын-ала суретті есептеудің ең жылдам тәсілі а арқылы жүретіндей қатал шабуыл. Үшін n-биттік хэш, бұл шабуылда а бар уақыттың күрделілігі 2n, бұл типтік шығу өлшемі үшін өте жоғары болып саналады n = 128 бит. Егер мұндай күрделілік қарсыластың қолынан келетін ең жақсы болса, онда хэш функциясы суретке төзімді болып саналады. Алайда, кванттық компьютерлер құрылымдық алдын-ала шабуыл жасайтын жалпы нәтиже бар 2n = 2n/2, бұл екінші алдын-ала бейнелеуді де білдіреді[2] және осылайша соқтығысу шабуылы.

Алдын ала шабуылдарды жылдамырақ табуға болады криптоанализ белгілі бір хэш функциялары және осы функцияға тән. Кейбір маңызды шабуылдар қазірдің өзінде табылды, бірақ олар әлі практикалық емес. Егер практикалық алдын-ала шабуыл анықталса, бұл көптеген Интернет протоколдарына әсер етуі мүмкін. Бұл жағдайда «практикалық» дегеніміз оны шабуылдаушы ресурстардың жеткілікті мөлшерімен орындай алатындығын білдіреді. Мысалы, триллиондаған доллар тұратын және бір қажетті хэш-мәнді немесе бір хабарламаны алдын-ала алуға ондаған жылдар қажет болатын алдын-ала жасалған шабуыл практикалық емес; құны бірнеше мың доллар тұратын және бірнеше аптаға созылатын өте пайдалы болуы мүмкін.

Қазіргі уақытта практикалық немесе практикалық шабуылдардың барлығы белгілі[3][4][5] қосулы MD5 және SHA-1 болып табылады соқтығысу шабуылдары[дәйексөз қажет ]. Жалпы, соқтығысу шабуылын алдын-ала жасалған шабуылға қарағанда оңайырақ орнатады, өйткені оны кез келген белгіленген мәнмен шектемейді (соқтығысу үшін кез-келген екі мәнді пайдалануға болады). Соқтығысу шабуылының уақыттық күрделілігі, керісінше, 2 құрайдыn/2.

Шектелген алдын-ала ғарыштық шабуылдар

Идеалды хэш-функцияға алдын-ала жасалған шабуылдың есептеу мүмкін еместігі, мүмкін хэш кірістерінің жиынтығы қатал күш іздеу үшін тым үлкен деп болжайды. Егер берілген хэш мәні салыстырмалы түрде аз немесе қандай-да бір жолмен ықтималдығы бойынша реттелген кірістер жиынтығынан өндірілгені белгілі болса, онда өрескел күш іздеу тиімді болуы мүмкін. Практикалық кіріс жиынтығының өлшеміне және хэш функциясын есептеу жылдамдығына немесе шығынына байланысты.

Жалпы мысал - сақтау үшін хэштерді пайдалану пароль аутентификация үшін тексеру деректері. Пайдаланушының парольдерінің қарапайым мәтінін сақтаудың орнына, кіруді басқару жүйесі парольдің хэшін сақтайды. Пайдаланушы кіруді сұрағанда, олар жіберген құпия сөз сақталады және сақталған мәнмен салыстырылады. Егер сақталған валидация деректері ұрланған болса, ұры тек пароль емес, тек хэш мәндеріне ие болады. Алайда, көптеген қолданушылар құпия сөздерді болжамды тәсілдермен таңдайды және көптеген парольдер жеткілікті қысқа, сондықтан жылдам хэштер қолданылса, барлық хэштерді тексеруге болады, тіпті егер хэш алдын-ала шабуылға қарсы қауіпсіз деп бағаланса да.[6] Арнайы хэштер шақырылды кілттерді шығару функциялары іздеуді баяулатуға арналған. Қараңыз Құпия сөзді бұзу.

Сондай-ақ қараңыз

  • Туған күнге шабуыл
  • Криптографиялық хэш функциясы
  • Хэш функциясы қауіпсіздігінің қысқаша сипаттамасы
  • Радуга үстелі
  • Кездейсоқ оракул
  • RFC  4270: Интернет хаттамаларындағы криптографиялық хэштерге шабуыл

Әдебиеттер тізімі

  1. ^ а б c г. e Рогауэй, П .; Шримптон, Т. (2004). «Криптографиялық Hash-функциясының негіздері: алдын-ала қарсылық, екінші деңгейге қарсы тұру және соқтығысуға қарсы тұрудың анықтамалары, салдары және бөлімдері» (PDF). Бағдарламалық жасақтаманы жылдам шифрлау. Шпрингер-Верлаг. Алынған 17 қараша 2012.
  2. ^ Даниэл Дж. Бернштейн (2010-11-12). «Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD және Skein-ге қарсы кванттық шабуылдар» (PDF). Чикагодағы Иллинойс университеті. Алынған 2020-03-29.
  3. ^ Брюс Мортон, Клейтон Смит (2014-01-30). «Неге біз SHA-2-ге ауысуымыз керек». Куәлік орталығы қауіпсіздік кеңесі.CS1 maint: авторлар параметрін қолданады (сілтеме)
  4. ^ «MD5 және перспективалар». 2009-01-01.
  5. ^ «Google Online Security Blog: алғашқы SHA1 соқтығысты жариялау». Алынған 2017-02-23.
  6. ^ Гудин, Дэн (2012-12-10). «25-графикалық процессор кластері Windows стандартты паролін <6 сағат ішінде бұзады». Ars Technica. Алынған 2020-11-23.