<前の日記(2003年12月13日) 次の日記(2004年01月31日)> 最新 編集

高木浩光@自宅の日記

目次 はじめに 連絡先:blog@takagi-hiromitsu.jp
訪問者数 本日: 2983   昨日: 4374

2003年12月15日

アンチコリジョン機能のないRFIDタグの個数を調べる方法例

11月3日のアンチコリジョン機構がなければ紙幣にRFIDを付けても安全?で、

そのためには事実が知らされなくてはならない。IDが読めないことは関係がない。枚数を推定できるのかできないのかだ。そういう調査をしたという話は未だ聞いたことがない。

と書いたことに対して、

なんか相変わらず「とんでも」な事書いてるなぁ。 IDは読めないにしても、そこに何枚あるかがもし読み取られる状況であれば、って、なぜアンチコリジョン機構が必要か理解しているとは思えない記述。

少し検討してみよう。方式にもよるかもしれないが、基本的にはIDのビット列が異なる部分が衝突として検出されるはずである。(略)

例えば、128ビットの2つのIDのうち、 10ビットくらい違っていることは普通にありそうだ。 2^10=1024だから、普通の人は2千円〜1,024万円持っている可能性があることになる。実際に今持っているお札の数字をビット列にして、ビットが異なる数を検出したところ、 6個であった。さて私はいくら持っているだろうか?

調査なんぞしなくても、ちょっと考えてみれば済むことだ。衝突の話は、ブロッキング・タグの話が出てきた時に、ちゃんと読んでいればそういったことも分かるはずだ。

藝夢日報, アンチコリジョン機構を持たないIDタグの個数推定問題

などと書いている人がいると、11月3日のコメント欄で教えていただいた。

11月3日のコメントにも書いたように、デジタル化された後の話だけしても意味がない。アナログ信号レベルまで含めて何かできやしないかを確認する必要がある。一般に、セキュリティとは、すぐに思いつく正攻法の1つを否定して安心してよいという性質のものではない。そういう発想でセキュリティに関わる物を作ることは危険だ。

アナログ信号レベルで個数を推定する方法について、11月3日のコメント欄では、どのデジタル変調方式でも有効な、搬送波の位相のずれを測定する方法を挙げたが、そうした精密測定をしなくても、変調方式によってはもっと簡単な装置で推定する方法が有効である可能性があるので以下に書いておく。

位相のずれが搬送波の波長に比べて十分に短い(複数のタグからの距離の差が十分に小さく、応答のタイミングの個体差が十分に小さい)と仮定すると、複数のタグからの応答電波はリーダでは合成波として観測され、信号のデジタル変調方式がASKであるとすると、アナログ復調後の各ビットの重ね合わせは電位差として観測される。

(話を簡単にするためマンチェスタなどの変調符号のことを無視すると、)例えば 8ビットのランダムなビットパターンを応答するタグが2つあるとき、その重ね合わせは、

     10101001
     11000011
     --------
     21101012
などとなり、電位は最大のものに比して 100%, 50%, 50%, 0%, 50%, 0%, 50%, 100%となる。電位の数が3種類あることから、少なくとも2つのタグが存在することがわかる。

タグの数が増えると、0% や 100% などの極端な電位となるビット位置の存在確率が小さくなっていき、50% 前後の電位が多くなっていく。8ビットのタグが100個ある場合は、ほとんどのビット位置の電位が 50% 前後となるだろう。

では、128ビットのRFIDタグが30個存在する場合ではどうか。n通り以上の電位が現れる確率の計算式を求めればよいのだが、面倒なので、シミュレーションで確かめてみる。以下のRubyプログラムは、128ビットの乱数を32個生成して、各ビット位置ごとに1の数を合計し、合計数の集合を求めて、その要素の数を出力する。

num_of_tags = 30
num_of_bits = 128
srand
tags = []
for i in 0..(num_of_tags - 1)
    tags << rand(2 ** num_of_bits)
end
counters = []
for b in 0..(num_of_bits - 1)
    counters[b] = 0
    for i in 0..(num_of_tags - 1)
        if tags[i] % 2 == 1
            counters[b] += 1
        end
        tags[i] /= 2
    end
end
num = []
counters.each do |c|
    printf("%d ", c)
    num |= [c]
end
print "\n"
printf("%d\n", num.size)

これを25回試してみたところ次の結果となった。

19 15 21 19 16 14 15 14 15 15 16 17 15 14 14 15 13 14 14 13 14 15 15 15 15
これは、15種類前後の電位が観測されることを意味する。

タグの個数 n を変えながら試してみると、

