logauth
/
schastsp
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
Page: STSP
Pages
Overview STSP
5 STSP
xdrm-brackets edited this page 2018-04-23 15:54:12 -04:00
Unescape Escape
Table of Contents
This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Stateless Time Scrambling Protocol

Motivation

After designing some APIs, I found out that you must have at some point a token system where the token is a fixed-length string. An easy MITM attack could be to repeat a previously sent request while the token is still valid. Or in worse conditions, catch the client token and build a malicious request with its authenticated session.

In the rest of this document we will admit that what travels through the network is public, so any MITM can store it. Obviously I highly recommend using TLS for communicating, but we look here for a consistent token system, it only can be better through TLS.

A good solution could be to use a one-time token so the server sends back a new token for each response. This behavior means that the token travels through the network - which we consider public - before being used. In addition we would like the server to create only a secret key once to fasten the authentication system, because it could manage millions of clients.

A better solution would be to keep a private key and wrap it in a one-time system that generates a public token for each request. It would avoid attackers to repeat our requests or guess the private key from the token. Also short-lived one-time passwords have a mechanism that we could use to build a time-dependent system.

What we need

  1. Generate a public token for each request from a fixed private key (protocol documentation here)
  2. The public token never to be the same
  3. Each public token to be only valid a few seconds after sending it (protocol documentation here)

Technology requirements

  1. Mixing 2 hashes in a way that without one of them, the other is cryptographically impossible to guess (i.e. one-time pad).
  2. Having a time-dependent unique hash, that could be found only a few seconds after sending it (as for TOTP).

Documents

  • The stateless cyclic hash algorithm that generates a unique public token from a fixed private key has its documentation available here.

General knowledge & Notations

Notation

Symbols Description
\|a\| The absolute value of a. \|a\|=\|-a\|
\mid a \mid The integer value of a
(e.g. \mid 12.34 \mid = 12)
a \oplus b The bitwise operation XOR between binary words a and b
h(m) The digest of the message m by a consistent cryptographic hashing function h().
(e.g. sha-512)
L The length in bits of the digest of the hash function h(); i.e. L is 4 times the length of the hexadecimal representation
f(x, n^1) A one-way function that will, from an input x and a nonce n^1​ result in a value y​ of L​ bits. From y​ and n^1​, it must be cryptographically impossible to guess x​. Note that 2 different nonces with the same input must never output the same value.
a \mod b The result of a modulo b (the remainder of the Euclidean division of a by b)
T_{now} The current Unix Timestamp in seconds

One-way function f()

  • The function f should be replaced with any consistent algorithm such as one-time password (OTC) or the cyclic-hash algorithm for instance.
  • If you only want the time-dependent feature, you can set f(x, n^1) to always return x. The key K will be only protected by the time protection protocol described in this document. I highly recommend not to choose this option. The private key is easily extractable from attackers sniffing the requests.

Entities

  • A machine C (i.e. typically a client)
  • A machine S (i.e. typically a server)

Variables

Variable Name Description
W window size A fixed number of seconds; i.e. typically the maximum transmission time
K shifting key A fixed private key. C and S both must have the same value and eventually a way to resynchronize it the key have been compromised or have been used for too long.
n^1 shifting nonce A unique request index. It is updated on both C and S after each valid request-response exchange. Warning: 2 requests must not have the same index !
(e.g. the index could be incremented after each request on both machines)

Description of the problem

C wants to send a token that will only be valid one time and within a fixed time window.

​ Note: This document only gives a solution for the time-dependent feature, the one-time aspect is wrapped into the implementation of the f() function. If you only need the time-dependent feature, you can set f(x, n^1) to always return x so the key K will be only protected by the time protection algorithm.

Constraints

  • S must be able to recover the token only if the data is received within the time window.
  • If the window expired, no one will never be able to recover the token from the request itself (not considering the headers containing the date).

Requirements

  • The window size constant W must be the same on the 2 machines.
  • The shifting key constant K must always be the same on the 2 machines.
  • The shifting nonce n^1 must always be the same on the 2 machines over requests.

