🦀

RustでTOTP(Time-based One-Time Password)を、RFCだけ見て原理原則から実装する

commits13 min read

先に成果物はこちらです。

https://github.com/ulwlu/rust-totp

経緯:ひょんなきっかけで TOTP の実装機会があった。RFC 文書からは 0→1 でコード実装した経験ないので、せっかくなので RFC だけ見て Rust で実装する事にした。

概要:OATH や 2FA で使われている、TOTP(Time-based One-Time Password)アルゴリズムの概念と実装をメモ。RFC6238準拠。

単語

  • TOTP: 2011 年に HOTP の拡張として誕生。RFC6238 準拠。「ユーザー&サーバー間で共有されてる秘密 token、時間情報」をもとに OTP を生成する。HOTP と違って時間情報をもとにするからブルートフォースに対する防御力は強い。勿論キーロガーなどされたら即死。またオンラインと通信しながら時刻を調整できる正確なクロックが内蔵されていれば問題ないが、そうでないサーバーの場合もありえるので、RFC では許容幅について言及しており、一度その許容幅を超えた場合は次回以降ユーザー毎にその幅を記録する方法などが提案されている。
  • HOTP: 2005 年に誕生。RFC4226準拠。「ユーザー&サーバー間で共有されてる秘密 token、認証回数」をもとに OTP を生成する。TOTP と比較して決定的な致命点があり、OTP が使用されない限り更新されないためブルートフォースアタックの危険性がある(当然ネットワーク層で防御するとしても)。あとユーザー&サーバー間でカウントが同期してなければならないにも関わらず当然連打などによりカウントがずれる事があり、その対策として RFC にあげられている再同期方法(link は stackexchange)が更にブルートフォースアタックのリスクをあげているんじゃないかと思われる。一応まだ Google Authenticator などでも選べるオプションなので現役だが、色々セキュリティ系記事読む限 TOTP の方が推奨されてる。
  • OTP: TOTP や HOTP で生成される One Time Password そのものを指す。最小 6 桁(RFC4226 準拠)
  • hashlib: hash アルゴリズム。TOTP のデフォルトは sha1 なのだが、google などでは sha512 が用いられているらしい。単に文字列を hash 化するだけならこれだけで作れるのだが、メッセージ付きに今回はしたいので(token、時間情報)hmac に入れる。
  • hmac: 指定した hash アルゴリズムを使ってメッセージ認証するライブラリ。RFC2104 準拠。

要件

terminology のMUST, MUST NOT, REQUIRED あたりを検索して今回の実装に関係しそうなものをメモしていきます。

https://tools.ietf.org/html/rfc6238
  • The prover (e.g., token, soft token) and verifier (authentication or validation server) MUST know or be able to derive the current Unix time (i.e., the number of seconds elapsed since midnight UTC of January 1, 1970) for OTP generation →   unixtime は鯖の GMT に合わせる方針でいく
  • The prover and verifier MUST either share the same secret or the knowledge of a secret transformation to generate a shared secret. → 本来アプリなら QR コードで渡したりするのだが、今回は試験用なので引数で適当な文字列渡せるようにして、鯖側は test で入力するようにする
  • The prover and verifier MUST use the same time-step value X →  今回はデフォルトの 30 秒でやります。
  • The implementation of this algorithm MUST support a time value T larger than a 32-bit integer when it is beyond the year 2038. →  はい。
  • Implementations MUST extract a 6-digit code at a minimum and possibly 7 and 8-digit code. Depending on security requirements, Digit = 7 or more SHOULD be considered in order to extract a longer HOTP value  →  はい。(これは RFC4226 HOTP の方の要件)

どう作る?

上から読んでいきつつ理解します。

  • we define TOTP as TOTP = HOTP(K, T), where T is an integer and represents the number of time steps between the initial counter time T0 and the current Unix time → HOTP アルゴリズムのカウンター部分を時間のものに変えたのが TOTP
  • The definition of HMAC requires a cryptographic hash function, which we denote by H, and a secret key K. → これは RFC2104 の説明。K は秘密鍵。今回は適当に決める。
  • More specifically, T = (Current Unix time - T0) / X
  • T0 is the Unix time to start counting time steps (default value is 0, i.e., the Unix epoch)
  • X represents the time step in seconds (default value X = 30 seconds) → T の値の算出は簡単にできそう。
  • Due to network latency, the gap (as measured by T, that is, the number of time steps since T0) between the time that the OTP was generated and the time that the OTP arrives at the receiving system may be large.
  • We RECOMMEND that at most one time step is allowed as the network delay → 1 回分の遅延を許容しています。冒頭でも書きましたが time step window を伸ばすほどセキュリティ上脆弱性を大きくなっていきます。今回は加味しません。

HOTP の拡張としての TOTP 側の考慮はある程度わかったので、次に RFC4226 を見て HOTP アルゴリズムの実装方針を見ていきます

