Merge GH #1054 Add HOTP and TOTP algorithms

11 files changed, 592 insertions, 0 deletions

diff --git a/doc/manual/contents.rst b/doc/manual/contents.rst
index 20bd855a0..23fa218b2 100644
--- a/doc/manual/contents.rst
+++ b/doc/manual/contents.rst
@@ -30,6 +30,7 @@ Contents
    compression
    pkcs11
    tpm
+   otp
    ffi
    python
    cli
diff --git a/doc/manual/otp.rst b/doc/manual/otp.rst
new file mode 100644
index 000000000..5c49c4533
--- /dev/null
+++ b/doc/manual/otp.rst
@@ -0,0 +1,67 @@
+One Time Passwords
+========================
+
+One time password schemes are a user authentication method that relies on a
+fixed secret key which is used to derive a sequence of short passwords, each of
+which is accepted only once. Commonly this is used to implement two-factor
+authentication (2FA), where the user authenticates using both a conventional
+password (or a public key signature) and an OTP generated by a small device such
+as a mobile phone.
+
+Botan implements the HOTP and TOTP schemes from RFC 4226 and 6238.
+
+Since the range of possible OTPs is quite small, applications must rate limit
+OTP authentication attempts to some small number per second. Otherwise an attacker
+could quickly try all 1000000 6-digit OTPs in a brief amount of time.
+
+HOTP
+^^^^^^
+
+HOTP generates OTPs that are a short numeric sequence, between 6 and 8 digits
+(most applications use 6 digits), created using the HMAC of a 64-bit counter
+value. If the counter ever repeats the OTP will also repeat, thus both parties
+must assure the counter only increments and is never repeated or
+decremented. Thus both client and server must keep track of the next counter
+expected.
+
+Anyone with access to the client-specific secret key can authenticate as that
+client, so it should be treated with the same security consideration as would be
+given to any other symmetric key or plaintext password.
+
+.. cpp:class:: HOTP
+
+    Implement counter-based OTP
+
+    .. cpp:function:: HOTP(const SymmetricKey& key, const std::string& hash_algo = "SHA-1", size_t digits = 6)
+
+       Initialize an HOTP instance with a secret key (specific to each client),
+       a hash algorithm (must be SHA-1, SHA-256, or SHA-512), and the number of
+       digits with each OTP (must be 6, 7, or 8).
+
+       In RFC 4226, HOTP is only defined with SHA-1, but many HOTP
+       implementations support SHA-256 as an extension. The collision attacks
+       on SHA-1 do not have any known effect on HOTP's security.
+
+    .. cpp:function:: uint32_t generate_hotp(uint64_t counter)
+
+       Return the OTP assosciated with a specific counter value.
+
+    .. cpp:function:: std::pair<bool,uint64_t> verify_hotp(uint32_t otp, \
+                      uint64_t starting_counter, size_t resync_range = 0)
+
+       Check if a provided OTP matches the one that should be generated for
+       the specified counter.
+
+       The *starting_counter* should be the counter of the last successful
+       authentication plus 1. If *resync_resync* is greater than 0, some number
+       of counter values above *starting_counter* will also be checked if
+       necessary. This is useful for instance when a client mistypes an OTP on
+       entry; the authentication will fail so the server will not update its
+       counter, but the client device will subsequently show the OTP for the
+       next counter. Depending on the environment a *resync_range* of 3 to 10
+       might be appropriate.
+
+       Returns a pair of (is_valid,next_counter_to_use). If the OTP is invalid
+       then always returns (false,starting_counter), since the last successful
+       authentication counter has not changed.
+
diff --git a/src/cli/utils.cpp b/src/cli/utils.cpp
index 65923ec47..2bf03c760 100644
--- a/src/cli/utils.cpp
+++ b/src/cli/utils.cpp
@@ -41,6 +41,10 @@
    #include <botan/hmac.h>
 #endif
 
