ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

ドイツのトリ Advent Calendar2018 9日目 調査

adventar.org

  

今までに入手したトリステッカー

2016年夏 10枚 - 初めての購入 このときTシャツも手に入れた

2017年夏 200枚 - 頭おかしい

2018年夏 50枚 - すぐなくなった(なんで?)

 

 

 

去年の暮れ, ちょうど一年前にドイツのトリ聖地巡礼をしました. が, 残念なことにドイツのトリは"おらんかった"(以下参照)ので, いつでもトリを見ることができるようにアプリを作りたいと思います.

 

時間がなかった

代わりにドイツのトリに関する意識調査のテンプレートを作成しました.  

 

f:id:ushiromiya3:20181130230555p:plain

 

texも置いておくのでコピペして自由に使ってください.

渋谷とかで実施してみるといいと思います. 僕はしませんが.

 

\documentclass[10pt, a4j]{jsarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath,amssymb}

\setlength{\textwidth}{\paperwidth}
\setlength{\oddsidemargin}{-10mm}
\setlength{\evensidemargin}{-10mm}
\addtolength{\textwidth}{-50mm}

\title{\vspace{-40mm} ドイツのトリに関する意識調査}
\date{}


\begin{document}
\maketitle
\vspace{-20mm}

\section{ドイツのトリを知っていますか?}
\noindent
$\Box$ 知っている \\
$\Box$ 知らない \\
$\Box$ 聖地巡礼した \\
$\Box$ 私がドイツのトリである \\
$\Box$ 興味ない

\vspace{-3mm}
\section{ドイツのトリをどこで知りましたか?}
\noindent
$\Box$ 西新宿 \\
$\Box$ ドイツ \\
$\Box$ SNS \\
$\Box$ ケルン

\vspace{-3mm}
\section{1.で知っていると答えた方にお聞きします。ドイツのトリが``お''った座標を知っていますか?}
\noindent
$\Box$ 知らない \\
$\Box$ どうでもいい \\
$\Box$ 48.10261N, 11.33151E \\
$\Box$ 秋葉原

\vspace{-3mm}
\section{ドイツのトリステッカーを持っていますか?}
\noindent
$\Box$ 持っている \\
$\Box$ いらないが持っている \\
$\Box$ 持っていない \\
$\Box$ いらない \\
$\Box$ 欲しくない \\
$\Box$ かわいい

\vspace{-3mm}
\section{ドイツのトリAdvent Calendarを知っていますか?}
\noindent
$\Box$ 知っている \\
$\Box$ 知っているし毎年記事を寄稿している \\
$\Box$ 今知った \\
$\Box$ 知りたくなかった

\vspace{-3mm}
\section{最後にドイツのトリについて自由にコメントをお書きください}

\end{document}

 

 

Golangで暗号化されたsocket通信をする

はじめに

Chacha20-Poly1305の解説と実装 の子記事になります.
上記事ではChacha20-Poly1305をPythonで再実装しましたが, 本記事ではGolangを用いて再再実装しました.

RFCs

  • ChaCha20 and Poly1305 for IETF Protocols
    RFC7539
  • HMAC-based Extract-and-Expand Key Derivation Function (HKDF)
    RFC5869
  • The Transport Layer Security (TLS) Protocol Version 1.3
    RFC8446
test vector
  • HKDFのPRK, OKMの導出
  • chacha20_encrypt
  • poly1305_mac, key_gen
  • chacha20_AEAD

のtest vectorを通してあるので実装としては信用して利用できます. 書き方については信用できませんが.

コードの解説がまだ書ききれていませんが一旦投稿します(ごめんなさい)


やったこと

基本的にはクライアントとサーバー間でデータを送受信してるだけです.
クライアントからの最初の送信(いわゆるClient Hello1)とそれに対するサーバーからの返答(いわゆるServer Hello)で共有鍵を作り, 以降の通信は鍵を使ってChacha20で暗号化しています. 今回は省きましたが, "Chacha20-Poly1305"を実装しているのでもちろんPoly1305を使ってメッセージ認証ができます.