n:
1: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2: 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4: 5 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5: 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6: 7 7 7 7 7 7 7 6 6 6 7 7 7 7 7 7 7 7 7 7 6 7 7 7 5
7: 8 8 8 8 7 7 7 7 8 8 7 7 8 8 8 8 7 8 7 6 8 8 8 8 8
8: 8 9 8 7 7 7 8 8 7 8 8 7 9 8 8 7 8 9 8 7 7 7 8 8 8
9: 8 9 8 8 10 8 9 7 9 8 8 9 8 9 9 8 9 8 9 8 8 8 8 8 9
10: 7 9 9 8 8 9 8 9 8 9 9 9 10 8 9 8 10 9 9 9 9 10 9 7 8
11: 9 10 9 10 9 10 10 10 9 9 9 9 10 9 8 8 9 9 10 10 9 9 9 8 9
12: 9 11 10 9 8 11 9 11 10 9 8 10 10 11 9 9 8 11 10 10 10 9 9 10 7
13: 10 10 10 10 10 8 9 9 10 9 11 8 9 11 8 9 10 10 10 9 10 10 9 10 10
14: 11 11 10 10 11 9 9 9 10 9 10 9 10 10 10 10 12 12 10 10 10 9 11 9 9
15: 11 12 11 11 12 10 12 11 11 11 11 10 8 12 10 10 9 12 10 11 12 10 9 10 10
16: 9 11 9 11 11 11 12 10 12 10 9 11 10 10 9 11 11 10 10 11 12 12 11 11 11
17: 13 11 10 10 9 11 12 11 11 11 10 10 11 11 12 13 11 10 10 11 12 11 13 12 12
18: 11 11 11 10 11 12 11 12 13 11 13 10 12 11 11 11 13 11 9 12 13 12 12 12 11
19: 12 11 12 13 12 12 11 12 10 13 13 11 13 11 12 11 12 12 11 12 13 12 12 11 11
20: 12 12 13 13 13 12 13 11 13 12 12 12 12 11 11 12 12 11 11 11 11 11 13 12 12
21: 13 11 12 11 12 13 13 11 12 11 14 12 11 12 12 13 12 13 12 11 13 13 11 12 12
22: 11 12 14 12 13 13 12 13 14 14 13 14 12 13 13 13 13 12 12 11 12 12 14 13 11
23: 13 15 13 13 13 12 12 13 12 12 12 13 13 13 12 14 14 13 13 14 12 14 13 13 12
24: 11 12 12 13 14 13 12 12 14 11 12 14 13 14 12 12 14 13 12 11 12 12 13 12 14
25: 13 13 13 13 14 13 13 13 13 13 13 13 13 16 13 13 14 13 12 14 13 14 13 14 12
26: 13 13 13 13 14 14 14 15 15 14 12 13 13 14 14 13 15 12 13 12 15 14 12 13 13
27: 15 14 12 14 15 12 13 13 13 13 15 14 14 15 13 15 14 12 14 12 14 13 13 12 15
28: 14 14 15 14 14 14 13 15 14 14 12 16 13 13 12 14 13 15 16 13 13 15 13 15 13
29: 13 13 14 14 15 13 15 13 15 14 15 14 14 15 16 13 14 14 14 15 13 15 14 13 15
30: 14 14 16 13 14 13 15 14 14 14 14 14 13 15 15 15 14 15 12 13 14 13 13 16 14
31: 16 14 14 14 16 16 15 16 13 13 14 14 13 13 13 14 15 13 16 17 14 12 14 16 13
32: 14 13 15 15 17 15 15 15 15 13 15 15 16 14 11 17 13 13 13 16 17 16 15 15 14
33: 15 15 15 17 14 14 14 14 17 14 14 15 14 15 14 15 18 16 14 15 15 18 14 15 14
34: 16 17 15 15 16 16 14 17 16 15 15 16 15 15 14 15 15 16 16 13 15 15 17 13 16
35: 16 14 16 15 15 14 15 15 16 15 18 15 17 14 17 15 15 15 16 15 14 16 16 15 17
36: 15 17 16 14 15 14 18 12 16 15 16 16 15 15 16 14 15 14 15 16 16 15 14 16 17
37: 16 17 16 15 14 16 16 16 13 16 16 19 15 17 15 17 14 16 14 14 18 15 13 16 15
38: 17 17 16 17 16 16 15 16 18 16 14 16 18 16 11 17 17 17 17 17 15 14 17 17 17
39: 15 17 16 14 17 18 14 15 17 17 19 16 14 16 16 17 18 17 15 15 17 14 16 16 16
40: 16 17 16 16 14 15 16 15 17 16 18 16 16 17 18 16 17 17 15 17 17 18 16 15 15
41: 14 18 17 19 18 15 16 16 16 15 17 17 16 13 16 17 18 17 14 16 16 16 18 16 16
42: 16 16 15 18 17 17 17 14 17 13 17 19 16 16 18 15 16 17 15 16 17 14 17 14 17
43: 15 16 15 19 18 13 15 17 14 20 17 16 16 14 18 16 15 19 16 15 17 14 19 17 16
44: 17 17 19 15 16 16 16 20 18 18 19 16 17 18 17 17 17 17 18 16 16 17 16 18 19
45: 19 16 18 16 18 18 16 17 16 18 16 18 18 16 17 18 17 14 17 16 15 15 16 17 15
46: 16 18 17 19 19 19 17 17 17 16 17 19 17 17 16 17 15 18 16 19 16 17 20 16 18
47: 18 16 17 18 16 19 17 17 14 19 19 17 17 19 18 18 18 20 17 18 19 17 16 18 16
48: 19 16 19 18 14 17 18 17 16 15 17 18 19 17 16 19 17 15 17 17 17 17 18 17 16
49: 19 15 17 19 18 17 17 19 17 19 16 18 17 19 18 16 19 17 17 19 17 19 17 16 18
50: 17 16 17 18 18 15 18 17 17 18 17 18 17 19 17 18 19 18 20 15 18 17 19 19 17
51: 19 17 17 17 18 17 17 19 16 17 16 18 16 16 17 16 17 18 19 17 17 17 19 18 17
52: 19 16 17 19 19 18 18 17 17 20 20 17 16 16 20 20 17 18 17 20 15 18 18 17 17
53: 17 18 17 17 18 17 16 17 18 20 19 17 18 17 17 18 17 17 19 17 20 19 20 19 17
54: 21 19 18 18 18 18 19 18 17 21 19 17 19 17 18 19 18 20 18 17 20 17 19 17 17
55: 18 20 17 19 17 17 19 17 19 19 19 18 20 17 21 17 19 18 20 16 18 19 20 17 19
56: 19 19 19 15 18 19 18 19 18 21 15 18 17 19 21 21 15 19 18 17 17 19 20 19 19
57: 20 17 18 20 19 18 22 20 18 18 19 18 19 18 21 16 17 19 18 17 17 20 19 21 20
58: 20 19 18 19 18 21 17 19 21 18 19 18 16 19 15 20 19 21 18 17 18 21 17 20 20
59: 19 19 20 20 19 20 15 19 20 20 19 21 18 21 18 18 19 20 17 19 22 18 19 17 22
60: 20 19 17 18 20 19 18 18 16 20 19 20 18 19 19 19 19 21 17 21 19 22 20 19 19
となった。

