平均時・最悪時の話

djbがなんか言ってるのでメモ。

格子の例は強い意味での平均時/最悪時帰着になっているので、広く宣伝されているわけですが、よく「強い意味で」というところが省略されているので、誤解を招いているようです。
djbが指摘しているように離散対数系のランダム自己帰着性は古くから知られている話なので、誤解を招く表現は確かによくないですね。はい。

PS3の署名に対する攻撃の話

Chaos Computer Club (CCC) により開催されたハッカー・カンファレンス 27C3 において、Bushing 氏、Marcan 氏、Sven 氏の3名により PS3 の新たな exploit が公開されました。
PS3 では ECDSA と呼ばれる電子署名アルゴリズムが用いられているそうですが、そこで private key を生成する際に用いられる本来はランダムに生成される数値が、実は固定されていることを彼らは発見したそうです。それにより容易に praivate key を見つけることができるようになったそうです。(もう見つけてる?)

カスタムなPSPBLOG: PS3の新たなHackの始まり – fail0verflow

Prominent hackers Bushing, Marcan, and Sven took the stage at this year’s annual Chaos Communication Congress (27C3) to showcase their latest underground efforts on PS3. The trio describe Sony’s security measures as an ‘epic fail,’ pointing to the botched implementation of ECDSA. Apparently, the so-called ‘random’ number used to create the private key is always static.

What does mean for you, the end-user? Well, it means that homebrew devs can essentially sign their own applications. The keys generated as every bit as valid Sony’s own official signatures. Full control means custom firmware is within grasp. What’s more, is that the feat is valid for all current firmware up to 3.55 and possibly beyond.

Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access - eXophase.com

下の動画が攻撃者の発表。

全部版
27C3 - Console Hacking 2010 on Vimeo
スライド
27C3: Console Hacking 2010

えーと元の人も勘違いしているみたいだけど、「署名するときに使う乱数を固定できた」ので「秘密鍵を取り出せた」との説明が正しいのではないか.
ECDSAの署名アルゴリズムをざっくり書くと, メッセージをM, 秘密鍵をkとして,

  1. e = msb_n(Hash(M))
  2. mをZ_q上の乱数として, R = (mG)_x
  3. s = (e + kR)/m
  4. (R,s)を署名とする

となっている (細部は省略).

仮に乱数 m が固定されていると,

  1. 乱数を固定する
  2. メッセージM_1で署名(R_1,s_1) を得る
  3. メッセージM_2で署名(R_2,s_2) を得る
  4. m = (e_1 + k R_1)/s_1 = (e_2 + k R_2)/s_2
  5. kについて解くと, k = (s_1 e_2 - s_2 e_1) / (R_1 s_2 - R_2 s_1)

と署名を2つ得ることで秘密鍵が取り出せる. (動画の最初に出てくる数式)

Sony側が乱数固定してた」ってなってるけど本当なんですかね?

Sony側が固定してたらしい.


Clarification #3: The private keys refer to keys that Sony HQ uses. PS3s don't have these keys (but we calculated them due to the fail).

Clarification #4: the random number isn't 4, it's more like 007eabbb79360e14df1457a4194b82f71a0dc39280 (example). But it's still constant.
だそうな。

ファイル暗号化のためにAESの「秘密鍵 = private key」を作る+「秘密鍵」にSonyが署名も付けていた→署名の実装バグ→署名用の「署名鍵(秘密鍵)」が漏れる
ということなんだろうか?

CRT

考えるの面倒臭くなってmapとapplyで全て済ましたというメモ。

(define (ExGCD x y)
  ;;;Input: x, y in Z
  ;;;Output: a and b s.t. ax + by = gcd(a,b)
  (let loop ((r0 x) (r1 y) (a0 1) (a1 0) (b0 0) (b1 1))
    (if (= r1 0)
        (values r0 a0 b0)
      (receive (q r) (quotient&remainder r0 r1)
               (loop
                 r1 r
                 a1 (- a0 (* q a1))
                 b1 (- b0 (* q b1)))))))

(define (inverse-p x p)
  ;;;Input: x in Z
  ;;;Output: x^{-1} mod p
  ;;;find a s.t. ax + bp = 1 and return a mod p.
  (receive (r a b) (ExGCD x p)
           (modulo a p)))

(define (CRT lis)
  ;;;INPUT: ((b1 . d1) (b2 . d2) ...)
  ;;;Output: N s.t. N \equiv b_i mod d_i
  (let1 N (apply * (map cdr lis))
        (modulo 
         (apply +
                (map (lambda (c)
                       (apply *
                              (list (car c)
                                    (/ N (cdr c))
                                    (inverse-p (/ N (cdr c)) (cdr c)))))
                     lis))
         N)))

  • STOC 2010のY. Dodis, M. Pătraşcu, M. Thorupのが面白そうだとは思わんかね。
    • A[1...n] in {0,...,9}^nなるベクトルを考える。10進n桁の整数である。計算機上(PRAMでモデル化してる)で、各桁 A[i]を読み書きする機能を高速化しつつ保存容量をなるべく小さくしたい。さてどうする?
      • 素直に2進表記した場合は保存容量は\lfloor n \cdot \log_2{10} \rfloorとなるが、読み書き機能にO(n)掛かる。
      • ハフマン符号化した場合は(ようするに各A[i]をそれぞれ2進数で表して保存)、保存容量が4n、読み書き機能はO(1)と速い。
      • いいとこどりしたのが今回の話。ここ5年位ずっとある流れですね。
      • さらに実はprefix-free codeと基数の置き換えが関連しているという話があるらしく、真面目に読みたい。DodisがいるのはMACとかに関連してくるからだそうで。
  • SHA3の話を天下一武闘会に例えると受けた。

  • 2月中、書くの忘れてた。
  • 博論が終わったので、色々読んでいる最中。
  • Toy soldiers楽しい. Tower Defenseに介入出来るだけでこんなに違うのね。
  • 2010/121, 2010/127.
    • 格子暗号でCCA2出来たよと言われましても、Peikert and Waters (STOC 2008) とPeikert (STOC 2009) があるんですけどね。内容は間違っているので読まなくても大丈夫です。CCA2の証明に誤りあり。

  • 博論は最後の追い込み中らしい。卒業出来たら晴れて研究職です。
    • 最初の半年は新人研修だとか。9-17なので研究出来るとか言われても。
  • SCIS中に査読1つ終えるとか。そしたらもう1個来るとかなんとか。
  • 今年のナイトセッションではTwitter上の情報からソーシャルハックというネタを考え、実際に2〜3人実名と所属を特定したのですが、本人の許可を取ってなかったので、ぽしゃりました。残念。ナイトセッションの締め切りが早過ぎた。また来年に期待しましょう。