socket通信はこちら(【Golang】Socket通信するプログラムを書いてみた)を参考にしました.

big.Intの扱い方やbig.Int to Bytes (Bytes to big.Int), SHA256やHMAC2など調べることが多くて大変でした.


以下の動画のように動作します.

上がserver, 下がclientになっています.
共有鍵がちゃんと同じであること, サーバーから送られてきた(暗号化されている)メッセージをクライアント側でちゃんと復号して"this is a message"と表示されていることが確認できました.


コードの解説

chacha20に使用するkey, nonceはTLS1.3であればHKDFで導出しますが, まだそこまで実装ができていないので今回は雑にDiffie-Hellmannで共有した鍵の先頭のバイトを使っています.


サーバー


クライアント


おわりに

最終的にはハンドシェイクも実装してTLS1.3サーバとして動くようにしたいと思います.


最終目標



1: 実際にはClient Helloしていない
2: 今回は出てこない HKDFに使う

Chacha20-Poly1305の解説と実装

セキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018 2日目.

この記事はセキュリティ・キャンプ全国大会2018で実装したTLS1.3(の筆者が担当した暗号部分)の再実装と解説を目的としている.

なんだこれは を読み返すと意味がわからなくなったので, これを機におさらいをする.


表記揺れについて

許して


どうやって実装するの??

RFCを読む. RFC7539

chacha20-poly1305の実装を詳しく解説している日本語のドキュメントはあまりない. この記事を読めば理解できる(はず). 多分これが一番わかりやすいと思います

RFCでところどころさんtest vectorが用意されているので, 新しく実装した部分はちゃんとテストしておくとよい.


Chacha20-Poly1305

Chacha20-Poly1305は暗号スイートの一種で, Chacha20(暗号化)とPoly1305(認証タグの生成)を組み合わせて使用する.


Chacha20

公開鍵暗号のストリーム暗号に分類されるアルゴリズムである.
ステート(state)と呼ばれるバイト列を使い, 平文とXORを取ることで暗号化する.


以下にChacha20のstateを示す.

f:id:ushiromiya3:20181120112018j:plain ステートを見るとまるでブロック暗号かのように思えるが, 任意長の平文を暗号化できパディングも必要ない. つまりストリーム暗号である.
ステートのブロックはそれぞれ 4 [Bytes] だが, 注意すべきはcounter以外はリトルエンディアンであること.
たとえばnonceとして0123456789AB を渡すと, stateでは

nonce1 = 3210
nonce2 = 7654
nonce3 = BA98

となる.
counterはビッグエンディアンでよいので counter=1は \x00\x00\x00\x01 になる.

上で示したstateはあくまで初期状態で, 暗号化に使われるstateは初期状態をもとにごちゃ混ぜにされる(といっても計算を施すだけだが).


Quarter Round

stateを変化させる計算を行う関数Quarter Roundについて.
Quarter Roundは4つの引数をとり足し算, XOR, bitローテーションを行う.
ただしステートは4 Bytes/block であることに注意(& 0xFFFFFFFFをすればよい).

   1.  a += b; d ^= a; d <<<= 16;
   2.  c += d; b ^= c; b <<<= 12;
   3.  a += b; d ^= a; d <<<= 8;
   4.  c += d; b ^= c; b <<<= 7;

ステートを4 × 4 の行列と見立て(上記画像参照), 列要素ごとに4回, 対角要素ごとに4回行いこれを10回繰り返す.