10個あたりまではおおむねの数を推定できることがわかる。25個くらいまでなら±数個の誤差で推定できるようだ。15種類の電位が計測されたときは、26個くらい以上があるらしいと判断できる。

以下は、波形を図にしてみたものだ。上の図はタグが30個の場合で、下の図は10個の場合である。10個と30個とでは、違いを検出する装置を作れそうに思える。

電位の数ではなく電位の絶対値(コリジョンのない信号部分の電位に対する比の値)から量子化ステップ数を求めて、タグの数を推定することもできるかもしれない。ただ、それは精密な解像度で電位を計測できるとの仮定が必要なので、上では同じ電位を示す数からおおまかに推定する方法を考えてみた。

電位の数を測定するにしても、測定精度の問題で、いくつまでを区別できるかはわからない。例えば、30段階に区別するのは難しいのかもしれない。

こうしたことができないことを確かめる必要があることを、11月3日の日記では述べた。

検索

<前の日記(2003年12月13日) 次の日記(2004年01月31日)> 最新 編集

最近のタイトル

2017年12月29日

2017年10月29日

2017年10月22日

2017年07月22日

2017年06月04日

2017年05月13日

2017年05月05日

2017年04月08日

2017年03月10日

2017年03月05日

2017年02月18日

2017年01月08日

2017年01月04日

2016年12月30日

2016年12月04日

2016年11月29日

2016年11月23日

2016年11月05日

2016年10月25日

2016年10月10日

2016年08月23日

2016年07月23日

2016年07月16日

2016年07月02日

2016年06月12日

2016年06月03日

2016年04月23日

2016年04月06日

2016年03月27日

2016年03月14日

2016年03月06日

2016年02月24日

2016年02月20日

2016年02月11日

2016年02月05日

2016年01月31日

2015年12月12日

2015年12月06日

2015年11月23日

2015年11月21日

2015年11月07日

2015年10月20日

2015年07月02日

2015年06月14日

2015年03月15日

2015年03月10日

2015年03月08日

2015年01月05日

2014年12月27日

2014年11月12日

2014年09月07日

2014年07月18日

2014年04月23日

2014年04月22日

2000|01|
2003|05|06|07|08|09|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|05|06|07|08|09|10|11|12|
2012|02|03|04|05|06|07|08|09|
2013|01|02|03|04|05|06|07|
2014|01|04|07|09|11|12|
2015|01|03|06|07|10|11|12|
2016|01|02|03|04|06|07|08|10|11|12|
2017|01|02|03|04|05|06|07|10|12|
<前の日記(2003年12月13日) 次の日記(2004年01月31日)> 最新 編集