「Implementing SSL / TLS」を Rust で
dmystk前提
本はこちらです。全文英語なのでご注意ください。
原文ではサンプルコードが C 言語で記述されていますが、今回は Rust で書き直しながら読み進めます。
Rust についても初学者なので、色々と書き留めていきます。
書いたコードは こちら に置いてあります。
dmystkChapter 1 : Understanding Internet Security (1)
Chapter 1 には SSL / TLS を理解するための前提知識である TCP / IP と HTTP の概要について書いてある。
この章では簡単な HTTP クライアントとサーバを実装する。ここでは SSL / TLS の前提部分を理解することにフォーカスしているため、実装する内容にはセキュリティ機能はない。ここで実装した内容をベースに次章以降でセキュリティ機能を追加していく。
コードを掲載する都合上、コメントが長くなってしまうため、Chapter 1 をいくつかのコメントに分けて投稿する。このコメントでは Chapter 1 の HTTP クライアントの骨格部分の実装までを述べる。
SSL / TLS の前提
インターネット通信には Socket が使用されるが、そもそも Socket とは TCP / IP によって確立された接続の参照である。従って、Socket 作成時にはその背後で TCP の 3-way handshake が実施され、Socket 利用時にはデータの順序制御などの恩恵が享受できる。
SSL / TLS は TCP / IP によって確立された接続に対して、追加の handshake を行ってトンネル（暗号化された安全な経路）を作成するように定義されている。つまり Socket の外側で handshake を別途実施する形になる。
HTTP クライアントの実装
まずは HTTP クライアントを実装する。ここで実装するクライアントはごく簡単なもので、引数で渡された URL に対して HTTP の GET リクエストを送信し、レスポンスの内容を標準出力に書き出すだけのツールである。
準備
前準備として Rust の環境を作っておく。以下のコマンドを実行する。
$ cargo new impl_ssl_tls --bin && cd impl_ssl_tls
$ rm src/main.rs
$ mkdir -p src/bin
$ touch src/bin/client.rs
最終的にクライアントとサーバの両方を実装するので、今回は main.rs は使用せず、代わりに client.rs と server.rs の２つのバイナリターゲットを用意する方針でいく。Cargo のマルチバイナリについては ここ に書いてある。ここではさしあたり必要となる client.rs のみを作成している。
バイナリターゲットを認識させるため、Cargo.toml の末尾に以下の内容を追記しておく。
[[bin]]
name = "client"
test = false
bench = false
各バイナリの実行は以下のコマンドで実行できる。
$ cargo run --bin <name> -- <cli-args>
Socket の作成
いよいよ実装開始である。まずは Socket の作成から始める。
Rust では TcpStream::connect(host, port) とすれば、それだけで Socket 作成からホストへの接続まで面倒を見てくれる。C 言語で必要だったディスクリプタ管理などは一切必要ない。[1]
use std::net::TcpStream;
fn main() {
let host = "www.example.com";
let port = 80;
let mut stream = TcpStream::connect((host, port)).unwrap_or_else(|e| {
eprintln!("{}", e);
std::process::exit(-1);
});
println!("Socket created.");
}
上の内容を実行して Sokcet created. と表示されれば Socket での接続に成功している。また host の値を適当な文字列に変更して実行すれば DNS で失敗するのが確認できる。
HTTP リクエストの送信
次に Socket を介して HTTP GET リクエストを送信する。なお、本書で使用しているのは HTTP / 1.1 である。HTTP / 1.1 の仕様は RFC 2616 で定義されている。[2]
HTTP / 1.1 ではリクエストをテキスト形式で送信できる（ HTTP / 2 ではバイナリ形式に変更された）ので、実装は簡単である。以下のような形式の文字列を Socket で送信すればよい：
GET /index.html HTTP/1.1↵
Host: www.example.com↵
Connection: close↵
↵
上記の例は http://www.example.com/index.html にリクエストを送った場合の例である。↵ は改行文字 \r\n を表す。この文字列を送信する処理を、先ほどの main 関数の末尾に書き足せばよい。
以下が追加の実装である。冒頭の use std::io::Write; を忘れるとコンパイルエラーになるので注意する。
use std::io::Write; // need to use stream.write()
use std::net::TcpStream;
fn main() {
// ... 省略 ...
// send HTTP GET request
let path = "/index.html";
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"Connection: close\r\n\r\n",
), path, host);
stream.write(request.as_bytes()).unwrap_or_else(|e| {
eprintln!("Failed to send request: {}", e);
std::process::exit(-1);
});
}
HTTP レスポンスの受信
HTTP リクエストを送信すると、同じ Socket を介してサーバからレスポンスが送信されてくる。今回は単にこれを読み出して標準出力に出力する。
前回と同様に main 関数の末尾に読み出し処理を追記すればよい。冒頭の use 宣言に Read を追加しているので注意すること。
use std::io::{Write, Read}; // need to use stream.read() and stream.write()
use std::net::TcpStream;
fn main() {
// ... 省略 ...
// recieve response
const MAX_CHUNK_SIZE: usize = 1024;
let mut buf: [u8; MAX_CHUNK_SIZE] = [0; MAX_CHUNK_SIZE];
loop {
let read_size = stream.read(&mut buf).unwrap_or_else(|e| {
eprintln!("Failed to recieve request: {}", e);
std::process::exit(-1);
});
if read_size == 0 {
break;
}
print!("{}", std::str::from_utf8(&buf[0..read_size]).unwrap());
}
}
サイズが予測できないレスポンスを取得する際には、レスポンスを Chunk という適当な大きさの単位に分けて、少しずつデータを受信するのが一般的である。ここではレスポンスを 1024 バイトの Chunk に分けて繰り返し取得している。Rust の read() は最後までデータを読み出したら 0 を返す仕様なので、そのタイミングで読み出しループから抜けるようにしている。
これでリクエストの送信とレスポンスの受信ができるようになった。cargo run してリクエストに成功すると、レスポンスの内容が画面に表示される。ここでは http://www.example.com/index.html にリクエストを送信しているので、中身は HTTP ヘッダーと HTML である。
HTTP/1.1 200 OK
Accept-Ranges: bytes
Age: 43484
Cache-Control: max-age=604800
Content-Type: text/html; charset=UTF-8
:
コード中の host や path を変更して、リクエスト先を変えると楽しい。
ツールとしての体裁を整える
ここまでは host や port をハードコーディングしていたが、これをコマンドライン引数で受け取れるようにする。次にような形で使用できるようにしたい：
$ client http://www.example.com/index.html
Rust でコマンドライン引数を読み込むには std::env を使えばよい。
fn main() {
// check command line arguments
let args: Vec<String> = std::env::args().collect();
if args.len() != 2 {
eprintln!("Usage: {} <URL>", args[0]);
std::process::exit(-1);
}
// ... 省略 ...
}
これで引数に指定された http://www.example.com/index.html のような文字列を取得することができるようになった。今度はこの文字列から host・path・port を取り出さなければならない。この URL の例では、それぞれ www.example.com・/index.html・80 である。
本書では簡素な URL のパース処理を実装しているが、今回は既製品があるのでそれを利用する。Rust の url クレート を使えば、今回必要な情報は全て読み取れる。
url クレートは標準ライブラリではないので、Cargo.toml に依存関係を追加する必要がある。
[dependencies]
url = "^2.2.2"
あとは url クレートの仕様を確認しながら実装するだけである。
use std::io::{Write, Read};
use std::net::TcpStream;
use url::Url;
fn main() {
// ... 省略 ...
// parse and validate input URL
let url = Url::parse(&args[1]).unwrap_or_else(|e| {
eprintln!("Malformed URL: {}", e);
std::process::exit(-1);
});
if url.scheme() != "http" {
eprintln!("Unsupported shceme: {}", url.scheme());
std::process::exit(-1);
}
let host = url.host_str().unwrap();
let path = url.path();
let port = url.port_or_known_default().unwrap();
// ... 省略 ...
}
url クレートは有能すぎて色々な形式の URL を読み込めてしまうので、HTTP 以外のスキーマが指定された場合はサポート対象外扱いでエラーとしている。
これで HTTP クライアントの骨格部分の実装は完了である。以下のコマンドで GET リクエストを発行して遊べる。
$ cargo run --bin client -- http://www.example.com/index.html
ここまでの client.rs の全文を掲載しておく。コード整理のために随所に手を加えている。
use std::io::{Write, Read}; // need to use stream.read() and stream.write()
use std::net::TcpStream;
use url::Url;
/// Exit program with printing a message to stderr.
macro_rules! exit_with_message {
($($arg:tt)*) => {
eprintln!($($arg)*);
std::process::exit(-1);
}
}
fn main() {
// check command line arguments
let args: Vec<String> = std::env::args().collect();
if args.len() != 2 {
exit_with_message!("Usage: {} <URL>", args[0]);
}
// parse and validate input URL
let url = Url::parse(&args[1]).unwrap_or_else(|e| {
exit_with_message!("Malformed URL: {}", e);
});
if url.scheme() != "http" {
exit_with_message!("Unsupported shceme: {}", url.scheme());
}
let host = url.host_str().unwrap();
let path = url.path();
let port = url.port_or_known_default().unwrap();
// connect to host
let mut stream = TcpStream::connect((host, port)).unwrap_or_else(|e| {
exit_with_message!("{}", e);
});
// send HTTP GET request
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"Connection: close\r\n\r\n",
), path, host);
stream.write(request.as_bytes()).unwrap_or_else(|e| {
exit_with_message!("Failed to send request: {}", e);
});
// recieve response
read_chunks(&stream, |chunk| {
print!("{}", std::str::from_utf8(chunk).unwrap());
}).unwrap_or_else(|e| {
exit_with_message!("Failed to recieve response: {}", e);
})
}
/// Unwrap Ok value or terminate function with Err as return value
/// i.e. this macro is only for functions that have Result(..) as return type.
/// This macro is to avoid deep nesting by `match` expression.
macro_rules! unwrap_or_return_err {
($e:expr) => {
match $e {
Ok(x) => x,
Err(e) => return Err(e),
}
};
}
/// Maximum size of chunk.
const MAX_CHUNK_SIZE: usize = 1024;
/// Read bytes from a stream chunk by chunk and process it.
fn read_chunks(mut stream: &TcpStream, f: fn(&[u8])) -> std::io::Result<()> {
let mut buf: [u8; MAX_CHUNK_SIZE] = [0; MAX_CHUNK_SIZE];
loop {
let read_size = unwrap_or_return_err!(stream.read(&mut buf));
if read_size == 0 {
return Ok(())
} else {
f(&buf[0..read_size]);
}
}
}
Chapter 1 : Understanding Internet Security (2)
Chapter 1 の続き。HTTP クライアントで認証なしの Proxy サーバを利用できるように改修する。
Proxy のサポートのための対応箇所
Proxy 経由で HTTP リクエストを行う際のフローは以下のようになる：
- HTTP クライアントが Proxy サーバへ Socket 接続する
- HTTP クライアントが Proxy サーバへ HTTP リクエストを発行する
- Proxy サーバが HTTP のリクエスト先を確認する
- Proxy サーバがリクエスト先サーバへ Socket 接続する
- Proxy サーバがリクエスト先サーバへ HTTP リクエストを発行する
- リクエスト先サーバが Proxy サーバへレスポンスを返却する
- Proxy サーバが HTTP クライアントへレスポンスを返却する
ボールド体になっている部分がクライアントの処理に関わる項目である。
上記のうち、明らかに 1 については対応が必要である。具体的には、Proxy を利用する場合、Socket の接続先として Proxy サーバのホストとポートを使用するようにコードを修正する必要がある。
また、それに伴って 2 の HTTP リクエスト発行においても若干の対応が必要になる。これまでは HTTP GET の取得対象に相対パスを指定していたが、Proxy 利用時には Socket の接続先とリクエスト先のホストとポートが異なるため、取得対象を完全な URL で指定する必要がある。例を挙げると、
GET /index.html HTTP/1.1↵
Host: www.example.com↵
Connection: close↵
↵
というリクエストを
GET http://www.example.com/index.html HTTP/1.1↵
Host: www.example.com↵
Connection: close↵
↵
に修正しなければならない。なお、上記の例ではポート指定を省略しているが、リクエスト先のポートが指定されている場合は、それも HTTP GET の取得対象の記述の中に含める必要がある。
7 については Socket から得たレスポンスを標準出力に書き出すだけなので、特に対応すべき箇所はない。
Proxy のテスト環境の準備
最初に Proxy のテストができる環境を整えておく。今回は こちら の Docker コンテナを利用して Proxy サーバを立てることにした。
$ git clone https://github.com/megmogmog1965/squid-for-http-proxy-testing.git
$ cd squid-for-http-proxy-testing
$ docker-compose build
$ docker-compose up -d
Proxy 自体が動作しているかどうかは curl で確認できる。
$ curl http://www.example.com --proxy http://localhost:3128
ちなみに squid-for-http-proxy-testing はデフォルトだと認証なしになる。認証を有効化するには .env を編集する。さしあたり認証なしのままで問題ないので、認証有効化の方法は必要になったタイミングで述べる。
Proxy あり／なしを分岐する
実装を始めるにあたって Proxy あり／なしで処理を適当に分けておく。
fn main() {
// ... 省略 ...
let proxy = Some("http://localhost:3128").map(|arg| {
Url::parse(arg).unwrap_or_else(|e| {
exit_with_message!("Malformed proxy URL: {}", e);
})
});
// request HTTP GET
if proxy.is_some() {
let proxy_url = proxy.unwrap();
request_http_get_with_proxy(&url, &proxy_url).unwrap_or_else(|e| {
exit_with_message!("{}", e);
});
} else {
request_http_get(&url).unwrap_or_else(|e| {
exit_with_message!("{}", e);
});
}
}
fn request_http_get(url: &Url) -> std::io::Result<()> {
// ... 省略 ...
}
fn request_http_get_with_proxy(url: &Url, proxy_url: &Url) -> std::io::Result<()> {
// TODO: implement
}
proxy が利用する Proxy サーバである。Proxy の利用は任意なので、Rust の Option で表現している。ここでは適当な値で仮置きしているが、後ほどコマンドライン引数から取得するように修正する。
request_http_get_with_proxy に Proxy ありの処理を実装していく。request_http_get は Chapter.1 (1) の内容を関数に移しただけのものなので割愛する。
Socket の接続先を Proxy サーバにする
Socket で Proxy サーバに接続するようにする。単純に Chapter.1 (1) の Socket への接続処理で指定していた host・port を Proxy のものに差し替えればよい。
fn request_http_get_with_proxy(url: &Url, proxy_url: &Url) -> std::io::Result<()> {
// connect to proxy
let proxy_host = proxy_url.host_str().unwrap();
let proxy_port = proxy_url.port_or_known_default().unwrap();
let mut stream = unwrap_or_return_err!(
TcpStream::connect((proxy_host, proxy_port))
);
}
HTTP リクエストの取得対象を完全な URL にする
続いて HTTP リクエストの取得対象の記述を修正する。こちらも Chapter.1 (1) での同処理の path を完全な URL に差し替えるだけでよい。
fn request_http_get_with_proxy(url: &Url, proxy_url: &Url) -> std::io::Result<()> {
// ... 省略 ...
// send HTTP GET request
let host = url.host_str().unwrap();
let path = url.as_str(); // need to use the full URL as path when using proxy
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"Connection: close\r\n\r\n",
), path, host);
}
別途 Host タグを記述しているので、path に相対パスを指定しても問題ないような気もするが、絶対パスで指定する方が Proxy フレンドリーらしい。この辺は決め事なので、大人しく従っておくのが吉である。
request_http_get_with_proxy の残りを書く
以降は Chapter.1 (1) と全く同じでよいので、この時点で request_http_get_with_proxy は完成である。以下に全文を掲載しておく。
fn request_http_get_with_proxy(url: &Url, proxy_url: &Url) -> std::io::Result<()> {
// connect to proxy
let proxy_host = proxy_url.host_str().unwrap();
let proxy_port = proxy_url.port_or_known_default().unwrap();
let mut stream = unwrap_or_return_err!(
TcpStream::connect((proxy_host, proxy_port))
);
// send HTTP GET request
let host = url.host_str().unwrap();
let path = url.as_str(); // need to use the full URL as path when using proxy
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"Connection: close\r\n\r\n",
), path, host);
unwrap_or_return_err!(
stream.write(request.as_bytes())
);
// recieve response
read_chunks(&stream, |chunk| {
print!("{}", std::str::from_utf8(chunk).unwrap());
})
}
Docker を立ち上げて cargo run すれば動作確認が行える。なお、Proxy なしの動作に戻したい場合は main 関数の proxy を以下のようにする。
let proxy = None;
Proxy あり／なしで動かしてみて、HTTP レスポンスヘッダーに差分がないかを確認するとよい。私の環境では Proxy ありの場合のみ、以下の Via ヘッダーが付与された。
Via: 1.1 2686d978b868 (squid/4.15)
Proxy をコマンドライン引数で指定する
Proxy を以下のような形式でコマンドライン引数から引き受けられるようにしたい：
$ client http://www.example.com/index.html --proxy http://localhost:3128
これまでのように std::env を使うこともできるが、コマンドライン引数のパース処理を一から実装するのは大変なので、ここでは structopt を導入して対応する。
structopt は標準ライブラリではないので、Cargo.toml に依存関係を追加する必要がある。
[dependencies]
structopt = "^0.3.25"
structop では structopt 属性を宣言した構造体を定義することで、コマンドライン引数のパース処理を自動生成してくれる。structopt の使い方の詳細については こちら を参照のこと。今回必要な構造体は以下のようになる。
use structopt::StructOpt;
/// Struct for CLI arguments.
#[derive(Debug, StructOpt)]
#[structopt(name = "client", about = "Simple CLI HTTP client.")]
struct Opt {
#[structopt(name = "URL")]
pub url: Url,
#[structopt(short, long, help = "Set proxy server URL")]
pub proxy: Option<Url>,
}
メンバー変数には FromStr を実装している型を使用できる。url::Url は FromStr を実装しているので、そのままメンバー変数型として指定できる。
これを使えば、これまで std::env を使って実装していたパース処理が以下のように書ける。
fn main() {
// check command line arguments
let opt = Opt::from_args();
let url = opt.url;
if url.scheme() != "http" {
exit_with_message!("Unsupported shceme: {}", url.scheme());
}
let proxy = opt.proxy;
if proxy.is_some() && proxy.as_ref().unwrap().scheme() != "http" {
exit_with_message!("Unsupported proxy shceme: {}", proxy.unwrap().scheme());
}
// ... 省略 ...
}
かなりスッキリしていてよい感じである。
structopt を使うと --help が自動でサポートされるので、それを利用して構造体がうまく定義できているかを確認するとよい。
$ cargo run --bin client -- --help
Finished dev [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/client --help`
client 0.1.0
Simple CLI HTTP client.
USAGE:
client [OPTIONS] <URL>
FLAGS:
-h, --help Prints help information
-V, --version Prints version information
OPTIONS:
-p, --proxy <proxy> Set proxy server URL
ARGS:
<URL>
以上で認証なし Proxy のサポートは完了である。ここまでのコードの全文は こちら を参照。
dmystkChapter 1 : Understanding Internet Security (3)
Chapter 1 の続き。HTTP クライアントで認証ありの Proxy サーバを利用できるように改修する。
Proxy の認証シーケンス
今回は BASIC 認証を使用する。以下の手順に従えばよい：
- Proxy サーバの URL からユーザ名とパスワードを取得する
- ユーザ名とパスワードを
:で接続した文字列<user>:<password>を BASE64 でエンコードする - HTTP の
Proxy-Authorizationタグで認証方式BASICと共に 2 で得た文字列を送信する
つまり、結果として得られる HTTP リクエストは以下のようになる：
GET http://www.example.com/index.html HTTP/1.1↵
Host: www.example.com↵
Proxy-Authorization: BASIC c3F1aWQ6cGFzc3dvcmQ=↵
Connection: close↵
↵
認証あり Proxy サーバの準備
テスト環境を作成しておく。squid-for-http-proxy-testing の .env を以下のように変更すればよい。
# Squid proxy port.
HTTP_PORT=3128
# Basic authentication.
-BASIC_AUTH_COMMENT_OUT=#### <-- comment out basic authentication settings.
+BASIC_AUTH_COMMENT_OUT=
BASIC_AUTH_USERNAME=squid
BASIC_AUTH_PASSWORD=password
curl を使って認証が有効になっていることを確かめられる。以下のコマンドでは HTTP ヘッダーのみを出力するようにオプション指定している。
$ # 407 Proxy Authentication Required
$ curl -v -s -x http://localhost:3128 http://www.example.com > /dev/null
$ # 200 OK
$ curl -v -s -x http://squid:password@localhost:3128 http://www.example.com > /dev/null
BASE64 の実装
前提として、Rust には base64 クレート があるので、単に BASE64 でエンコードしたいだけであれば自分で実装する必要はない。が、ここでは学習が目的のため、あえて自分の手で再実装する。
自分の手で実装した後に base64 クレートの ソースコード を見ると、BASE64 の仕様やパフォーマンスチューニング等について非常に勉強になるのでオススメ。
BASE64 の概要
BASE64 はバイナリデータを ASCII 文字列に変換するためのエンコード方式である。
その昔、バイナリデータを通信で送付した際、それを ASCII 文字として（非表示可能文字などの考慮をせずに）ログなどに印字しようとすることによる問題が多発したらしい。それを予防するためにバイナリデータを ASCII の表示可能文字に変換するエンコード方式がいくつか検討されたとのこと。BASE64 はそれらの中で最も人気のあるエンコード方式の１つである。
BASE64 では、バイナリデータを 6 bit ずつのチャンクに分解し、6 bit で表される
bytes: 11111111 01010101 00000000 ...
↓
6bits: 111111 110101 010100 000000 ...
↓
ASCII: '/' '1' 'U' 'A' ...
元々 8 bit 単位だったデータを 6 bit 単位に分割するので、2 bit ないし 4 bit の余りが出る可能性がある。余りに対しては不足分の下位ビットを 0 埋めすることで対応する。以下は 8 bit のデータ（余りが 2 bit になる）を処理した場合の例である：
bytes: 11111111
↓
6bits: 111111 110000
↓
ASCII: '/' 'w'
さらにこの変換で出力された ASCII 文字列の長さが 4 の倍数でない場合、4 の倍数になるようにパディング文字 = を挿入する必要がある。[1] １つ上の例では出力された ASCII 文字は２つなので、パディング文字を２つ挿入する必要がある：
ASCII: '/' 'w'
↓
out : '/' 'w' '=' '='
こうして得られた out が BASE64 のエンコード結果となる。なお、デコードの際には単にエンコードの流れを逆に辿っていけばよい。
モジュールの準備
BASE64 の処理は main.rs に書きたくないので、モジュールを分けておく。初のモジュールなので、lib.rs も合わせて準備しておく。
$ touch src/lib.rs
$ touch src/base64.rs
pub mod base64;
バイト列を 6 bit 列に変換する
BASE64 実装のファーストステップとしてバイト列を 6 bit の配列に変換する処理を書いていく。
8 bit と 6 bit の最小公倍数は 24 bit = 3 * 8 bit = 4 * 6 bit なので、３バイトごとに４つの 6 bit が得られる。これを利用して 3 バイトずつ再帰的に処理していく。まずは 3 バイトを 4 つの 6 bit に変換する関数を書く。
fn into_4_bit6(byte1: u8, byte2: u8, byte3: u8) -> (u8, u8, u8, u8) {
let bit32 = u32::from_be_bytes([0, byte1, byte2, byte3]);
( ((bit32 >> 18) & LOW_6_BITS) as u8
, ((bit32 >> 12) & LOW_6_BITS) as u8
, ((bit32 >> 6) & LOW_6_BITS) as u8
, ((bit32 >> 0) & LOW_6_BITS) as u8
)
}
元のバイト列は３バイトの倍数とは限らないので、1 ないし 2 バイトの余りが発生する可能性がある。この余りを処理するための関数も書いておく。
fn into_3_bit6(byte1: u8, byte2: u8) -> (u8, u8, u8) {
let bit32 = u32::from_be_bytes([byte1, byte2, 0, 0]);
( ((bit32 >> 26) & LOW_6_BITS) as u8
, ((bit32 >> 20) & LOW_6_BITS) as u8
, ((bit32 >> 14) & LOW_6_BITS) as u8
)
}
fn into_2_bit6(byte: u8) -> (u8, u8) {
let bit32 = u32::from_be_bytes([byte, 0, 0, 0]);
( ((bit32 >> 26) & LOW_6_BITS) as u8
, ((bit32 >> 20) & LOW_6_BITS) as u8
)
}
これで準備は整ったので、バイト列を再帰的に処理するための変換関数を書いていく。
fn into_bit6s(bytes: &[u8]) -> Vec<u8> {
let mut bit6s = Vec::new();
let mut rest = bytes;
loop {
match rest.len() {
0 => {
return bit6s;
},
1 => {
let (bit6_1, bit6_2) = into_2_bit6(rest[0]);
bit6s.push(bit6_1);
bit6s.push(bit6_2);
return bit6s;
},
2 => {
let (bit6_1, bit6_2, bit6_3) = into_3_bit6(rest[0], rest[1]);
bit6s.push(bit6_1);
bit6s.push(bit6_2);
bit6s.push(bit6_3);
return bit6s;
},
_ => {
let (bit6_1, bit6_2, bit6_3, bit6_4) = into_4_bit6(rest[0], rest[1], rest[2]);
bit6s.push(bit6_1);
bit6s.push(bit6_2);
bit6s.push(bit6_3);
bit6s.push(bit6_4);
},
}
rest = &rest[3..];
}
}
6 bit 列を ASCII 文字列に変換する
6 bit を ASCII 文字に変換するために辞書を用意する。
const BASE64_ENCODE_TABLE : &[u8]= concat!(
"ABCDEFGHIJKLMNOPQRSTUVWXYZ", // 0-25
"abcdefghijklmnopqrstuvwxyz", // 26-51
"01234567889+/", // 52-63
).as_bytes();
これを使って単に BASE64_ENCODE_TABLE[bit6 as usize] とすれば 6 bit に対応する ASCII 文字が得られる。
エンコード処理の実装
ここまでで準備した関数を使えばエンコード処理は簡単に実装できる。
pub fn encode<T: AsRef<[u8]>>(input: T) -> String {
let bit6s = into_bit6s(input.as_ref());
let mut encoded: Vec<_> = bit6s.into_iter()
.map(|bit6| { BASE64_ENCODE_TABLE[bit6 as usize] })
.collect();
while encoded.len() % 4 != 0 {
encoded.push(b'=');
}
String::from_utf8(encoded).unwrap()
}
型引数の中で AsRef トレイトを使用しているが、こうしておくことで [u8] として解釈可能な型全般（＝ AsRef<[u8]> を実装している型）に対応できるようになり、汎用性が上がる。
ASCII 文字列を 6 bit 列に変換する
デコード処理を実装するために、今度は上記の流れを逆に辿っていく。まずは ASCII 文字列を 6 bit 列に変換するための関数を書いていく。
色々と方法は考えられるが、今回はエンコードの際と同様に ASCII 文字から 6 bit への辞書を用意することにした。ただし、入力の中には 6 bit に対応していない不正な文字が混じっている可能性があるため、それらも含めた辞書を用意している。不正な文字には INVALID_VALUE が対応するように実装している。[2]
const BASE64_DECODE_TABLE: [u8; 256] = generate_decode_table_from(
&BASE64_ENCODE_TABLE
);
const INVALID_VALUE: u8 = 0xFF;
const fn generate_decode_table_from(encode_table: &[u8]) -> [u8; 256] {
let mut decode_table = [INVALID_VALUE; 256];
let mut index = 0;
while index < 64 {
decode_table[encode_table[index] as usize] = index as u8;
index += 1;
}
decode_table
}
6 bit 列をバイト列に変換する
エンコードの時と考え方は同じである。まずは 4 つの 6 bit を 3 バイトに変換する関数を用意する。
fn into_3_byte(bit6_1: u8, bit6_2: u8, bit6_3: u8, bit6_4: u8) -> (u8, u8, u8) {
( (bit6_1 << 2) + (bit6_2 >> 4)
, (bit6_2 << 4) + (bit6_3 >> 2)
, (bit6_3 << 6) + (bit6_4 >> 0)
)
}
エンコード文字列にパディングが含まれている場合、格納されている 6 bit が 4n + 3 ないし 4n + 2 個になるため、剰余分を処理するための関数も用意しておく。
fn into_2_byte(bit6_1: u8, bit6_2: u8, bit6_3: u8) -> (u8, u8) {
( (bit6_1 << 2) + (bit6_2 >> 4)
, (bit6_2 << 4) + (bit6_3 >> 2)
)
}
fn into_1_byte(bit6_1: u8, bit6_2: u8) -> u8 {
(bit6_1 << 2) + (bit6_2 >> 4)
}
あとは変換のための関数を書くだけである。
fn into_bytes(bit6s: &[u8]) -> Vec<u8> {
if bit6s.len() % 4 == 1 {
// パディングが３つ付与されている場合にあたるがエンコードの規則上それはあり得ない
panic!("Invalid 6-bits length. {}:{}", file!(), line!());
}
let mut bytes = Vec::new();
let mut rest = bit6s;
loop {
match rest.len() {
0 => {
return bytes;
},
2 => {
let byte = into_1_byte(rest[0], rest[1]);
bytes.push(byte);
return bytes;
},
3 => {
let (byte1, byte2) = into_2_byte(rest[0], rest[1], rest[2]);
bytes.push(byte1);
bytes.push(byte2);
return bytes;
},
_ => {
let (byte1, byte2, byte3) = into_3_byte(rest[0], rest[1], rest[2], rest[3]);
bytes.push(byte1);
bytes.push(byte2);
bytes.push(byte3);
},
}
rest = &rest[4..];
}
}
一応 6 bit 列の長さを 4 で割った余りが 1 の場合にパニックしているが、後ほど関数を呼ぶ側でもしっかりバリデーションすることで該当ケースには入らないように制御する。
入力のバリデーション
エンコードでは特に必要なかったが、デコード時はいくつかのエラーケースがあるため、バリデーションが必要となる。確認項目は大きく以下の４つである：
- 入力の長さが 4 の倍数になっているか
- BASE64 の定める ASCII 文字以外が含まれていないか
- 不正なパディングが挿入されていないか
- パディングが指定されている場合に最後の 6 bit の下位ビットはゼロ埋めされているか
まずは上記エラーに対応する列挙型を定義する。今回は こちら から拝借した。
#[derive(Debug)]
pub enum DecodeError {
InvalidLength,
InvalidByte(usize, u8),
InvalidLastSymbol(usize, u8),
}
InvalidByte が先ほど挙げた確認項目の 2 と 3 の両方を受け持つため、定義項目は合計３つになっている。
あとは愚直に検証処理を書いていく。
fn validate_decoding_target(input: &[u8]) -> Result<(), DecodeError> {
// インデックス範囲オーバーが怖いので空の場合は先に処理しておく
if input.is_empty() {
return Ok(());
}
// 入力の長さが４の倍数であることを確認する
if input.len() % 4 != 0 {
return Err(DecodeError::InvalidLength);
}
// 適切な ASCII 文字であることおよび不正パディングがないことを確認する
let padding = count_padding(input);
let invalid_value = input[..input.len()-padding].into_iter()
.zip(0..input.len())
.filter(|(value, _)| { BASE64_DECODE_TABLE[**value as usize] == INVALID_VALUE })
.nth(0);
if let Some((value, index)) = invalid_value {
return Err(DecodeError::InvalidByte(index, *value));
}
// パディングがある場合に最後の要素の下位ビットがゼロ埋めされていることを確認する
let last_non_pad_index = input.len() - padding - 1;
let last_non_pad_elem = input[last_non_pad_index];
let mask = match padding {
2 => 0b0000_1111,
1 => 0b0000_0011,
_ => 0b0000_0000,
};
if BASE64_DECODE_TABLE[last_non_pad_elem as usize] & mask != 0 {
return Err(DecodeError::InvalidLastSymbol(last_non_pad_index, last_non_pad_elem));
}
Ok(())
}
fn count_padding(input: &[u8]) -> usize {
let (last, last2) = (input[input.len()-1], input[input.len()-2]);
if last == PADDING && last2 == PADDING {
2
} else if last == PADDING {
1
} else {
0
}
}
デコード処理の実装
ここまでで必要な部品は揃ったので、デコード処理を書いていく。バリデーション → 6 bit 列に変換 → バイト列に変換 と順次処理していけば OK 。
pub fn decode<T: AsRef<[u8]>>(input: T) -> Result<Vec<u8>, DecodeError> {
let input = input.as_ref();
if input.is_empty() {
return Ok(vec!());
}
if let Err(e) = validate_decoding_target(input) {
return Err(e);
}
let padding = count_padding(input);
let bit6s: Vec<_> = input[..input.len()-padding].iter()
.map(|symbol| { BASE64_DECODE_TABLE[*symbol as usize] })
.collect();
let decoded = into_bytes(bit6s.as_ref());
Ok(decoded)
}
BASE64 については以上で完了である。テストを書いて色々試してみると楽しい。
Proxy の認証機能の実装
BASE64 を実装してようやく準備が整ったので、Proxy サーバの認証処理の追加を行っていく。
修正方針
Proxy の認証を行うには HTTP リクエストヘッダーに Proxy-Authorization タグを追加する必要がある。これは Proxy の URL にユーザとパスワードが指定された場合にのみ付与したいタグなので、Proxy へのリクエスト作成処理の部分を修正する必要がある。今回は request_http_get_with_proxy の該当箇所を以下のように修正することを考える：
let host = url.host_str().unwrap();
let path = url.as_str();
let auth = /* get from proxy URL*/;
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"{}",
"Connection: close\r\n\r\n",
), path, host, auth);
auth には Proxy-Authorization タグの内容全般が含まれることになるが、これを直接関数で返すようにするのはハードコードすぎてイマイチな感じがする。なので、認証情報のための構造体を用意して、そこからタグに変換できるようにする方針を採る。
Proxy 認証のための構造体の準備
HTTP の Proxy-Authorization タグは認証方式と認証文字列の２つの情報を要求するので、それに合わせてデータ構造を構築する。
struct ProxyAuth {
method: &'static str,
credentials: String,
}
method には列挙型を使う方法もあるが、今のところは固定の文字列 "BASIC" しか使わないので静的文字列にしておく。
BASIC 認証の規則に従って、必要なメソッドを定義しておく。
impl ProxyAuth {
pub fn basic(username: &str, password: &str) -> ProxyAuth {
let credentials = impl_ssl_tls::base64::encode(
format!("{}:{}", username, password)
);
ProxyAuth { method: "BASIC", credentials }
}
pub fn as_tag(&self) -> String {
format!("Proxy-Authorization: {} {}\r\n", self.method, self.credentials)
}
}
Proxy 認証の取得処理
構造体が準備できたので、修正方針の項で /* get from proxy URL */ としていた部分を書いていく。
基本的には Url からユーザ名とパスワード取得すればよいだけだが、１点だけコーナーケースへの対応が必要である。Proxy の URL に http://user@proxy.com のようにパスワードの記述なしでユーザだけを指定される場合がある。パスワードなしで認証する手段はないので、この場合はエラーとする。[3]
以下が認証取得処理の実装である。
fn get_proxy_auth(proxy: &Url) -> Result<Option<ProxyAuth>> {
let user = proxy.username();
let pass = proxy.password();
// ユーザ名のみの指定は許さない
if !user.is_empty() && pass.is_none() {
// return something error
return Err(Error::new(ErrorKind::Other,
format!("Invalid proxy credentials: Expected password in {}", proxy)
));
}
// 認証なし
if user.is_empty() {
return Ok(None);
}
Ok(Some(ProxyAuth::basic(user, pass.unwrap())))
}
リクエスト作成処理の修正
これで認証情報が取得できるようになったので、後は修正方針の項で示したリクエスト作成処理を正式な形に修正すれば完了である。
let host = url.host_str().unwrap();
let path = url.as_str(); // need to use the full URL when using proxy
let auth = unwrap_or_return_err!(get_proxy_auth(&proxy_url))
.map(|auth| { auth.as_tag() })
.unwrap_or(String::new());
let request = format!(concat!(
"GET {} HTTP/1.1\r\n",
"Host: {}\r\n",
"{}",
"Connection: close\r\n\r\n",
), path, host, auth);
以上で認証ありの Proxy サーバへの対応は完了である。Docker を立ち上げて以下のコマンドを実行すれば動作確認できる。
$ cargo run --bin client -- -p http://squid:password@localhost:3128 http://www.example.com
ここまでのコード全文は こちら を参照。
-
変換後の文字列を 4 の倍数の長さにするのは、8 bit と 6 bit の最小公倍数が 24 bit = 4 * 6 bit であることに由来すると思われる。しかし、パディングを挿入することによる実際上のメリットはほとんどない。本書には「パディング文字を確認することでデコード結果のバイト数がわかる」と書かれているが、実際にはパディング文字がなくともバイト数は計算可能である。Stack Overflow にはエンコード済み文字列を結合する際に有用とあるが、そのようなユースケースがいつ必要となるのかはわからない。また RFC にもパディングの目的は記載されていないらしい。そのような状況のため、実装によってはパディング文字の仕様を丸ごと無視しているケースもあるとのとこ。 ↩︎
-
対応する値がない可能性を表現するためには
Option型の使用が正道という気もするが、ここでは base64 クレートの ソースコード に倣って固定値にしている。少し調べてみたところ、Stack Overflow に「列挙型にはメモリのオーバーヘッドがある」とあるので、これを嫌った結果と思われる。 ↩︎ -
念のため BASIC 認証を定めた RFC 7617 も確認してみたが、パスワードがない場合についての記述は見当たらなかった。 ↩︎
dmystkChapter 1 : Understanding Internet Security (4)
Chapter 1 の続き。HTTP サーバを実装する。また、実装したサーバを Heroku にデプロイする。
Heroku にデプロイするのは、Proxy 経由での確認を行う際、Proxy サーバと HTTP サーバのドメインが一致している（＝両方ともローカルホスト）と、Proxy がうまく接続を捌いてくれないためである。なので、HTTP サーバは Heroku 上で動かせるようにしておく。
実装する HTTP サーバの概要
実装するのは GET リクエストだけに対応した簡単な HTTP サーバである。GET 以外のメソッドがリクエストされた場合は 501 Not Implemented を返す。
基本的に SSL / TLS の学習に必要な最低限の機能しか実装しない。
事前準備
実装のためのバイナリターゲットを用意しておく。
$ touch src/bin/server.rs
[[bin]]
name = "server"
test = false
bench = false
HTTP サーバの実装
例によって、本書では C 言語での古式ゆかしい socket・bind・listen・accept を使って実装しているが、Rust での HTTP サーバ実装はもっと簡単である。基本的に こちら で説明されている手順に従えば実装できる。
use std::net::{TcpStream, TcpListener, SocketAddrV4, Ipv4Addr};
const DEFAULT_PORT: u16 = 7878; // ポート番号は適当
fn main() {
let listener = TcpListener::bind(
SocketAddrV4::new(Ipv4Addr::LOCALHOST, DEFAULT_PORT)
).unwrap();
for stream in listener.incoming() {
match stream {
Ok(stream) => {
handle_connection(stream);
},
Err(e) => {
eprintln!("Couldn't get client: {}", e);
},
}
}
}
fn handle_connection(mut stream: TcpStream) {
// TODO: implement here
}
TcpListener::bind() をコールすると裏で socket・bind・listen の内容をまとめて処理してくれる。また listener.incoming() では accept を使ったループに当たる内容のイテレータを作成して渡してくれる。あとは handle_connection の中身を実装すれば完成である。とても楽。
handle_connection は以下のように実装してみた。GET 対象のパスどころかプロトコルバージョンの確認すらしていないが、今回の目的にとってはこれで十分である。
use std::io::{Write, Read};
use std::cmp::Ordering;
const MAX_CHUNK_SIZE: usize = 1024;
fn handle_connection(mut stream: TcpStream) {
let mut buffer = [0; MAX_CHUNK_SIZE];
stream.read(&mut buffer).unwrap();
println!("{}", String::from_utf8_lossy(&buffer[..]));
let response = match buffer[..4].cmp(b"GET ") {
Ordering::Equal => {
let contents = include_str!("../../res/index.html");
format!("HTTP/1.1 200 OK\r\n\r\n{}", contents)
},
_ => {
let contents = include_str!("../../res/501.html");
format!("HTTP/1.1 501 NOT IMPLEMENTED\r\n\r\n{}", contents)
},
};
stream.write(response.as_bytes()).unwrap();
stream.flush().unwrap();
}
それぞれのレスポンスで返す HTML ファイルとして res/index.html と res/501.html を参照しているので、以下のコマンドで生成しておく。各 HTML ファイルの中身は適当でよいが、一応掲載しておく。
$ mkdir res
$ touch res/index.html
$ touch res/501.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Hello!</title>
</head>
<body>
<h1>Hello!</h1>
<p>Hi from Server</p>
</body>
</html>
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>501 Not Implemented</title>
</head>
<body>
<h1>501 Not Implemented</h1>
</body>
</html>
fs クレート を使用せずに include_str!() で HTML ファイルを読み込んでいるが、include_str!() でファイルを読み込むと、バイナリビルド時、読み込まれたファイルは文字列としてバイナリの中に組み込まれる。後ほど Heroku にデプロイする際、全てがバイナリ１つにまとまっていた方が簡単なため、今回はこのような実装にしている。[1]
以下のコマンドで HTTP サーバを実行できる。ブラウザなどから http://localhost:7878 にアクセスすると res/index.html の中身が表示される。
$ cargo run --bin server
別ターミナルから curl を実行すれば GET 以外のメソッドでエラーが返されることも確認できる。data オプションを付与するとリクエストが POST で送信される。
$ curl --data "something-to-send" http://localhost:7878
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>501 Not Implemented</title>
</head>
<body>
<h1>501 Not Implemented</h1>
</body>
</html>
Heroku への対応
今後確認を行なっていくにあたり、Proxy サーバと HTTP サーバが両方ともローカルホストで動作していると都合が悪いことがあるため、HTTP サーバを Heroku にデプロイして動作させる。
Heroku のアカウント作成および Heroku CLI のインストールは実施されている前提とする。
Socket 設定の修正
Heroku へのデプロイの前にコードを少しだけ修正する。修正するのは以下の箇所である：
let listener = TcpListener::bind(
SocketAddrV4::new(Ipv4Addr::LOCALHOST, DEFAULT_PORT)
).unwrap();
Ipv4Addr::LOCALHOST を指定しているが、これはローカルでの実行を想定しているためである。インターネットからの要求を受け付けるためには Ipv4Addr::UNSPECIFIED を指定する必要がある。[2]
また、ポート番号を固定値で指定しているが、Heroku では環境変数 PORT で渡される [3] ので、それを読み取って設定する必要がある。
修正後のコードは以下のようになる。
const PORT_KEY: &'static str = "PORT";
fn main() {
let port = std::env::var(PORT_KEY)
.map(|port| { port.parse().unwrap() })
.unwrap_or(DEFAULT_PORT);
let listener = TcpListener::bind(
SocketAddrV4::new(Ipv4Addr::UNSPECIFIED, port)
).unwrap();
// ... 省略 ...
}
Heroku へデプロイする
Heroku CLI を使用してアプリの設定を行う。Git に結びつくので、必要であれば git init を実行しておく。
$ heroku login
$ heroku create -a (your-app-name)
$ heroku git:remote -a (your-app-name)
$ heroku buildpacks:set emk/rust
Procfile を作成する。リリースビルドで生成されるバイナリの場所を指定すれば OK 。
$ touch Procfile
web: ./target/release/server
リモートリポジトリの heroku に git push すればデプロイ完了である。
$ git push heroku main
http://(your-app-name).herokuapp.com にアクセスすれば動作確認できる。
以上で Chapter 1 : Understanding Internet Security は完了である。ここまでのコード全文は こちら を参照。Chapter 2 以降では、ここまでで実装したコードをベースにセキュリティ機能を実装していく。
dmystkChapter 2 : Protecting Against Eavesdroppers (1)
Chapter 2 では対称鍵暗号を使用したセキュリティ機能を実装する。具体的には、ブロック暗号アルゴリズムとして DES・AES を、ストリーム暗号アルゴリズムとして RC4 を実装する。
承前
SSL における暗号化の役割は、「攻撃者が攻撃成功までにかかる時間を、送信内容が価値を失うのに十分なだけ引き延ばす」ことにある。これは以下の内容による：
攻撃者の代表的な手口の１つにブルートフォース攻撃というものがある。送信内容の一部を推定し、それに一致する文字列が現れるまで考えうる全ての鍵のパターンを試してみるという攻撃手法である。
例えば、HTTP リクエストであれば、送信される内容は GET で始まる可能性が高い。従って、適当な鍵を使用して復号をかけ、得られた文字列の冒頭に GET が現れるまで繰り返せば、いずれは攻撃者が正しい鍵に行き当たり、内容を解読されてしまう。
ブルートフォース攻撃に対抗するには、鍵のサイズを十分に大きくすることで、攻撃者が全てのパターンの鍵を試すのにかかる時間を引き延ばす以外の方法はない。従って、SSL の暗号化の目的もこれに準ずることになる。
暗号化の方式には公開鍵暗号と対称鍵暗号の２つがあるが、Chapter 2 では後者を扱う。前者は Chapter 3 で扱うことになる。
余談だが、本書には Chapter 2 が最も技術的に濃密であると注意書きされている。怖い。
ブロック暗号
太古の原始的な暗号の手法は、ある文字を別の文字に置き換えることで暗号を作るというものであった。例えば、太古の代表的な換字式暗号であるシーザー暗号は、以下の対応表に示すように、アルファベットを３文字シフトすることで暗号を作る。
ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓
DEFGHIJKLMNOPQRSTUVWXYZABC
この対応表に基づいて、実際に HELLO WORLD を暗号化してみると以下のようになる。実際はスペースを省略する場合が多いが、ここではわかりやすさのために残している。
HELLO WORLD
↓
KHOOR ZRUOG
シーザー暗号は平文の１文字に対して別の１文字を対応させる暗号化方法である。これは非常にシンプルで理解しやすいが、同時に攻撃者にとっては解読が容易な暗号である。
現代の暗号では、より解読を困難にするために、複数の文字を一度に処理する。特に固定長のデータを一度に処理する暗号化方式をブロック暗号アルゴリズムと呼ぶ。これは対称鍵暗号の最も一般的な用途の１つである。
DES の実装
ブロック暗号への理解を深めるため、まずは DES (Data Encryption Standard) を実装する。DES は既に安全な暗号とは見做されていないが、対称鍵暗号の学習のためのよい開始地点となる。
DES の仕様は こちら で定められている。DES は入力データを 8 バイト単位で処理するブロック暗号であり、鍵も同様に 8 バイトである。
現代の共通鍵暗号の多くがそうであるように、DES は XOR 演算に多くを依存している。XOR は同じ操作で変換と逆変換を行うことができるため、暗号化においては非常に有益である。以下に例を示す：
0011 xor 0101 → 0110
0110 xor 0101 → 0011
0011 を 0101 で XOR した結果は 0110 となるが、その 0110 に対して同様に 0101 で XOR をとると、元の値 0011 が得られる。これは 0101 を鍵として同じ操作を行うことで平文と暗号文を得ていることに相当する。
Initial Permutation
DES では最初に Initial Permutation と呼ばれるビットの置換処理（並べ替え）を行うことになっている。この処理は暗号の安全性には寄与せず、処理を行う目的も曖昧らしい。本書には特定のハードウェアへの最適化のためではないかと書かれている。
処理概要
Initial Permutation では、入力データの８つのバイトそれぞれから１ビットずつを取得して１つのバイトを作り、これを８回繰り返す。１回目では上から２番目のビットを取得する。以下の * になっている部分のビットを集めて１バイトを作るイメージである。
byte1: 0bX*XX_XXXX
byte2: 0bX*XX_XXXX
byte3: 0bX*XX_XXXX
byte4: 0bX*XX_XXXX
byte5: 0bX*XX_XXXX
byte6: 0bX*XX_XXXX
byte7: 0bX*XX_XXXX
byte8: 0bX*XX_XXXX
集めた * を byte8 から順番に byte1 まで並べることで１つのバイトを作る。つまり、最上位ビットは byte8 の * になり、最下位ビットは byte1 の * になる。
これを上から２番目、４番目、６番目、と偶数４つを先に処理し、８番目に到達したら１番目に戻って、同様に奇数４つを処理していく。７番目のビットまで到達したら完了である。
実装の準備
今回はビット演算を多用するので、そのためのユーティリティと DES の実装の２つのモジュールを用意する。ビット演算のユーティリティはクレート内部でしか使用しないので、lib.rs の記述に pub を付与する必要はない。
$ touch src/des.rs
$ touch src/bit.rs
pub mod des;
mod bit;
ビットの取得・更新処理の実装
まずはビット演算ユーティリティの実装から始める。指定した位置のビットの値を取得したり更新したりできると便利なので、そのための関数を bit モジュールに用意しておく。データ型のバイト長に囚われたくないので、u8 の配列をターゲットに実装する。
// 引数 bytes の一番最初のバイトを最上位バイトと見做す。
// 引数 position は最上位ビットを 0 とするビット番号とする。
pub fn get_bit(bytes: &[u8], position: usize) -> u8 {
let target = bytes[position / 8];
let rem = position % 8;
(target & (0b1000_0000 >> rem)) >> (7 - rem)
}
pub fn set_bit(bytes: &mut [u8], position: usize, value: u8) {
let index = position / 8;
let rem = position % 8;
if value == 0 {
bytes[index] = bytes[index] & !(0b1000_0000 >> rem);
} else {
bytes[index] = bytes[index] | (0b1000_0000 >> rem);
}
}
set_bit では 0 以外の値が来たらビットに 1 を設定するようにしているが、引数が厳密に 1 であるかどうかをチェックするメリットがないのでそうしているだけである。特に深い意味はない。
ビットの置換処理の実装
先ほど実装した関数を利用してビット単位の置換関数を実装する。
pub fn permute(input: &[u8], output: &mut [u8], perm: &[usize]) {
for i in 0..perm.len() {
set_bit(output, i, get_bit(input, perm[i]));
}
}
ここでは引数 perm で置換の内容を表すテーブルを受け取るように実装している。以下のテストコードが使い方のイメージを掴む役に立つかもしれない。
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_permute_reverse() {
let input = [ 0b1010_1010, 0b0101_0101, 0b1111_0000 ];
let mut output = [0; 3];
let reverse_perm = [
23, 22, 21, 20, 19, 18, 17, 16,
15, 14, 13, 12, 11, 10, 9, 8,
7, 6, 5, 4, 3, 2, 1, 0,
];
permute(&input, &mut output, &reverse_perm);
assert_eq!(output, [ 0b0000_1111, 0b1010_1010, 0b0101_0101 ])
}
}
reverse_perm が置換のテーブルである。input が合計３バイトなので 0-23 までのビットが存在するが、ここでは出力が入力のビットと逆順に（最上位ビットが最下位ビットに、最下位ビットが最上位ビットに）なるように置換を行なっている。
Initial Permutation の実装
これで置換処理は実装できたので、あとは Initial Permutation 用のテーブルを用意してやればよい。
/// Initial Permutation Table
const ip_table: [usize; 64] = [
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7,
56, 48, 40, 32, 24, 16, 8, 0,
58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
];
これで以下のように書けば Initial Permutation が行える。
crate::bit::permute(input, output, &ip_table);
Key Schedule
DES では「ラウンド」と呼ばれる一連の処理を繰り返し適用することで暗号を生成する。このような形式の暗号アルゴリズムを積暗号（ Product Cipher ）という。各ラウンドでは鍵から生成されたラウンド鍵が使用される。このラウンド鍵生成のためのアルゴリズムのことを一般に Key Schedule という。[1]
DES は 16 のラウンドからなり、16 個のラウンド鍵を生成する必要がある。ラウンド鍵は全て 48 ビットである。ラウンド鍵の生成は以下の手順で行われる：
- 鍵から 28 ビットのペアを生成する
- 28 ビットのペアそれぞれを左に 1 ないし 2 ビット分ローテートする
- ローテート済みのペアから 48 ビットのラウンド鍵を生成する
- 16 ラウンド全てのラウンド鍵が得られるまで 2 に戻って繰り返す
以下、それぞれのステップの詳細について述べる
鍵から 28 ビットのペアを生成する
最初に 8 バイトの鍵から 7 バイト分を取り出し、それを 28 ビットのペアに分ける。Initial Permutation と同様に、こちらも 8 バイトの各バイトから 1 ビットずつ取り出すことでバイトを構成していくが、各バイトの最下位ビットは使用しない。[2] また、Initial Permutation と異なり、ビットは上から１番目、２番目、３番目と取り出していく。さらに４番目を取り出す際には 4 ビット分しか取り出さない。つまり、以下の図における * の部分までしか使用しない。
byte1: 0b****_XXXX
byte2: 0b****_XXXX
byte3: 0b****_XXXX
byte4: 0b****_XXXX
byte5: 0b***X_XXXX
byte6: 0b***X_XXXX
byte7: 0b***X_XXXX
byte8: 0b***X_XXXX
４番目の半分まで取り出したら、今度は逆に７番目、６番目、５番目と取り出していき、最後に４番目の下半分を取り出す。以下の図の * の部分が後半で取得する 28 ビットである。
byte1: 0bXXXX_***X
byte2: 0bXXXX_***X
byte3: 0bXXXX_***X
byte4: 0bXXXX_***X
byte5: 0bXXX*_***X
byte6: 0bXXX*_***X
byte7: 0bXXX*_***X
byte8: 0bXXX*_***X
上記の操作を置換のテーブルで表現すると以下のようになる。
/// Permuted Choice 1 Table
const pc1_table: [usize; 56] = [
// 第１の 28 ビット
56, 48, 40, 32, 24, 16, 8, 0,
57, 49, 41, 33, 25, 17, 9, 1,
58, 50, 42, 34, 26, 18, 10, 2,
59, 51, 43, 35,
// 第２の 28 ビット
62, 54, 46, 38, 30, 22, 14, 6,
61, 53, 45, 37, 29, 21, 13, 5,
60, 52, 44, 36, 28, 20, 12, 4,
27, 19, 11, 3,
];
28 ビットのペアそれぞれを左に 1 ないし 2 ビット分ローテートする
掲題の通りだが、ローテートするビット数はラウンド数に依存する。1・2・9・16 ラウンドでは 1 ビットで、それ以外は 2 ビットである。
実装では 1 ビットのローテート用の関数のみを用意する。
/// 引数は7バイト＝28ビットのペアの想定
fn rotate_left(target: &mut [u8]) {
let carry_left = (target[0] & 0b1000_0000) >> 3;
let carry_right = (target[3] & 0b0000_1000) >> 3;
target[0] = (target[0] << 1) | (target[1] >> 7);
target[1] = (target[1] << 1) | (target[2] >> 7);
target[2] = (target[2] << 1) | (target[3] >> 7);
target[3] = (((target[3] << 1) | (target[4] >> 7)) & !0b0001_0000) | carry_left;
target[4] = (target[4] << 1) | (target[5] >> 7);
target[5] = (target[5] << 1) | (target[6] >> 7);
target[6] = (target[6] << 1) | carry_right;
}
28 ビットのペアそれぞれをローテートする必要があるので、target[3] の処理が少し複雑になっている。
ローテート済みのペアから 48 ビットのラウンド鍵を生成する
基底のビット配列に則ってローテート済みの 28 ビットのペアから 48 ビットのラウンド鍵を生成する必要がある。28 ビットのペアを結合して得られる 7 バイトの配列に以下の置換テーブルを適用すればよい：
/// Permuted Choice 2 Table
const pc2_table: [usize; 48] = [
13, 16, 10, 23, 0, 4,
2, 27, 14, 5, 20, 9,
22, 18, 11, 3, 25, 7,
15, 6, 26, 19, 12, 1,
40, 51, 30, 36, 46, 54,
29, 39, 50, 44, 32, 47,
43, 48, 38, 55, 33, 52,
45, 41, 49, 35, 28, 31,
];
以上でラウンド鍵の生成に必要な関数は揃った。
Expansion Function
DES の各ラウンドでは入力となる 8 バイトの下位 4 バイトとラウンド鍵で XOR 演算を行う。しかしながら、ラウンド鍵は 48 ビットなので、入力の下位 4 バイトを 48 ビットに拡張して XOR を行う。
拡張では以下のテーブルを参照する。
const expansion_table: [usize; 48] = [
31, 0, 1, 2, 3, 4,
3, 4, 5, 6, 7, 8,
7, 8, 9, 10, 11, 12,
11, 12, 13, 14, 15, 16,
15, 16, 17, 18, 19, 20,
19, 20, 21, 22, 23, 24,
23, 24, 25, 26, 27, 28,
27, 28, 29, 30, 31, 0,
];
拡張は 4 バイトから 8 つの 6 ビットを生成することで実現される。各 6 ビットは上位および下位の 2 ビットが他の 6 ビットと重なるように生成される。
Substitution-Boxes (S-Box)
（工事中）