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

公開:2021/02/13
更新:2021/02/15
13 min読了の目安(約12200字TECH技術記事

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

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の方)。

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

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

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種類しかないからやってもよかったかも。

動作確認してみると↓


期待した通りできてますね。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

動作確認すると↓

正常動作していますね。

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

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

まとめ

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

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