Chacha20の20は
(Quarter Round(列要素) × 4 + Quarter Round(対角要素) × 4) × 10 = 20 から来ている.

   1.  QUARTERROUND ( 0, 4, 8,12)
   2.  QUARTERROUND ( 1, 5, 9,13)
   3.  QUARTERROUND ( 2, 6,10,14)
   4.  QUARTERROUND ( 3, 7,11,15)

   5.  QUARTERROUND ( 0, 5,10,15)
   6.  QUARTERROUND ( 1, 6,11,12)
   7.  QUARTERROUND ( 2, 7, 8,13)
   8.  QUARTERROUND ( 3, 4, 9,14)

1~4が列要素, 5~8が対角要素のQuarter Roundで, 引数はstateのインデックスを表す.

10回繰り返した時点でstateはごちゃ混ぜにされているが, これに初期状態のstateを足し合わせてようやく完成.

擬似コードは以下のように示されている. 参照 - The ChaCha20 Block Function in Pseudocode

inner_block (state):
     Qround(state, 0, 4, 8,12)
     Qround(state, 1, 5, 9,13)
     Qround(state, 2, 6,10,14)
     Qround(state, 3, 7,11,15)
     Qround(state, 0, 5,10,15)
     Qround(state, 1, 6,11,12)
     Qround(state, 2, 7, 8,13)
     Qround(state, 3, 4, 9,14)
     end

chacha20_block(key, counter, nonce):
     state = constants | key | counter | nonce
     working_state = state
     for i=1 upto 10
        inner_block(working_state)
        end
     state += working_state
     return serialize(state)
     end

ここまでで暗号化に使用されるバイト列が生成できた. あとは平文とXORを取ればよい.
同じkey, nonceを使うと必ず同じstateが得られるので暗号文とXORを取れば復号が可能.

64バイトを超えた場合について.
The ChaCha20 Encryption Algorithm in Pseudocode

chacha20_encrypt(key, counter, nonce, plaintext):
    for j = 0 upto floor(len(plaintext)/64)-1
       key_stream = chacha20_block(key, counter+j, nonce)
       block = plaintext[(j*64)..(j*64+63)]
       encrypted_message +=  block ^ key_stream
       end
    if ((len(plaintext) % 64) != 0)
       j = floor(len(plaintext)/64)
       key_stream = chacha20_block(key, counter+j, nonce)
       block = plaintext[(j*64)..len(plaintext)-1]
       encrypted_message += (block^key_stream)[0..len(plaintext)%64]
       end
    return encrypted_message
    end

counterを1ずつ増やしながら新しくstateを得, 同じように暗号化するだけ.
counterの初期値は1であることに注意(counter=0はPoly1305で使用).


Poly1305