https://tools.ietf.org/html/rfc4226
  • A string always means a binary string, meaning a sequence of zeros and ones.
  • T: throttling parameter: the server will refuse connections from a user after T unsuccessful authentication attempts これは今回無視します
  • s: resynchronization parameter: the server will attempt to verify a received authenticator across s consecutive counter values → これは今回無視します
  • As the output of the HMAC-SHA-1 calculation is 160 bits, we must truncate this value to something that can be easily entered by a user →  単純に hmac でメッセ認証するだけでなく、truncate しなければならない。
We can describe the operations in 3 distinct steps:

   Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C)  // HS
   is a 20-byte string

   Step 2: Generate a 4-byte string (Dynamic Truncation)
   Let Sbits = DT(HS)   //  DT, defined below,
                        //  returns a 31-bit string

   Step 3: Compute an HOTP value
   Let Snum  = StToNum(Sbits)   // Convert S to a number in
                                    0...2^{31}-1
   Return D = Snum mod 10^Digit //  D is a number in the range
                                    0...10^{Digit}-1
DT(String) // String = String[0]...String[19]
     Let OffsetBits be the low-order 4 bits of String[19]
     Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
     Let P = String[OffSet]...String[OffSet+3]
     Return the Last 31 bits of P
  • ↓   ↓
  • ①HMAC 結果の 20byte 値から、動的バイナリ変換して下位 4bit を取得。
  • ②① をオフセットとして、更に HMAC 結果から offset bit - offset + 3 bit を取り出す。
  • ③② の後ろから 31bit を取得する。
  • ④ これが OTP で(31bit なので最大 2147483648)、後は指定の桁数で落とす。(これ見て気づいたけど、記載はないが HOTP の RFC 水準で考えると digit 最大は実質 10 なのだと思われる)
  • ちなみにサンプルの public static byte[] hmac_sha1 を見るとわかりますが、key が secret で、承認用メッセージが counter/時間情報です(RFC4226 の方)。

ある程度わかったのでまとめます。

とりあえずまとめた全体図

nya

Thanks: draw.io

実装

大体下記の実装で良さそう。

  • TOTP
    • generate_otp (secret, time_step, time_offset, digit, digest)
    • generate_counter(time_step, time_offset)
    • もし time-step window やるなら now と at みたいな関数も必要と思う(何個前の、という指定が必要なので)。
  • HOTP (本来別なので)
    • generate_hasher(secret, counter(TOTP なので時間情報だが、hotp アルゴリズム自体はカウントを用いる物なので名称はこれが良さそう), digest)
    • truncate_hasher(hasher)

備考

Rust の hash/hmac ライブラリはいくつかあるのですが、rust-postgres で実績のあるライブラリを選定しました。rust-crypto は 2016 年が最終更新なのでやめました。
また、デフォルト値は derive(Default)して

impl Default for HotpCounterElement {
  fn default() -> Self {
    HotpCounterElement {
      time_step: 30,
      time_offset: 0,
    }
  }
}

みたいな struct 作ろうかと思いましたが、cli でフリーチェックとかしたいので慣れてる structopt でデフォルト値は全て入れました。
あと原理理解が目的かつ第一だったのでパッと書きましたが、作り方駄目だよって場合はコメントにてご指摘ください。

ではまず簡単そうな TOTP の counter から作りましょう。

fn generate_counter(time_step: u64, time_offset: u64) -> [u8; 8] {
  let current_time = SystemTime::now()
    .duration_since(UNIX_EPOCH)
    .unwrap()
    .as_secs();
  let counter = (current_time - time_offset) / time_step;
  let mut unpacked_counter = [0; 8];
  BigEndian::write_u64(&mut unpacked_counter, counter);

  unpacked_counter
}

hmac へ渡すキーは u8 なので、計算後に unpack しています。ここは簡単ですね。

TOTP はこの counter と他情報を HOTP にわたすだけの役目なので、次に HOTP の実装をします。まず hasher を生成する関数を作成します。ここで sha1, sha256, sha512 をいい感じに切り分けたいのですが、sha1 だけ別ライブラリで型が違うのでちょっとうまく書けないか悩みました。最終的に enum で match させました。

pub enum HashType {
  Sha1,
  Sha256,
  Sha512,
}

enum HashReceiver {
  Sha1([u8; 20]),
  Sha256(Box<Hmac<Sha256>>),
  Sha512(Box<Hmac<Sha512>>),
}

fn generate_hasher(secret: &[u8], counter: &[u8], digest: HashType) -> Vec<u8> {
  let hmac = match digest {
    HashType::Sha1 => HashReceiver::Sha1(hmac_sha1(secret, counter)),
    HashType::Sha256 => HashReceiver::Sha256(Box::new(
      Hmac::<Sha256>::new_varkey(secret).expect("HMAC is able to accept all key sizes"),
    )),
    HashType::Sha512 => HashReceiver::Sha512(Box::new(
      Hmac::<Sha512>::new_varkey(secret).expect("HMAC is able to accept all key sizes"),
    )),
  };

  // hasher is surely 20 byte sized, but hmac lib returns unsized.
  match hmac {
    HashReceiver::Sha1(hmac) => hmac.to_vec(),
    HashReceiver::Sha256(mut hmac) => {
      hmac.update(counter);
      hmac.finalize().into_bytes().to_vec()
    }
    HashReceiver::Sha512(mut hmac) => {
      hmac.update(counter);
      hmac.finalize().into_bytes().to_vec()
    }
  }
}

