A plan for CAPTCHAs

I had the idea (I'm uncertain if it is original [pdf]) of mixing two distinct elements to make a better CAPTCHA. The problem is that there are essentially two ways to solve a CAPTCHA. The first is by designing some kind of image recognition system, this is an OCR problem and there are indications that nearly every major CAPTCHA has been broken. The other main avenue of attack seems to come down to paying people to crack them. This is a much tougher nut to crack because CAPTCHAs are not designed to prevent humans from cracking them; in some sense, this attack isn't a break of the system at all, but a design goal of CAPTCHAs. But much like the mathematician in that old joke, this definition of acceptable wouldn't sit well with some. The solution is to pose a question in such a way that is very hard for a computer to perceive but at the same time hard for a person to solve by herself. As an example, imagine a cryptographically hard problem posed in a way that a computer couldn't readily interpret, and a person would find difficult (or impossible) to solve by hand. This could be the source code for a simple discrete logarithm solver. The code would be obscured in the normal way that a CAPTCHA is (wavy text, visual noise, etc.) The user is instructed to type the code into a text box (where a built-in solver, client-side, can operate on it), and then use the result for entry into the protected resource. It would be easy to tune the toughness of the discrete log problem (randomly chosen of course) to generate any penalty you want. This penalty would cost an attacker any amount of CPU time that the challenger desires. By mixing a character-recognition task (that a human is good at) with a number-crunching task (which a computer is good at, but can be made arbitrarily CPU-intensive and thus slow) you protect from both types of attacks:

1. If an OCR program can read your text, they still must compute a computationally expensive value.
2. If humans are being used to circumvent the OCR task, a computer must be used to compute the expensive task as well, still incurring most of the penalty (by tweaking the exact type and hardness of the one-way function, this part can come to dominate the time needed for a successful break).

Some ideas on how to make the computation time more palatable for a legitimate user:

• Make this be the first question on a form that the user has to fill out.
• Grant the user provisional access to the site while the computation proceeds in the background.

Hex Clock

I was reading Hal's blog the other day when I thought that I'd try and implement a clock that uses the hexadecimal time that he talks about. I have seen a bunch of these so-called binary clocks that display the time is some nifty format (blinkenlights). The thing is, what they display is usually binary coded decimal (i.e. 1100:111011 = 12:59). Sometimes they even code each digit: 0001 0010:0101 1001! Hal defined the hexadecimal second to be 1/2^16 of a day, making 65,536 "hexeconds" per day. Since there are 86,400 seconds in a day, there are about 1.318 sec/hxs. Naturally, there are FF hexeconds in a "hexinute." A hexinute is 1/2^8 of a day, making each 337.5 seconds long, or 5.625 minutes (5 min, 37.5 sec). This leads to a nice property (besides being easily convertible to binary), A day then is recursive, there are 256 hxm per day and there are 256 hxs per hxm. Much better than 24 hours, with 60 minutes with 60 seconds! Who could remember that? You just have to get used to your clock displaying a time like: BE|EF (~64,440 seconds into your day or 5:54 PM, clearly not a vegetarian dinner time). Another thing that I thought about was the "stability" of a given digit. Each digit "stays put" for 16 times as long as the digit to it's right. The fastest-changing digit advances each ~1.318 second, to its left the 16's place advances each 16*1.318 = ~21 seconds. In the one's place in the hexinutes each advances 337.5 seconds (or 5.625 minutes), lastly, the most stable digit advances each every 90 minutes. That's great for measuring the orbital period of the space shuttle, each orbit is 10|00 long! That's my proposal for writing the time, by the way, for the programmers out there it will be evocative of a bitwise OR; if you think of the time as something like 0xAB00 | 0xCD. Without further ado:

hexclock.py

#!/usr/bin/env python
#
# Based on discussion here: http://halcanary.org/vv/2007/10/31/706/
#
# Copyright 2008 Chris Wilson.
#
# This program is free software: you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation, either version 3 of the License, or (at your
# option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
# Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program.  If not, see <http://www.gnu.org/licenses/>.

from Tkinter import *
from random import random
from time import sleep
from hs import hexarray, hexdisplay
import sys
import math
import getopt

master = Tk()

def usage():
    
    print """\nDislpay a Tk-based animated binary clock. The fastest pixel
blinks about once every 1.318 seconds, there are 2^16 such transitions
per day.

%s [options]

\t-h  --help This message
\t-s --size SIZE. make the display SIZE pixels on a side
\t-d --digits display digits in addition to the graphical binary
\t            representation of the time.
\t-f --foreground COLOR. the "lit up" pixels are this color.  
\t-b --background COLOR. the background pixels are this
\t            color.
\t-t --textcolor COLOR. the text will appear this color. Obviously,
\t            this option only makes sense with -d""" % sys.argv[0]
    sys.exit(1)

digits = False
HEIGHT = WIDTH = 400
on = "blue"
off = "black"
textcolor = "white"
try:
    opts, args = getopt.getopt(sys.argv[1:],
                               "hs:df:b:t:", ["help", "size=", "digits",
                                              "foreground","background",
                                              "textcolor"])
                                          
except getopt.GetoptError, err:
    print str(err)
    usage()
for o, a in opts:
    if o in ("-d", "--digits"):
        digits = True
    elif o in ("-s", "--size"):
        try:
            HEIGHT = WIDTH = int(a)
        except:
            usage()
    elif o in ("-f", "--foreground"):
        on = a
    elif o in ("-b", "--background"):
        off = a
    elif o in ("-h", "--help"):
        usage()
    elif o in ("-t", "--textcolor"):
        textcolor = a
    else:
        usage()

fs = int(math.sqrt(HEIGHT))

w = Canvas(master, width=WIDTH, height=HEIGHT)

def create_grid(canvas, grid, height, width):
    ulx = 0
    uly = 0
    xdimen = width/4
    ydimen = height/4
    item_array = list()
    for square in grid:
            if square == 1:
                i = canvas.create_rectangle(ulx, uly, ulx+xdimen, uly+ydimen,
                                    fill=on)
            else:
                i = canvas.create_rectangle(ulx, uly, ulx+xdimen, uly+ydimen,
                                                    fill=off)
            item_array.append(i)
            if ulx == (width-xdimen):
                uly = uly + ydimen
                ulx = 0
            else:
                ulx = ulx + xdimen
    return item_array


def update(canvas, items, grid):
    for i in range(len(items)):
        if grid[i] == 1:
            canvas.itemconfig(items[i], fill=on)
        else:
            canvas.itemconfig(items[i], fill=off)

if digits:
    def create_timestamp(canvas,h,w):
        return canvas.create_text(h/2,w/2,text=hexdisplay(),fill=textcolor,
                                  justify=CENTER, font="Courier %d bold" % fs)

    def update_time(canvas,text_handle):
        canvas.itemconfig(text_handle, text=hexdisplay())
else:
    def create_timestamp(canvas,h,w): pass
    def update_time(canvas,text_handle): pass
    

items = create_grid(w, hexarray(), HEIGHT, WIDTH)
text = create_timestamp(w, HEIGHT, WIDTH)
w.pack()
while True:
    update(w, items, hexarray())
    update_time(w,text)
    w.update_idletasks()    # redraw
    w.update()              # process events
    sleep(1)
mainloop()

hs.py

#!/usr/bin/env python
#
# Based on blog post on: http://halcanary.org/vv/2007/10/31/706/
#
# Copyright 2008 Chris Wilson
#
# This program is free software: you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation, either version 3 of the License, or (at your
# option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
# Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program.  If not, see <http://www.gnu.org/licenses/>.

import math, time

# hex timekeeping
hs = 86400.0/(2**16)    # there are 65,536 hexeconds in a day ~1.318 sec.
hm = 86400.0/(2**8) # there are 256 hexeconds in hexinute  ~337.5 sec

# I'm not defining an hour since there wouldn't be many of them (and they'd
# be redundant, with a hexinute being ~5.6 mins, these are pretty stable.
# Plus, hackers are more precise anyway ;) ).

def day_secs():
    h, m, s = time.localtime()[3:6]
    return h*3600 + m * 60 + s

def hextime():
    s = day_secs()
    hexmin = int(math.floor(s/hm))
    s = s - (hexmin*hm)
    hexsec = int(math.floor(s/hs))
    return hexmin,hexsec

def hexarray():
    hexmin, hexsec = hextime()
    total = (hexmin << 8) + hexsec
    out = list()
    for x in range(16):
        out.append(total & 1)
        total = total>>1
    out.reverse()
    return out

def hexdisplay():
    return "%02X:%02X" % hextime()

def bindisplay():
    hm, hs = hextime()
    n1, n2 = nybbles(hm)
    n3, n4 = nybbles(hs)
    format_args = map(to_bin, (n1, n2, n3, n4))
    return "%s\n%s\n%s\n%s" %  tuple(format_args)

def nybbles(byte):
    lower = byte&15
    upper = (byte>>4)&15
    return upper, lower

def to_bin(nybble):
    out = list()
    for x in range(4):
        out.append(str(1 & nybble))
        nybble = nybble>>1
    out.reverse()
    return " ".join(out)
    
def _test():
    print "16", nybbles(16)
    u, l = nybbles(16)
    print "bin:",u,l, to_bin(u), to_bin(l)

def run_clock():
    import os
    while True:
        os.system("clear")
        print bindisplay()
        print "("+hexdisplay()+")"
        time.sleep(1)

if __name__ == "__main__":
    #_test()      
    run_clock()