hashchain.py

#!/usr/bin/env python

class HashChain(object):
  """A chain of hash values that can be traversed backwards

  A hash chain is a sequence of the form H(s), H(H(s)), H(H(H(s))),
  where 'H' is a one-way hash function and s is the initial seed.
  This class generates a hash chain and allows you to traverse it
  in reverse order (e.g., from H(H(H(s))), to H(H(s)), H(s)).
  Construction requires O(N) time (where N is the length of the
  hash chain).  Preparing the next (previous) value requires
  O(log(N)) time.  The space requirement is also O(log(N)).
  """

  def __init__(self, bits,
               oneway = (lambda obj: obj), seed = None,
               recorder = (lambda _: None)):
    """Initialize the hash chain

    bits -- Base 2 logarithm of the length of the chain
    oneway -- Hash function to generate the chain
    seed -- Initial value for the hash function
    recorder -- logging function to record steps for analysis
    """

    state = []
    pos = (1 << bits)
    val = seed
    while pos >= 0:
      if (pos & (pos + 1)) == 0:
        state.append((pos, val))
      pos -= 1
      val = oneway(val)
    state.reverse()

    self.__bits = bits
    self.__oneway = oneway
    self.__state = state
    self.__recorder = recorder

  @property
  def initial_bits(self):
    """Base 2 logarithm of the initial chain length"""
    return self.__bits

  @property
  def internal_state(self):
    """A list containing all of the stored chain values"""
    return self.__state

  @property
  def exhausted(self):
    """True iff the chain is empty"""
    return not self.__state


  @property
  def next_value(self):
    return self.__state[0][1]

  def prepare_next_value(self):
    pos = self.__state[0][0]

    ## Recursive helper function.  state_pos is the index into
    ## the state array.  It's basically an interator over the state.
    ## We return it from recursive calls because we can't destructively
    ## increment it.  left and right geometrically zoom in on pos.
    ## The state is logically a linked list (the only operations I use
    ## are iterating forward and inserting an element before the iterator),
    ## but I store it as a Python list for convenience, which technically
    ## breaks the O(log(N)) guarantee, but this is just a demonstration of
    ## the algorithm.

    def prepare(state_pos, left, right):
      ## The start of a block is a special case.
      ## All points in the block stay.
      if pos == left:
        while state_pos < len(self.__state) and \
            self.__state[state_pos][0] < right:
          self.__recorder(('stay', pos, self.__state[state_pos][0]))
          state_pos += 1
        return state_pos

      ## If we are to the right of the midpoint, the left is all done.
      ## Just tail-recur on the right.
      mid = (right+left)/2
      if pos >= mid:
        return prepare(state_pos, mid, right)

      ## Otherwise, recur on the left before advancing the right.
      state_pos = prepare(state_pos, left, mid)

      ## The far-left hash on the right half advances down toward the left,
      ## splitting off a "breadcrumb" if we are at a power of two minus one.
      mover = self.__state[state_pos]
      moved = (self.__oneway(mover[0]) - 1, self.__oneway(mover[1]))
      offset = mover[0] - mid
      split = (offset & (offset + 1)) == 0
      if split:
        self.__recorder(('split', pos, mover[0]))
        self.__state[state_pos:state_pos] = [moved]
      else:
        self.__recorder(('move', pos, mover[0]))
        self.__state[state_pos] = moved
      state_pos += 1

      ## The rest of the hashes just stay put.
      while state_pos < len(self.__state) and \
          self.__state[state_pos][0] < right:
        self.__recorder(('stay', pos, self.__state[state_pos][0]))
        state_pos += 1

      return state_pos

    self.__recorder(('used', pos, pos))
    del self.__state[0]
    prepare(0, 0, 1 << self.__bits)

otpa_tree.py

#!/usr/bin/env python

def main():
  import logging

  from optparse import OptionParser
  parser = OptionParser()
  parser.add_option("--bits", default=8, type='int', help="password bits")
  parser.add_option("--scale", default=1, type='int', help="image scale")
  parser.add_option("--ouput", default="otpa.png", help="output file")
  (options, args) = parser.parse_args()

  from PIL import Image, ImageDraw
  img_dim = (1 << options.bits) * options.scale
  image = Image.new('RGB', (img_dim, img_dim), 'white')
  draw = ImageDraw.Draw(image)
  draw.line([(0,0), (img_dim + 0 , img_dim + 0)], fill='red')
  draw.line([(1,0), (img_dim + 1 , img_dim + 0)], fill='red')
  draw.line([(0,1), (img_dim + 0 , img_dim + 1)], fill='red')

  def recorder(args):
    typ, time, pos = args
    start = (pos * options.scale, time * options.scale)

    if typ == 'split':
      recorder(('move', time, pos))
      recorder(('stay', time, pos))
    elif typ == 'used':
      draw.line([start, start], fill='black')
    elif typ in ('move', 'stay'):
      if typ == 'stay':
        endx = pos * options.scale
      else:
        endx = (pos-1) * options.scale + 1
      end = (endx, (time+1) * options.scale - 1)
      draw.line([start, end], fill='black')
    else:
      logging.warning("Unkown operation type: '%s'" % typ)

  import hashchain
  passwords = hashchain.HashChain(options.bits, recorder = recorder)
  while not passwords.exhausted:
    passwords.prepare_next_value()
  image.save(options.ouput)