Poly1305は認証用のメッセージと鍵(32 [Bytes]を使って認証タグ(16 [Bytes])を生成する.
Chacha20のステートを利用してPoly1305の鍵を取得するためChacha20を先に実装しておく必要がある.
鍵生成の流れとしては,

  1. chacha_key, nonceを準備
  2. これらを使ってChacha20のstateを得る(counter=0)
  3. r = state[0 .. 15], s = state[16 .. 31] をPoly1305の鍵とする
    stateのはじめの4ブロックが "r", 次の4ブロックが "s"

鍵r, sそれぞれ16バイトのリトルエンディアンになることに注意しよう. 4バイトではない.
また, rはリトルエンディアンとして値を得てからclamp関数を適用し, 部分的にビットを落として利用する.

clamp関数の定義を以下に示す.

clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff

鍵を取得したらあとはタグを計算するだけである. 参照 - The Poly1305 Algorithms in Pseudocode

poly1305_mac(msg, key):
     r = (le_bytes_to_num(key[0..15])
     clamp(r)
     s = le_num(key[16..31])
     accumulator = 0
     p = (1<<130)-5
     for i=1 upto ceil(msg length in bytes / 16)
        n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
        a += n
        a = (r * a) % p
        end
     a += s
     return num_to_16_le_bytes(a)
     end

まずkeyからr, sに切り分ける.
次にAccumulatorとModulus pを定義する. pは2130 - 5という16 [Bytes]よりも少し大きな素数である.

msgを16バイトに切り分け, それぞれの末尾に0x01をくっつける. 最後のmsgが16バイトに満たない場合は気にせずそのまま0x01をくっつけてよい.
0x01をくっつけたバイト列をリトルエンディアンで数値に変換し順に計算を行う.
f:id:ushiromiya3:20181121214550j:plain

切り分けた全てのmsgに対して計算を行い, 最後に鍵sを足し合わせてタグの生成終了.. と思いきやまだ終わらない.
Accumulatorに s を足したものをまずは16バイトにそろえる必要がある(pが128 [Bits]を超えていることに注意).
mod 2**128 を取るか AND 0xFFFF...FF を取ろう.

あとはこの値をリトルエンディアンでバイト列に変換して終了となる.


Poly1305の安全性

Poly1305は認証タグを生成し, これはいわゆるハッシュ関数のようなものだがmd5SHA1/SHA2のような純粋なハッシュ関数と異なるのはメッセージの他にkeyを使用する点である.

これが何を意味するかと言うと, たとえば純粋なハッシュ関数H_FUNCを使用する場合

H_FUNC(data) = ハッシュ化された攻撃対象(解読したい)のメッセージ

となるdataを総当たり等で発見できた時, 攻撃が成功したことが明らかになる(ハッシュ衝突が起こり得ない空間であるとして).

対してPoly1305はメッセージが同じでもkeyが異なれば異なるハッシュ値を出力するため

Poly1305(data, key) = ハッシュ化された攻撃対象(解読したい)のメッセージ

となるdata, keyの組み合わせが万一発見できたとしても data = 攻撃対象のメッセージ である可能性は低い.


AEAD

暗号化と同時に認証タグを生成する.
Chacha20とPoly1305の実装ができていればタグの生成は難しくない.

chacha20_aead_encrypt(aad, key, iv, constant, plaintext):
     nonce = constant | iv
     otk = poly1305_key_gen(key, nonce)
     ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)
     mac_data = aad | pad16(aad)
     mac_data |= ciphertext | pad16(ciphertext)
     mac_data |= num_to_4_le_bytes(aad.length)
     mac_data |= num_to_4_le_bytes(ciphertext.length)
     tag = poly1305_mac(mac_data, otk)
     return (ciphertext, tag)

constant [4 Bytes] + iv [8 Bytes] をnonceとし, このnonceとkeyを使ってPoly1305のOne Time Keyを生成する.
次にChacha20を使って暗号化(使用するnonceとkeyはさっきと同じ)しciphertextを得る.
ciphertextが得られたらmac_dataを組み立てていく.

最後にmac_dataをmsg, One Time KeyをkeyとしてPoly1305で認証タグを生成する.


???

実はRFCに問題がある. Pseudocode for the AEAD Construction

擬似コードの後にtest vectorがあり,そこでは mac_data となる部分が

  AEAD Construction for Poly1305:
  000  50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 00 00 00 00  PQRS............
  016  d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2  ...4d.`.{...S.~.
  032  a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6  ...Q)n......6.b.
  048  3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b  =..^..g....i..r.
  064  1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36  .q.....)....~.;6
  080  92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58  ....-w......(..X
  096  fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc  ..$...u.U...H1..
  112  3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b  ?....Kz..v.e...K
  128  61 16 00 00 00 00 00 00 00 00 00 00 00 00 00 00  a...............
  144  0c 00 00 00 00 00 00 00 72 00 00 00 00 00 00 00  ........r.......

このようになっている.

末尾の num_to_4_le_bytes(aad.length)num_to_4_le_bytes(ciphertext.length) だが, test vectorでは4バイトではなく8バイトのリトルエンディアンである.
どちらが正しいのかを確認するためにopensslのchacha20_aeadのソースを漁ったが見つからなかった.

というか書いてあった.

*  The length of the additional data in octets (as a 64-bit
     little-endian integer).

*  The length of the ciphertext in octets (as a 64-bit little-
     endian integer).

トルエンディアンの8バイトが正しい.


まとめ

以下にコードを示した.
基本的にはRFC擬似コードを元にしているので擬似コードを模倣すれば任意の言語でChacha20-Poly1305が実装可能である.
擬似コードを読み返すと結構穴があるので, 実装でわからないことがあればRFCを読むか筆者にmentionを飛ばしてくれれば解決できると思う.


実際のコード

Gistで公開している.
ファイルごとに各節で表示したかったのだが..

ファイルは上から順に

  • aead_enc.py : chacha20, poly1305を使用してAEADを生成
  • calc.py : 主にchacha20で使用される計算の関数群
  • chacha20.py : Chacha20の実装
  • poly1305.py : Poly1305の実装
  • test.py : テストコード, RFCのtest vectorをクリア済
  • utils.py : utils

使用したモジュールはstructとbinasciiiのみ.


追記

こちら(Golangで暗号化されたsocket通信をする)にGolangを使ってChacha20-Poly1305を再再実装した記事を書きました.

matplotlibを使ってベクトルの可視化をする

目的

ベクトル, 行列の"計算をする"だけでなく, 実際にグラフで描画することで線形代数の気持ちを理解する.

線形代数の教材に良さそう.

使う

  • matplotlib
from mpl_toolkits.mplot3d import Axes3D  
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.gca(projection='3d')
ax.set_aspect("equal")

上のimport + 数行が動けばOK.


やったこと

Vectorクラスを定義して四則演算やメソッドを生やしていく.
matplotlibを使って描画.


できること

  • ベクトル同士の足し算
  • ベクトルのスカラー
  • ベクトルの行列積
  • もちろんベクトルの線型結合
  • 内積, 外積
  • Gram-schmidtのアルゴリズムによるベクトルの直交化

足し算

f:id:ushiromiya3:20181129003509p:plain

デフォルトではベクトルの始点は(0, 0, 0)にしているがこのように変えることもできる.
v1 + v2が実際に赤線のベクトルになっていることがわかる.

掛け算 1

f:id:ushiromiya3:20181129004128p:plain
スカラー積が得られる.

掛け算 2

f:id:ushiromiya3:20181129004752p:plain 引数に変換行列を与えることで一次変換もできる.

外積

f:id:ushiromiya3:20181129005210p:plain 2つのベクトルの外積が計算できる.
もちろん内積の計算も可能であり, v1, v2の外積v3はそれぞれのベクトルと直交する.
グラフをぐりぐり回転させると直交していることが視覚的に確認できる.

Gram-schmidt直交化

ベクトル2つ f:id:ushiromiya3:20181129005653p:plain

ベクトル3つ f:id:ushiromiya3:20181129010140p:plain

グラフの見易さのため正規化してある.
それぞれが直交していることも内積を取ることで確認できる.

今後の予定

考え中

Juliusで音声認識して結月ゆかりに喋ってもらう

ykm11.hatenablog.com

これの続き.

 

ソースコードGitHubにおいてあります.

github.com

 

 

やったこと

1. 連続音声認識ソフトウェアJuliusを使って喋った言葉を認識 :new:

http://julius.osdn.jp/index.php

2. 認識した言葉/文を読み上げテキストとして渡す :new:

3. VOICEROIDでゆかりんに喋ってもらう(前回記事参照)

 

 

喋ってもらう部分は, テキストを渡すだけでいいところまで実装してたので

・今回はマイクから拾った音声を認識する部分

・認識した言葉をVOICEROIDに渡す部分

を新たに実装(?)しました.  

 

 

認識した言葉をVOICEROIDに渡す部分はテキストを引数として再生をcallするだけです.  

マイクからの音声認識は, Juliusを立ち上げてlocalhostとソケット通信すれば認識したワードを得ることができます.

 

 

追記 25.11.2018  

5,6月に書いたものをずっと下書きで放置してた. なぜだろう.