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

摘要

2009年に，KhovratovichとBiryukovとNikolicによりAES-256を用いたDavies-Meyer型圧縮関数に対し，計算量q·2~(67)で同じハッシュ値に対応する同じ差分を有する入力の組をq組見つけることができる衝突攻撃が示された．この攻撃はq＝1のとき誕生日攻撃より計算量が大きい．本研究では段数を減らしたAES-256を用いたDavies-Meyer型圧縮関数に対する衝突攻撃を検討した．我々は中間一致攻撃のアイデアを利用することで差分trail を構築し衝突攻撃を行った．本稿では，10段，11段，12段のAES-256を用いたDavies-Meyer型圧縮関数への衝突攻撃とその計算量について述べる．さらに10段，11段の場合に関する計算機実験の結果を示す．