Challenge 3: Identification

One Time Passwords (OTPs) are passwords used once, that are either sent on a separate channel (e.g. as sms messages) or generated by dedicated devices and smartphone apps.  When generated in software they are usually computed starting from a user PIN (Personal Identification Number) that is also known by the server in order to validate the user’s OTPs. More precisely,

  1. the app asks the user to insert the secret PIN;
  2. the app uses the PIN to generate the OTP. Some time-variant parameter is used to make the OTP always different, e.g., a timestamp;
  3. the user sends the OTP to the server;
  4. the server knows the user’s PIN and the time-variant parameter: it re-generates the OTP and checks that it is the same as the one sent by the user.

Security property

OTP generators should guarantee that, even if some OTPs are leaked, the attacker won’t be able to forge next OTPs. In other words, secrecy of next OTPs should be preserved even if previous OTPs has been leaked. This property is what makes OTPs stronger than passwords: a password, once intercepted, can be easily reused. 

Goal

The Acme Corporation wants to adopt a new OPT generator. The algorithm is based on SHA-256 hash, a state-of-the-art secure one-way function. They are so confident about the security of their scheme that they have published three consecutive OTPs generated starting from a secret 8 digits PIN and and they are challenging security experts to break the scheme.

OTP1 = 754104, generated on 8 April 2020 at 21:45
OTP2 = 353471, generated on 8 April 2020 at 21:46
OTP3 = 084633, generated on 8 April 2020 at 21:47

Can you find the secret 8 digits PIN and prove that Acme’s scheme is weak? Can you also suggest a fix? (notice that the 8 digits format of the PIN is a usability requirement that cannot be changed)

import time
import hashlib

def otp(pin):
  '''The Acme Coorporation OTP generator.

  This generator is based on SHA256, a secure one-way hash so to prevent
  that the pin value is computed starting from the hash.
  Moreover the hash is cut to 6 (decimalized) bytes, which makes inversion 
  even harder!
  '''
  size = 6
  otp = ''

  # timestamp changes every minute to allow for synchronization
  t = time.localtime(time.time())
  timestamp = '{}-{}-{}-{}:{}'.format(t.tm_year,t.tm_mon,t.tm_mday,t.tm_hour,t.tm_min)

  # One-way function, to prevent computing PIN from OTP!
  h = hashlib.sha256((pin+timestamp).encode()).digest()

  for i in range(size):
    # decimalize i-th byte and add it to the otp
    digit = h[i] % 10 
    otp += str(digit)
  return otp

Bonus

Send me on slack the script used to the attack with a detailed description of how you solved the challenge by 11 November 2020 to get a 0.5 bonus on the final grade! In case you also suggest a valid fix Acme will award you with an additional 0.2 bonus! In bocca al lupo!  😁