Skip to main content

Posts

Showing posts from April, 2013

How I coded in 1985

Back in 1985 I worked on the computerization of a machine designed to stick labels on bottles. The company that made the machines was using electromechanical controls to spool labels off a reel and onto products (such as bottles of shampoo) passing by on a conveyor. The entire thing needed to work with mm accuracy because consumers don't like labels that aren't perfectly aligned.

Unfortunately, electromechanical controls aren't as flexible as computer controls and so the company had contracted a local technical college (where I was studying electronics) to prototype computer control using a KIM-1. Another student had put together the machine with a conveyor, a mechanism for delivering the labels, control of stepper motors, and infrared sensors for detecting labels and products.


My job was to write the software in 6502 assembly. Unfortunately, there wasn't an assembler and the KIM-1 just had a hex keypad and small display. So, it meant writing the code by hand, hand as…

The minimum coin problem (with prize)

I have in my pocket the following British coins: one £2, two £1, two 50p, three 20p, one 10p, two 5p, two 2p and two 1p. I wish to buy a copy of today's paper at a cost of £1.70.

What is the maximum number of coins I can use to pay for the paper? With the restriction that I pay in a reasonable manner (e.g. I could give exactly £1.70 or an amount greater than that but without giving extraneous coins: e.g. giving the seller all the coins would not be acceptable, but giving him one £1 an two 50ps and expecting 30p in change is OK). The reasonable manner is simply: if I give the seller a set of coins he should not be able to return any to me without the sum of the remaining coins dropping below £1.70.

Looks like it's: two 50p, three 20p, one 5p, two 2p and one 1p. That gives away 9 coins from the 15 coins I have.