if __name__ == '__main__':
  main()

otpa_ui.py

#!/usr/bin/env python
import wx

# Application-Specific Event Identifiers
ID_Step  = wx.ID_HIGHEST + 1
ID_Anim  = wx.ID_HIGHEST + 2


class OtpaApp(wx.App):
  def OnInit(self):
    from optparse import OptionParser
    parser = OptionParser()
    parser.add_option("--bits", default=8, type='int', help="password bits")
    parser.add_option("--xscale", default=1, type='int', help="image scale")
    parser.add_option("--yscale", default=64, type='int', help="image scale")
    parser.add_option("--delay", default=250, type='int', help="animation delay in ms")
    (options, args) = parser.parse_args()

    frame = OtpaFrame(None, wx.ID_ANY, "One-time Password Algorithm", options)
    frame.Show(True)
    self.SetTopWindow(frame)
    return True


class OtpaFrame(wx.Frame):
  def __init__(self, parent, id, title, options):
    wx.Frame.__init__(
        self, parent, id, title,
        style = wx.DEFAULT_FRAME_STYLE)

    self.__options = options

    self.prepare_chain()
    self.register_event_handlers()
    self.build_main_window()


  def prepare_chain(self):
    import hashchain
    self.__chain = hashchain.HashChain(self.__options.bits)

  def register_event_handlers(self):
    self.Bind(wx.EVT_BUTTON, self.OnButton)
    self.Bind(wx.EVT_TIMER, self.OnTimer)

    self.__anim_timer = wx.Timer(self)

  def build_main_window(self):
    main_sizer = wx.BoxSizer(wx.VERTICAL)
    info_sizer = wx.BoxSizer(wx.HORIZONTAL)
    main_panel = wx.Panel(self, wx.ID_ANY)

    info_sizer.Add(wx.Button(main_panel, ID_Step, "Step"    ))
    info_sizer.Add(wx.Button(main_panel, ID_Anim, "Animate" ))

    main_sizer.Add(info_sizer, border=4, flag=wx.ALL)

    self.__otpa_status = OtpaStatusDisplay(main_panel,
        self.__chain, self.__options.xscale, self.__options.yscale)
    main_sizer.Add(self.__otpa_status)

    main_panel.SetSizerAndFit(main_sizer)
    main_sizer.Fit(self)
    self.AutoLayout = True

  def OnButton(self, event):
    if event.GetId() == ID_Step:
      self.step()
    if event.GetId() == ID_Anim:
      self.__anim_timer.Start(self.__options.delay)

  def OnTimer(self, event):
    self.step()

  def step(self):
    if not self.__chain.exhausted:
      self.__chain.prepare_next_value()
      self.__otpa_status.Refresh()


class OtpaStatusDisplay(wx.Panel):
  def __init__(self, parent, chain, xscale, yscale):
    wx.Panel.__init__(
        self, parent,
        size = wx.Size((1 << chain.initial_bits) * xscale, yscale))

    self.__chain = chain
    self.__xscale = xscale
    self.__yscale = yscale

    self.__colours = {}
    for cname in ['red', 'green', 'blue', 'black']:
      colour = wx.NamedColour(cname)
      self.__colours[cname] = (wx.Pen(colour), wx.Brush(colour))

    self.BackgroundColour = wx.NamedColour('white')
    self.Bind(wx.EVT_PAINT, self.OnPaint)

  def set_colour(self, dc, colour):
    pen, brush = self.__colours[colour]
    dc.Pen = pen
    dc.Brush = brush

  def OnPaint(self, event):
    ## The background should be cleared by Refresh() already.
    dc = wx.PaintDC(self)
    self.set_colour(dc, 'black')
    for pos, k in self.__chain.internal_state:
      dc.DrawRectangle(pos * self.__xscale, 0, self.__xscale, self.__yscale)



if __name__ == '__main__':
  OtpaApp().MainLoop()