Box を入れているのは巨大すぎる為です。Box を入れる事でかなりの容量削減になります(これは clippy で見つける事ができます)。これ、もし 256 と 512 しか無い場合は HMAC::<T> とかでスマートにかけるのかな・・・とか少し調べましたが、うまくいかずそのまま書きました(どのみち今回は1も考慮するし)。型毎に impl して、generics をラップするという方法もありますがそちらは記述が長いのでやめました。どっちの方が好ましいのかはよくわかってないですが enum の方が目的が明示化されてて良いのではないかと考えています。

またコメントに記載していますが hmac.finalize().into_bytes()した結果は unsized です。一方 hmac_sha1 のライブラリはちゃんとサイズ決めてくれてるのでありがたい。

次に Truncate 部分を実装します。計算箇所が非常に複雑かつ、ここが HOTP の肝なのでコメントで説明しています。内容は先程書いた通りです。

fn truncate_hasher(hasher: &[u8], digits: u32) -> u64 {
  // offset_bit is the decimal number of the last 4 bits of hasher.
  let offset_bit = (hasher[hasher.len() - 1] & 0xf) as usize;
  let mut hasher_partial_value = 0u64;
  // ex.) hasher_partial_value
  // if offset = 10, and
  // hasher[10] = 0x99, hasher[11] = 0x88, hasher[12] = 0x77, hasher[13] = 0x66,
  // you want to get the decimal number of 0x99887766.
  hasher_partial_value += (hasher[offset_bit] as u64) << (24 as u64);
  hasher_partial_value += (hasher[offset_bit + 1] as u64) << (16 as u64);
  hasher_partial_value += (hasher[offset_bit + 2] as u64) << (8 as u64);
  hasher_partial_value += hasher[offset_bit + 3] as u64;
  // otp is the decimal number of the last 32bits of hasher_partial_value.
  let otp = hasher_partial_value & 0x7fffffff;

  otp % 10_u64.pow(digits)
}

python とかだと綺麗にhasher[offset_bit:offset_bit+4]とかで一気に取得できるみたいです。Rust はできない(と思われる、後から色々調べたけど無理そう)なので、愚直に足していきます。

ここまできて動作確認できたら、おまけといってはなんですがフリーチェックしやすいように Structopt もいれましょう。

#[derive(StructOpt, Debug)]
#[structopt(
  name = "rust-totp",
  about = "Implementation of totp in Rust",
  setting(ColorAlways),
  setting(ColoredHelp),
  after_help = "This is just for personal use."
)]
struct Opt {
  #[structopt(long = "secret")]
  pub secret: String,

  #[structopt(long = "timestep", default_value = "30")]
  pub time_step: u64,

  #[structopt(long = "offset", default_value = "0")]
  pub time_offset: u64,

  #[structopt(long = "digits", default_value = "6")]
  pub digits: u32,

  #[structopt(long = "digest", default_value = "512")]
  pub digest: u64,
}

コメントにも記載してますが、clap の arg_enum 使うと possible_values も指定できます。ちょっと冗長になるので今回はやってませんが、digest とかは3種類しかないからやってもよかったかも。

動作確認してみると ↓

nya
nya

期待した通りできてますね。30 秒待っても OTP は更新されず、unix0 から 30 区切りの基準を超えると OTP が更新される事を確認できます。良さそうなので justfile とテストも追加していきましょう。ありがたい事にRFC でテストケースを用意してくれています。簡単にですが、RFC で用意されているデータ部分のみテストをしてみましょう。

#[test]
fn test_generate_otp() {
  // test values from RFC 4226
  // https://tools.ietf.org/html/rfc4226#page-32
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 0], 6, HashType::Sha1), 755224);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 1], 6, HashType::Sha1), 287082);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 2], 6, HashType::Sha1), 359152);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 3], 6, HashType::Sha1), 969429);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 4], 6, HashType::Sha1), 338314);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 5], 6, HashType::Sha1), 254676);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 6], 6, HashType::Sha1), 287922);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 7], 6, HashType::Sha1), 162583);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 8], 6, HashType::Sha1), 399871);
  assert_eq!(generate_otp(b"12345678901234567890", &[0, 0, 0, 0, 0, 0, 0, 9], 6, HashType::Sha1), 520489);
}
format:
  cargo fmt --all

lint:
  cargo clippy

test:
  cargo test

build:
  cargo build --release

all: format lint test build

動作確認すると ↓

nya

正常動作していますね。

これにて実装終わりです。改めて成果物はこちら。

https://github.com/ulwlu/rust-totp

まとめ

wiki&論文から自分でアルゴリズム実装というのは 2 回経験あったのですが、RFC は図がほぼ無くて、ここから実装するのはなかなか体力いりました。このくらいの重量の実装をポンポンこなして、実装力というか実装 HP/MP というか、何でも来いくらいになれるよう精進精進。

ちなみに:あとから他の人の実装見てましたが、クラスメソッド様の奥様の記事のが滅茶苦茶わかりやすかったです。

GitHubで編集を提案

Discussion

ログインするとコメントできます