The general statement of this problem is as follows.  There are \(n\) coins in a currency: \(d_0\) to \(d_{n-1}\) are the denominations of the coins (normalize all to a …

Update on Go 1.1 crypto performance

Some time ago I integrated OpenSSL's MD5, SHA1 and RC4 functions into Go because Go's native implementations were slow. The Go team has made great strides in fixing this (for 386 and AMD64) with Go 1.1 with faster RC4, SHA1 and MD5.

Rerunning my tester program shows the following:

MD5SHA1RC4Native Go (pre-1.1)404 MB/s123 MB/s111 MB/sVia OpenSSL607 MB/s636 MB/s744 MB/sGo 1.1602 MB/s383 MB/s662 MB/sGo 1.1 vs. OpenSSL0.99x0.6x0.89x
So, the Go team has essentially reached parity with OpenSSL on MD5, is close on RC4, but could still do work to get the SHA1 performance close. (All testing of Go 1.1 was done with 84e21a8c2137 on Ubuntu 12.04 2.4Ghz Intel Core i7; 4 cores with 2GB of RAM).

As a further comparison Go's own benchmark tests shows the following.

MD5, via OpenSSL: BenchmarkHash8K (593 MB/s), BenchmarkHash8KUnaligned (581 MB/s); MD5, Go 1.1: BenchmarkHash8K (584 MB/s), BenchmarkHash8KUnaligned (589 MB/s)

SHA1, via OpenSSL: BenchmarkHash8K (606 MB/s); SHA1, Go 1.1: Benchm…

The importance of open code

Last February myself, Professor Darrel Ince and Professor Les Hatton had a paper published in Nature arguing for openness in the code used for scientific papers. The paper is called The Case for Open Computer Programs.

In a coda to that piece Darrel wrote the following:
Our intent was not to criticise; indeed we have admiration for scientists who have to cope with the difficult problems we describe. One thesis of the article is that errors occur within many systems and does not arise from incompetence or lack of care. Developing a computer system is a complex process and problems will, almost invariably, occur. By providing the ability for code to be easily perused improvement will happen. This is the result detailed in both the boxes in the article: the Met Office data is more accurate, admittedly by a small amount, and because of feedback to developers the geophysical software was considerably improved. Recently, an important paper in economics has been in the news because its conc…

PDF and eBook version of "A non-mathematical introduction to one-way functions and their use in securing passwords"

My four blog posts on this subject (starting here) have been very popular with well over 100,000 page views in four days. Because of their popularity, and because some people may wish to share the story of Alice and Bob in a different format I've put together an 11 page PDF and eBook containing and edited, illustrated and slightly expanded version of the posts.

You can buy it for $1.99 as a PDF or as ePub. It's 11 pages of detailed explanation for less than a latte!


It's for sale, rather than free, as a way of supporting this blog. There are no ads here and I intend to keep it that way.

Bob's wife Carla lends a speedy mind

This is part 4 of a series of blog posts about one-way functions and their use in securing passwords. If you have not read the other parts start here.

Bob doesn't usually let his wife Carla help him with crosswords. That's because, due to some unusual quirk of brain topology, Carla is a savant and she's memorized the entire Shorter Oxford English Dictionary. So, she's able to recall the definition of any word almost instantly. But, like many people with similar abilities, her talent is limited, she can't perform the opposite: given a definition she's just as slow as her husband at finding the corresponding word.

Carla's ability means that she can calculate Alice's one-way function from crossword solution through five definitions very quickly. She's about 100 times faster than Bob because she has no need to find words in the physical book. But she's no faster at performing the reverse.

Alice calls and Bob challenges her for the solution to 25A. …

Alice strikes back against Bob's 'reverse dictionary'

This is part 3 of a series of blog posts about one way functions and their use in securing passwords. If you haven't read the first two parts start here.

Now Alice is angry. She realizes that Bob has defeated her clever one way function with his reverse dictionary and that now that Bob's created it he can use it over and again. All his initial effort will be amortized day after day as he steals crossword answers from Alice.

And so Alice strikes back.

The following day she calls Bob and says that she's making a small change to her one way function. It'll still involve looking up five words in the dictionary and following the definitions, but the order will change. In fact, she'll get to pick the order.

In the original scheme the first word of the first definition was used, the second word of the second and so on. Alice proposes to verify that she knows the answer to 4D (TANGLE) by giving Bob the final word (just as before) but also five numbers indicating which wor…

Possible solutions to Leo Marks' security conundrum

A couple of years ago I wrote about a security conundrum left by Leo Marks in his excellent book Between Silk and Cyanide. The conundrum appears on this page:

And specifically, the sentences: Before he left he was briefed by signals to give MANELAUS an identity check. This was in such a form that PANDARUS himself, if caught later by the enemy, would be unable to remember it. But Marks doesn't reveal how it worked having been told at the time of publication that it must remain a secret. My 2011 appeal for assistance resulted in a number of interesting ideas (read the original comments).  I most liked the idea that MANELAUS might be able to read music and PANDARUS might not. So PANDARUS could have carried a code word written out as notes on a stave. MANELAUS could have turned these back into the actual security code word either via the letter notation (A B C D E F G H) or the solf├Ęge (Do Re Mi Fa Sol La Ti Do). Of course, the general version of this is for PANDARUS to take with him…

Bob outsmarts Alice's 'one way function'

In a previous blog post I described a one way function using a dictionary. Read that post before reading this one.

That night Bob realizes he's found a way to outsmart Alice and not bother doing the crossword at all. The next day, he waits for Alice's gloating call and starts asking her about clues in the crossword. As before Alice replies with words that have passed through her one way function, but now Bob manages to fill in the complete crossword without any thinking, searching or delay.

Late the night before Bob had a brainwave: it's easy to go forward through Alice's one way function and hard to go backwards, but there only so many words in the dictionary. So, instead of waiting for Alice to give him a word and then be forced to undertake the nearly impossible task of working backwards through all the possible definitions containing that word, Bob realizes that he can just build his own reverse dictionary. A dictionary in which he can look up a word Alice gives h…

A non-mathematical explanation of one way functions

Alice and Bob are crossword enthusiasts. Every morning they rush to complete the Daily Telegraph cryptic crossword. One morning Alice finishes the crossword and telephones Bob to gloat. Bob challenges her by asking for the solution to 21D as proof that she's completed the entire thing.

Alice knows the answer (FOLIO) but doesn't want to tell Bob because that would give away an answer that Bob might not yet have. And she knows that Bob may ask her for more solutions as further challenges, and she really doesn't want to help him complete the crossword.

So, she proposes to Bob that they both get out their Shorter Oxford English Dictionaries. Alice proceeds as follows:

1. She finds the word FOLIO and its definition: "an individual leaf of paper or parchment, either loose as one of a series or forming part of a bound volume, which is numbered on the recto or front side only."  She finds the first word (that's not an article) from the definition, in this case INDIV…

lulip: a line-level profiler for LuaJIT

If you are doing profiling of code written in Lua and running in LuaJIT it can be useful to know where your code is 'hot'. Using the debug.sethook I've put together a small profiler that outputs an HTML page showing execution times on a per-line basis.  It's called lulip.

Usage is simple:
And it creates a HTML showing the lines that consume the most time with the total time in ms, the number of times the line was executed and the line itself colorized.

For example,

file:linecountelapsed (ms)linewr.lua:11292822.455hash = ngx_sha1_bin(value)wr.lua:1172428470.849captures, err = ngx_re_match(v, p)wr.lua:11973762207.487x = string_find(v, f)wr.lua:212157154.386string_gsub(v, "//([^/]+)//", "%1")wr.lua:1196378887.475for i=1,g() dowr.lua:1158156352.906if not f() then
LuaJIT is required because I used the FFI interface to get interface to the gettimeofday function to get microsecond timing. LuaJIT makes this trivial to do:


Performance of array creation in Lua

The Lua 5.1 Optimization Notes say: "Short inline expressions can be faster than function calls. t[#t+1] = 0 is faster than table.insert(t, 0)." But the question is what's the fastest way to insert a number of items into a table (as an array).

Naive base test case (naive.lua): using Lua 5.2 is takes (average of 5 runs) 1718ms.
Make table.insert into a local (local.lua): using Lua 5.2 is takes (average of 5 runs) 1408ms (vs. base 82.0%).
Following the advice from the optimization tips (optimized.lua): using Lua 5.2 is takes (average of 5 runs) 1180ms (vs. base 68.7%)
Using a simple implementation with a counter (counter.lua): using Lua 5.2 is takes (average of 5 runs) 193ms (vs. base 11.2%)

So, the rather simplistic implementation with a counter is almost 9x faster than the naive implementation and it's 6x faster than the advice from the optimization page.

Moral: it pays to measure.

Switching to the most recent LuaJIT gives the following times: naive base case: 845ms…