AES-256を用いたDM型圧縮関数に対する衝突攻撃について

摘要

In 2009, Khovratovich, Biryukov and Nikolic presented a kind of collision attack on the Davies-Meyer (DM) compression function using AES-256. It is able to find q-pseudo collisions with complexity q · 2~(67). Unfortunately, it is not so efficient as the generic birthday attack for q = 1. In this article, we apply their technique to constructing a collision attack on the DM compression function using reduced AES-256. This attack is able to find a collision of the DM compression function using 12-round AES-256 with complexity 2~(56). We also show some results of the computer experiments of the collision attack on the DM compression function using 10/11-round AES-256.%2009年に，KhovratovichとBiryukovとNikolicによりAES-256を用いたDavies-Meyer型圧縮関数に対し，計算量q・2~(67)で同じハッシュ値に対応する同じ差分を有する入力の組を9組見つけることができる衝突攻撃が示された．この攻撃はq=1のとき誕生日攻撃より計算量が大きい．本研究では段数を減らしたAES-256を用いたDavies-Meyer型圧縮関数に対する衝突攻撃を検討した．我々は中間一致攻撃のアイデアを利用することで差分trailを構築し衝突攻撃を行った．本稿では，10段，11段，12段のAES-256を用いたDavies-Meyer型圧縮関数への衝突攻撃とその計算量について述べる．さらに10段，11段の場合に関する計算機実験の結果を示す．