Limitations

  • If an arbitrary catches, then blocks a request from C to S and sends it after, it will be authenticated. This case is equivalent to being C (with all secret variables), which can never occur if you use TLS. Notice that you won't be able to extract anything from the caught token anyway.
  • With requests meta data (e.g. HTTP headers containing the date), an attacker knowing W can forge the time hash h_n and be able to recover the private key K by processing a simple XOR on the public token. If the function f() is strong enough to generate a unique pseudo-random token from K for each request, this issue is no more relevant.

Protocol

1. Scramble the request

Variables

  • W the fixed window size
  • K​ the shifting key (same on both machines)
  • n^1 the shifting nonce (same on both machines)
Step Description Formula
c1 Calculate the one-time token T_C T_C = f(K, n^1)
c2 Get the current window id n_C n_C =\ \mid \frac{T_{now}}{W} \mid
c3 Calculate m_C, the parity of n_C m_C = n_C \mod 2
c4 Calculate the time hash h_{n_C} h_{n_C} = h(n_C)
c5 Calculate T_{req}, the scrambled request token T_{req} = T_C \oplus h_{n_C}

Steps explanation

  • c2 - The window id corresponds to the index of the time slice where slices are W seconds wide. By dividing the time in slices of W seconds, if we process the same calculation at an interval of W or less seconds, we will have either the same result or a result greater by 1.
  • c3 - The window id parity m_C allows us to adjust the value of n_S made on S when it receives the request. This difference of 1 second is caused by the division of time in slices, the precision is also divided by W.
    • T_{now}\mod W = 0 \implies \mid \frac{T_{now}}{W} \mid = \mid \frac{T_{now}+(W-1)}{W} \mid; no need for adjustment
    • T_{now}\mod W = 1 \implies \mid \frac{T_{now}}{W} \mid = \mid \frac{T_{now}+(W-1)}{W} \mid + 1; need to subtract 1
    • T_{now}\mod W = 2 \implies \mid \frac{T_{now}}{W} \mid = \mid \frac{T_{now}+(W-1)}{W} \mid + 1; need to subtract 1
    • ...
    • T_{now}\mod W = (W-1) \implies \mid \frac{T_{now}}{W} \mid = \mid \frac{T_{now}+(W-1)}{W} \mid + 1; need to subtract 1
  • c4 - h(n_C) allows h_{n_C} to be L bits long and protects n_C to be predictable from h_{n_C}.
  • c5 - we process a one-time pad between T_C and h_{n_C} it is crucial that both values have the same size of L bits. It makes T_C impossible to extract without having the value h_{n_C}, this property applies in both ways.

Short formulas

Field to send Short formula
T_{req} f(K, n^1) \oplus h(\mid\frac{T_{now}}{W}\mid)
m_C \mid\frac{T_{now}}{W}\mid \mod 2

Note

  • In order to send all the data in one request, for instance you can simply concatenate the 2 variables.

2. Unscramble the request

Variables

  • W the fixed window size
  • K the shifting key (same on both machines)
  • n^1 the shifting nonce (same on both machines)

Received data

  • T_{req} the received request token
  • m_C the received time id parity
Step Description Formula
s1 Calculate the one-time token T_S T_S = f(K, n^1)
s2 Store the reception time window id n' n' = \mid \frac{T_{now}}{W}\mid
s3 Calculate m_S, the parity of n' m_S = n' \mod 2
s4 Use m_C to try to correct the reception window id and guess the sender window id n_S = n' - \| m_C - m_S \|
s5 Calculate the time hash h_{n_S} h_{n_S} = h(n_S)
s6 Cancel h_{n_S} to extract T_{C'} T_{C'} = T_{req} \oplus h_{n_S}
s7 Check if T_{C'} matches T_S T_{C'} = T_S ?

