高度版ランダム化加算減算鎖法に対する多重電力解析  [in Japanese] A Multiple Power Analysis Breaks the Advanced Version of the Randomized Addition-subtraction Chains Countermeasure against Side Channel Attacks  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

サイドチャネル攻撃に対する高度版ランダム化加算減算鎖法による防御法は,新しい種類のサイドチャネル攻撃である,多重電力解析攻撃(MPA攻撃)に脆弱であることを示す.サイドチャネル攻撃は暗号実行時に漏洩する情報を用いた攻撃方法である.ランダム化加算減算鎖法は,Oswald-Aignerにより提案され,計算中にランダム決定を挿入する手法を用いている.この防御法には基本版と高度版がある.基本版はサイドチャネル攻撃に対して脆弱であることが示されている.これは,秘密スカラーのビットが0の場合,ランダム化のための状態数が縮退してしまうことによる.しかしながら,高度版ではそのような縮退は発生しない.多重電力解析は,電力消費量の測定と加算/2倍算の識別能力により得られる複数のAD列(加算と2倍算より成る列)を用い,そのAD列を互いに組み合わせることにより,秘密スカラーを特定する.高度版への多重電力解析におけるポイントは,2つのステートを結合し,1つのものと考えるところにある.これにより,秘密スカラーのビットが0のときにステートの数の縮退が発生する.与えられたAD列の集まりから,秘密スカラーを特定する提案攻撃アルゴリズムをANSI Cにより実装した.プログラムの入力は,高度版ランダム化加算減算鎖法を用いた,秘密スカラーによるスカラー倍に付随するAD列の集まりである.攻撃プログラムは秘密スカラーを特定し,攻撃アルゴリズムが実際に秘密スカラーを特定できることが示された.We show that the advanced version of a randomized addition-subtractionchains countermeasure against side channel attacksis vulnerable to a multiple power analysis attack, a new kind of side channel attack,under distinguishability betweenaddition and doubling.A side channel attack is an attackthat takes advantage of information leakedduring execution of a cryptographic procedure.The randomized addition-subtraction chains countermeasurehas been proposed by Oswald-Aigner,and is a random decision inserted into computations.The countermeasure has two versions;the basic version and the advanced version.The basic version has been proved to bevulnerable to a side channel attack.This is due to a shrink of states for randomizationif a bit of the secret scalar is zero.However, the advanced version does not havesuch a shrink.Thus, the advanced version's immunityto side channel attacks is still controversial.The multiple power analysis uses plural AD sequences,which are sequences of additions and doublings, andobtained by the distinguishability and measurements.The multiple power analysis relates the AD sequences each other,and deduces the secret scalar.A point of the multiple power analysis againstthe advanced version is thattwo different states are combined, and regarded as the same state.This provides a shrink of statesif a bit of the secret scalar is zero.We have implemented the proposed attack algorithmagainst the advanced version,whose input is a set of AD sequences,which consist of the characters ``A'' and ``D'' to indicate addition and doubling, respectively.Our program has clarified the effectiveness of the attack.The attack algorithm could actually detectsecret scalars for given AD sequences.

We show that the advanced version of a randomized addition-subtraction chains counter-measure against side channel attacks is vulnerable to a multiple power analysis attack, a new kind of side channel attack, under distinguishability between addition and doubling. A side channel attack is an attack that takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure has been proposed by Oswald-Aigner, and is a random decision inserted into computations. The countermeasure has two versions; the basic version and the advanced version. The basic version has been proved to be vulnerable to a side channel attack. This is due to a shrink of states for randomization if a bit of the secret scalar is zero. However, the advanced version does not have such a shrink. Thus, the advanced version's immunity to side channel attacks is still controversial. The multiple power analysis uses plural AD sequences, which are sequences of additions and doublings, and obtained by the distinguishability and measurements. The multiple power analysis relates the AD sequences each other, and deduces the secret scalar. A point of the multiple power analysis against the advanced version is that two different states are combined, and regarded as the same state. This provides a shrink of states if a bit of the secret scalar is zero. We have implemented the proposed attack algorithm against the advanced version, whose input is a set of AD sequences, which consist of the characters "A" and "D" to indicate addition and doubling, respectively. Our program has clarified the effectiveness of the attack. The attack algorithm could actually detect secret scalars for given AD sequences.

Journal

  • Transactions of Information Processing Society of Japan

    Transactions of Information Processing Society of Japan 44(8), 1924-1937, 2003-08-15

    Information Processing Society of Japan (IPSJ)

References:  24

Codes

  • NII Article ID (NAID)
    110002711788
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    6677915
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-741
  • Data Source
    CJP  NDL  NII-ELS  IPSJ 
Page Top