+#if defined(BOTAN_HAS_HOTP)
+   #include <botan/hotp.h>
+#endif
+
 namespace Botan_CLI {
 
 class Config_Info final : public Command
diff --git a/src/lib/misc/hotp/hotp.cpp b/src/lib/misc/hotp/hotp.cpp
new file mode 100644
index 000000000..f07c11c9f
--- /dev/null
+++ b/src/lib/misc/hotp/hotp.cpp
@@ -0,0 +1,62 @@
+/*
+* HOTP
+* (C) 2017 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/hotp.h>
+
+namespace Botan {
+
+HOTP::HOTP(const SymmetricKey& key, const std::string& hash_algo, size_t digits)
+   {
+   if(digits == 6)
+      m_digit_mod = 1000000;
+   else if(digits == 7)
+      m_digit_mod = 10000000;
+   else if(digits == 8)
+      m_digit_mod = 100000000;
+   else
+      throw Invalid_Argument("Invalid HOTP digits");
+
+   /*
+   RFC 4228 only supports SHA-1 but TOTP allows SHA-256 and SHA-512
+   and some HOTP libs support one or both as extensions
+   */
+   if(hash_algo == "SHA-1")
+      m_mac = MessageAuthenticationCode::create_or_throw("HMAC(SHA-1)");
+   else if(hash_algo == "SHA-256")
+      m_mac = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");
+   else if(hash_algo == "SHA-512")
+      m_mac = MessageAuthenticationCode::create_or_throw("HMAC(SHA-512)");
+   else
+      throw Invalid_Argument("Unsupported HOTP hash function");
+
+   m_mac->set_key(key);
+   }
+
+uint32_t HOTP::generate_hotp(uint64_t counter)
+   {
+   uint8_t counter8[8] = { 0 };
+   store_be(counter, counter8);
+   m_mac->update(counter8, sizeof(counter8));
+   const secure_vector<uint8_t> mac = m_mac->final();
+
+   const size_t offset = mac[mac.size()-1] & 0x0F;
+   const uint32_t code = load_be<uint32_t>(mac.data() + offset, 0) & 0x7FFFFFFF;
+   return code % m_digit_mod;
+   }
+
+std::pair<bool,uint64_t> HOTP::verify_hotp(uint32_t otp, uint64_t starting_counter, size_t resync_range)
+   {
+   for(size_t i = 0; i <= resync_range; ++i)
+      {
+      if(generate_hotp(starting_counter + i) == otp)
+         return std::make_pair(true, starting_counter + i + 1);
+      }
+   return std::make_pair(false, starting_counter);
+   }
+
+}
+
diff --git a/src/lib/misc/hotp/hotp.h b/src/lib/misc/hotp/hotp.h
new file mode 100644
index 000000000..cc222e5c0
--- /dev/null
+++ b/src/lib/misc/hotp/hotp.h
@@ -0,0 +1,52 @@
+/*
+* HOTP
+* (C) 2017 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_HOTP_H__
+#define BOTAN_HOTP_H__
+
+#include <botan/mac.h>
+
+namespace Botan {
+
+/**
+* HOTP one time passwords (RFC 4226)
+*/
+class BOTAN_DLL HOTP
+   {
+   public:
+      /**
+      * @param key the secret key shared between client and server
+      * @param hash_algo the hash algorithm to use, should be SHA-1 or SHA-256
+      * @param digits the number of digits in the OTP (must be 6, 7, or 8)
+      */
+      HOTP(const SymmetricKey& key, const std::string& hash_algo = "SHA-1", size_t digits = 6);
+
+      /**
+      * Generate the HOTP for a particular counter value
+      * @warning if the counter value is repeated the OTP ceases to be one-time
+      */
+      uint32_t generate_hotp(uint64_t counter);
+
+      /**
+      * Check an OTP value using a starting counter and a resync range
+      * @param otp the client provided OTP
+      * @param starting_counter the server's guess as to the current counter state
+      * @param resync_range if 0 then only HOTP(starting_counter) is accepted
+      * If larger than 0, up to resync_range values after HOTP are also checked.
+      * @return (valid,next_counter). If the OTP does not validate, always
+      * returns (false,starting_counter). Otherwise returns (true,next_counter)
+      * where next_counter is at most starting_counter + resync_range + 1
+      */
+      std::pair<bool,uint64_t> verify_hotp(uint32_t otp, uint64_t starting_counter, size_t resync_range = 0);
+   private:
+      std::unique_ptr<MessageAuthenticationCode> m_mac;
+      uint32_t m_digit_mod;
+   };
+
+}
+
+#endif
diff --git a/src/lib/misc/hotp/info.txt b/src/lib/misc/hotp/info.txt
new file mode 100644
index 000000000..ad74686c3
--- /dev/null
+++ b/src/lib/misc/hotp/info.txt
@@ -0,0 +1,9 @@
+<defines>
+HOTP -> 20170513
+TOTP -> 20170519
+</defines>
+
+<requires>
+hmac
+utils
+</requires>
diff --git a/src/lib/misc/hotp/totp.cpp b/src/lib/misc/hotp/totp.cpp
new file mode 100644
index 000000000..c3203c32a
--- /dev/null
+++ b/src/lib/misc/hotp/totp.cpp
@@ -0,0 +1,63 @@
+/*
+* TOTP
+* (C) 2017 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/totp.h>
+#include <botan/calendar.h>
+
+namespace Botan {
+
+TOTP::TOTP(const SymmetricKey& key, const std::string& hash_algo,
+           size_t digits, size_t time_step)
+   : m_hotp(key, hash_algo, digits)
+   , m_time_step(time_step)
+   , m_unix_epoch(calendar_point(1970, 1, 1, 0, 0, 0).to_std_timepoint())
+   {
+   /*
+   * Technically any time step except 0 is valid, but 30 is typical
+   * and over 5 minutes seems unlikely.
+   */
+   if(m_time_step == 0 || m_time_step > 300)
+      throw Invalid_Argument("Invalid TOTP time step");
+   }
+
+uint32_t TOTP::generate_totp(std::chrono::system_clock::time_point current_time)
+   {
+   const uint64_t unix_time =
+      std::chrono::duration_cast<std::chrono::seconds>(current_time - m_unix_epoch).count();
+   return this->generate_totp(unix_time);
+   }
+
+uint32_t TOTP::generate_totp(uint64_t unix_time)
+   {
+   return m_hotp.generate_hotp(unix_time / m_time_step);
+   }
+
+bool TOTP::verify_totp(uint32_t otp, std::chrono::system_clock::time_point current_time,
+                       size_t clock_drift_accepted)
+   {
+   const uint64_t unix_time =
+      std::chrono::duration_cast<std::chrono::seconds>(current_time - m_unix_epoch).count();
+   return verify_totp(otp, unix_time, clock_drift_accepted);
+   }
+
+bool TOTP::verify_totp(uint32_t otp, uint64_t unix_time,
+                       size_t clock_drift_accepted)
+   {
+   uint64_t t = unix_time / m_time_step;
+
+   for(size_t i = 0; i <= clock_drift_accepted; ++i)
+      {
+      if(m_hotp.generate_hotp(t-i) == otp)
+         {
+         return true;
+         }
+      }
+
+   return false;
+   }
+
+}
diff --git a/src/lib/misc/hotp/totp.h b/src/lib/misc/hotp/totp.h
new file mode 100644
index 000000000..767c7cc5a
--- /dev/null
+++ b/src/lib/misc/hotp/totp.h
@@ -0,0 +1,56 @@
+/*
+* (C) 2017 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_TOTP_H__
+#define BOTAN_TOTP_H__
+
+#include <botan/hotp.h>
+#include <chrono>
+
+namespace Botan {
+
+/**
+* TOTP (time based) one time passwords (RFC 6238)
+*/
+class BOTAN_DLL TOTP
+   {
+   public:
+      /**
+      * @param key the secret key shared between client and server
+      * @param hash_algo the hash algorithm to use, should be SHA-1, SHA-256 or SHA-512
+      * @param digits the number of digits in the OTP (must be 6, 7, or 8)
+      * @param time_step granularity of OTP in seconds
+      */
+      TOTP(const SymmetricKey& key, const std::string& hash_algo = "SHA-1",
+           size_t digits = 6, size_t time_step = 30);
+
+      /**
+      * Convert the provided time_point to a Unix timestamp and call generate_totp
+      */
+      uint32_t generate_totp(std::chrono::system_clock::time_point time_point);
+
+      /**
+      * Generate the OTP cooresponding the the provided "Unix timestamp" (ie
+      * number of seconds since midnight Jan 1, 1970)
+      */
+      uint32_t generate_totp(uint64_t unix_time);
+
+      bool verify_totp(uint32_t otp,
+                       std::chrono::system_clock::time_point time,
+                       size_t clock_drift_accepted = 0);
+
+      bool verify_totp(uint32_t otp, uint64_t unix_time,
+                       size_t clock_drift_accepted = 0);
+
+   private:
+      HOTP m_hotp;
+      size_t m_time_step;
+      std::chrono::system_clock::time_point m_unix_epoch;
+   };
+
+}
+
+#endif
diff --git a/src/tests/data/otp/hotp.vec b/src/tests/data/otp/hotp.vec
new file mode 100644
index 000000000..60e3d1665
--- /dev/null
+++ b/src/tests/data/otp/hotp.vec
@@ -0,0 +1,127 @@
+[SHA-1]
+
+# From RFC 4226
+
+Key = 3132333435363738393031323334353637383930
+Digits = 6
+
+Counter = 0
+OTP = 755224
+
+Counter = 1
+OTP = 287082
+
+Counter = 2
+OTP = 359152
+
+Counter = 3
+OTP = 969429
+
+Counter = 4
+OTP = 338314
+
+Counter = 5
+OTP = 254676
+
+Counter = 6
+OTP = 287922
+
+Counter = 7
+OTP = 162583
+
+Counter = 8
+OTP = 399871
+
+Counter = 9
+OTP = 520489
+
+# Long digit tests
+
+Digits = 7
+
+Counter = 7
+OTP = 2162583
+
+Counter = 8
+OTP = 3399871
+
+Digits = 8
+
+Counter = 7
+OTP = 82162583
+
+Counter = 8
+OTP = 73399871
+
+# From RFC 6238
+
+Key = 3132333435363738393031323334353637383930
+Digits = 8
+
+Counter = 1
+OTP = 94287082
+
+Counter = 37037036
+OTP = 07081804
+
+Counter = 37037037
+OTP = 14050471
+
+Counter = 41152263
+OTP = 89005924
+
+Counter = 66666666
+OTP = 69279037
+
+Counter = 666666666
+OTP = 65353130
+
+[SHA-256]
+
+# From RFC 6238
+
+Key = 3132333435363738393031323334353637383930313233343536373839303132
+Digits = 8
+
+Counter = 1
+OTP = 46119246
+
+Counter = 37037036
+OTP = 68084774
+
+Counter = 37037037
+OTP = 67062674
+
+Counter = 41152263
+OTP = 91819424
+
+Counter = 66666666
+OTP = 90698825
+
+Counter = 666666666
+OTP = 77737706
+
+[SHA-512]
+
+# From RFC 6238
+
+Key = 31323334353637383930313233343536373839303132333435363738393031323334353637383930313233343536373839303132333435363738393031323334
+Digits = 8
+
+Counter = 1
+OTP = 90693936
+
+Counter = 37037036
+OTP = 25091201
+
+Counter = 37037037
+OTP = 99943326
+
+Counter = 41152263
+OTP = 93441116
+
+Counter = 66666666
+OTP = 38618901
+
+Counter = 666666666
+OTP = 47863826
diff --git a/src/tests/data/otp/totp.vec b/src/tests/data/otp/totp.vec
new file mode 100644
index 000000000..2247b6f14
--- /dev/null
+++ b/src/tests/data/otp/totp.vec
@@ -0,0 +1,19 @@
+[SHA-1]
+
+# From RFC 6238
+
+Key = 3132333435363738393031323334353637383930
+Digits = 8
+Timestep = 30
+
+Timestamp = 1970-01-01T00:00:59
+OTP = 94287082
+
+Timestamp = 2005-03-18T01:58:29
+OTP = 07081804
+
+Timestamp = 2009-02-13T23:31:30
+OTP = 89005924
+
+Timestamp = 2033-05-18:03:33:20
+OTP = 69279037
diff --git a/src/tests/test_otp.cpp b/src/tests/test_otp.cpp
new file mode 100644
index 000000000..480065194
--- /dev/null
+++ b/src/tests/test_otp.cpp
@@ -0,0 +1,132 @@
+/*
+* OTP tests
+* (C) 2017 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "tests.h"
+
+#if defined(BOTAN_HAS_HOTP)
+   #include <botan/hotp.h>
+#endif
+
+#if defined(BOTAN_HAS_TOTP)
+   #include <botan/totp.h>
+   #include <botan/calendar.h>
+#endif
+
+namespace Botan_Tests {
+
+#if defined(BOTAN_HAS_HOTP)
+
+class HOTP_KAT_Tests : public Text_Based_Test
+   {
+   public:
+      HOTP_KAT_Tests()
+         : Text_Based_Test("otp/hotp.vec", "Key,Digits,Counter,OTP")
+         {}
+
+      bool clear_between_callbacks() const override { return false; }
+
+      Test::Result run_one_test(const std::string& hash_algo, const VarMap& vars) override
+         {
+         Test::Result result("HOTP " + hash_algo);
+
+         const std::vector<uint8_t> key = get_req_bin(vars, "Key");
+         const size_t otp = get_req_sz(vars, "OTP");
+         const uint64_t counter = get_req_sz(vars, "Counter");
+         const size_t digits = get_req_sz(vars, "Digits");
+
+         Botan::HOTP hotp(key, hash_algo, digits);
+
+         result.test_eq("OTP", hotp.generate_hotp(counter), otp);
+
+         std::pair<bool, uint64_t> otp_res = hotp.verify_hotp(otp, counter, 0);
+         result.test_eq("OTP verify result", otp_res.first, true);
+         result.confirm("OTP verify next counter", otp_res.second == counter + 1);
+
+         // Test invalid OTP
+         otp_res = hotp.verify_hotp(otp + 1, counter, 0);
+         result.test_eq("OTP verify result", otp_res.first, false);
+         result.confirm("OTP verify next counter", otp_res.second == counter);
+
+         // Test invalid OTP with long range
+         otp_res = hotp.verify_hotp(otp + 1, counter, 100);
+         result.test_eq("OTP verify result", otp_res.first, false);
+         result.confirm("OTP verify next counter", otp_res.second == counter);
+
+         // Test valid OTP with long range
+         otp_res = hotp.verify_hotp(otp, counter - 90, 100);
+         result.test_eq("OTP verify result", otp_res.first, true);
+         result.confirm("OTP verify next counter", otp_res.second == counter + 1);
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("otp_hotp", HOTP_KAT_Tests);
+
+#endif
+
+#if defined(BOTAN_HAS_TOTP)
+
+class TOTP_KAT_Tests : public Text_Based_Test
+   {
+   public:
+      TOTP_KAT_Tests()
+         : Text_Based_Test("otp/totp.vec", "Key,Digits,Timestep,Timestamp,OTP")
+         {}
+
+      bool clear_between_callbacks() const override { return false; }
+
+      Test::Result run_one_test(const std::string& hash_algo, const VarMap& vars) override
+         {
+         Test::Result result("TOTP " + hash_algo);
+
+         const std::vector<uint8_t> key = get_req_bin(vars, "Key");
+         const size_t otp = get_req_sz(vars, "OTP");
+         const size_t digits = get_req_sz(vars, "Digits");
+         const size_t timestep = get_req_sz(vars, "Timestep");
+         const std::string timestamp = get_req_str(vars, "Timestamp");
+
+         Botan::TOTP totp(key, hash_algo, digits, timestep);
+
+         std::chrono::system_clock::time_point time = from_timestring(timestamp);
+         std::chrono::system_clock::time_point later_time = time + std::chrono::seconds(timestep);
+         std::chrono::system_clock::time_point too_late = time + std::chrono::seconds(2*timestep);
+
+         result.test_eq("TOTP generate", totp.generate_totp(time), otp);
+
+         result.test_eq("TOTP verify valid", totp.verify_totp(otp, time, 0), true);
+         result.test_eq("TOTP verify invalid", totp.verify_totp(otp ^ 1, time, 0), false);
+         result.test_eq("TOTP verify time slip", totp.verify_totp(otp, later_time, 0), false);
+         result.test_eq("TOTP verify time slip allowed", totp.verify_totp(otp, later_time, 1), true);
+         result.test_eq("TOTP verify time slip out of range", totp.verify_totp(otp, too_late, 1), false);
+
+         return result;
+         }
+
+   private:
+      std::chrono::system_clock::time_point from_timestring(const std::string& time_str)
+         {
+         if(time_str.size() != 19)
+            throw std::invalid_argument("Invalid TOTP timestamp string " + time_str);
+         // YYYY-MM-DDTHH:MM:SS
+         // 0123456789012345678
+         const uint32_t year = Botan::to_u32bit(time_str.substr(0, 4));
+         const uint32_t month = Botan::to_u32bit(time_str.substr(5, 2));
+         const uint32_t day = Botan::to_u32bit(time_str.substr(8, 2));
+         const uint32_t hour = Botan::to_u32bit(time_str.substr(11, 2));
+         const uint32_t minute = Botan::to_u32bit(time_str.substr(14, 2));
+         const uint32_t second = Botan::to_u32bit(time_str.substr(17, 2));
+         return Botan::calendar_point(year, month, day, hour, minute, second).to_std_timepoint();
+         }
+   };
+
+BOTAN_REGISTER_TEST("otp_totp", TOTP_KAT_Tests);
+#endif
+
+}
+
+