If T_{C'} = T_S, S can consider that C sent the request 0 to (W + \frac{W}{2}) seconds ago.

Steps explanation

  • s1 - If C and S have the same values for K and n^1, f(K,n^1) must result in the same output; in other words T_C=T_S.

  • s3/s4 - \| m_C - m_s\| is the difference between m_C and m_S.

    • If the receiver time window id (n') is the same as the sender (n_C)

      ​ n'=n_C \implies m_S=m_C

      ​ m_C=m_S \implies \| m_C - m_S\| = 0

      ​ n_S = n_C - 0

      ​ n_S=n_C, the time ids are the same, S can now unscramble the request to check the token

    • If the receiver time window if further the sender by 1

      ​ n'=n_C+1 \implies \| m_C - m_S \| = 1

      ​ n_S = n_C + 1 - 1

      ​ n_S = n_C, the time ids are the same, S can now unscramble the request to check the token

    • If the receiver time window if further the sender by 2 or more, let k \in \N

      ​ n'= n_C+2+k \implies \| m_C - m_S\| \in \{0,1\}

      ​ - \| m_C - m_S\| \in \{-1,0\}

      ​ n_S \in \{n_C + 2 + k - 1, n_C + 2 + k + 0\}

      ​ n_S \in \{n_C + k + 1, n_C + k + 2\}

      ​ \rarr n_S = n_C + k + 1 \implies \forall (k\in \N), n_S \gt n_C, the time ids differ, S cannot extract T_S

      ​ \rarr n_S = n_C + k + 2 \implies \forall (k \in \N), n_S \gt n_C+1, the time ids differ, S cannot extract T_S

  • s6 - By the non-idempotency (i.e. a\oplus b \oplus a = b) and associativity properties of the XOR operator, considering h_{n_S}=h_{n_C}:

    ​ T_{C'} = T_{req} \oplus h_{n_S} = (T_C \oplus h_{n_C}) \oplus h_{n_S}

    ​ h_{n_S} = h_{n_C} \implies T_{C'} = T_C \oplus h_{n_C} \oplus h_{n_C}

    ​ T_{C'} = T_C, the one-time token of C have successfully been extracted

  • s7 - If K and n^1 are the same on both machines, T_S=T_C. Furthermore, if the time ids are the same (c.f. step s6) the 2 tokens should match.

Short formulas

​ The whole unscrambling process can be shortened into the following formula resulting in 0 if the client is authenticated.

​ T_{req} \oplus h(\mid \frac{T_{now}}{W}\mid - \| m_C - (\mid \frac{T_{now}}{W}\mid \mod 2) \|) \oplus f(K, n^1)

Practical Example

One-way algorithm

  • Lets consider our one-way function f(x, n^1) to always return x itself. By using this definition, we only have the time protection protocol "scrambling" the key K, it is for example only.

Warning

  • Always consider choosing a strong function f() for security.

Hash function

  • We will use the sha-128 algorithm as our hash function.

Warning

  • The sha-128 algorithm is no more secure !! I am using it only because its length fits well this document, newer hash functions have too long values impossible to be displayed properly.

Environment

  • Let K be the hexadecimal representation 83ff9f4e0d16d61727cbdf47d769fb707b652217
  • L=128 because of our hash function h()
  • Let n^1=2​ (i.e. 2 successful requests have already been sent)
  • Let W = 4 because we consider our maximum transmission time to 4 seconds.

Case 1: valid exchange (same window)

  • Let T_{now}=1523276226 on the client

  • Let T_{now} \in 1523276226+W=152327630 on the server

    ​

On the client

  • Process T_C = f(83ff9f4e0d16d61727cbdf47d769fb707b652217, 2)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217

  • Process n_C = \| \frac{1523276226}{4} \| = \mid 380819056.5 \mid = 380819056

  • Process m_C = 380819056 \mod 2 = 0

  • Process T_{req} = T_C \otimes h(n)$

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes h(380819056)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes c98851ec8e7751f14eee2880971d52c73b5791de

    =4a77cea2836187e66925f7c74074a9b74032b3c9

Request data

  • T_{req} = 4a77cea2836187e66925f7c74074a9b74032b3c9
  • m_C=0

On the server

  • Process T_S = f(83ff9f4e0d16d61727cbdf47d769fb707b652217, 2)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217

  • Process n' = \| \frac{152327630}{4} \| = \mid 380819057.5 \mid = 380819057

  • Process m_S = 380819057 \mod 2 = 1

  • Process n_S = 380819057 - \| 0 - 1 \| = 380819057 - 1 = 380819056

  • Process T_{C'} = 4a77cea2836187e66925f7c74074a9b74032b3c9 \otimes h(380819056)

    = 4a77cea2836187e66925f7c74074a9b74032b3c9 \otimes c98851ec8e7751f14eee2880971d52c73b5791de

    =83ff9f4e0d16d61727cbdf47d769fb707b652217%

    = T_S

    ​

\implies T_{C'} = T_{S} the client is authenticated, we can increment n^1=3.

Case 2: invalid exchange (next half-window)

  • Let T_{now}=1523276226 on the client

  • Let T_{now} \in 1523276226+W+\frac{W}{2}=1523276232 on the server

    ​

On the client

  • Process T_C = f(83ff9f4e0d16d61727cbdf47d769fb707b652217, 2)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217​

  • Process n_C = \| \frac{1523276226}{4} \| = \mid 380819056.5 \mid = 380819056

  • Process m_C = 380819056 \mod 2 = 0

  • Process T_{req} = T_C \otimes h(n_C)$

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes h(380819056)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes c98851ec8e7751f14eee2880971d52c73b5791de

    =4a77cea2836187e66925f7c74074a9b74032b3c9

Request data

  • T_{req} = 4a77cea2836187e66925f7c74074a9b74032b3c9
  • m_C=0

On the server

  • Process T_S = f(83ff9f4e0d16d61727cbdf47d769fb707b652217, 2)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217

  • Process n' = \| \frac{1523276232}{4} \| = \mid 380819058 \mid = 380819058

  • Process m_S = 380819058 \mod 2 = 0

  • Process n_S = 380819058 - \| 0 - 0' \| = 380819058 - 0 = 380819058

  • Process T_{C'} = 4a77cea2836187e66925f7c74074a9b74032b3c9 \otimes h(380819058)

    = 4a77cea2836187e66925f7c74074a9b74032b3c9 \otimes a86890d123a29c1115e7a2a9900d7f7a8b286103

    =e21f5e73a0c31bf77cc2556ed079d6cdcb1ad2ca

    \neq T_S

    ​

\implies T_{C'} \neq T_S the client is not authenticated, we do not increment n^1.

Case 3: invalid exchange (same window but wrong key)

  • Let T_{now}=1523276226 on the client

  • Let T_{now} \in 1523276226+W=152327630 on the server

    ​

On the client

  • Process T_C = f(secret\_key, 2)

    = h(secret\_key)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217

  • Process n_C = \| \frac{1523276226}{4} \| = \mid 380819056.5 \mid = 380819056

  • Process m_C = 380819056 \mod 2 = 0

  • Process T_{req} = T_C \otimes h(n)$

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes h(380819056)

    = 83ff9f4e0d16d61727cbdf47d769fb707b652217 \otimes c98851ec8e7751f14eee2880971d52c73b5791de

    =4a77cea2836187e66925f7c74074a9b74032b3c9

Request data

  • T_{req} = 4a77cea2836187e66925f7c74074a9b74032b3c9
  • m_C=0

On the server

  • Process T_S = f(435c07ed18d15b8896d21441f9189982191cba8b, 3) WRONG KEY

    = 435c07ed18d15b8896d21441f9189982191cba8b

  • Process n' = \| \frac{152327630}{4} \| = \mid 380819057.5 \mid = 380819057

  • Process m_S = 380819057 \mod 2 = 1

  • Process n_S = 380819057 - \| 0 - 1 \| = 380819057 - 1 = 380819056

  • Process T_{C'} = 435c07ed18d15b8896d21441f9189982191cba8b \otimes h(380819056)

    = 435c07ed18d15b8896d21441f9189982191cba8b \otimes c98851ec8e7751f14eee2880971d52c73b5791de

    =8ad4560196a60a79d83c3cc16e05cb45224b2b55

    \neq T_S

    ​

\implies T_{C'} \neq T_{S} the client is not authenticated, we do not can increment n^1.