Nicko van Someren:

> You could strengthen against the use of hardware by using a system
> that needed more memory and used functions such as multiply
> operations which are expensive in hardware but which CPU designers
> spend a lot of effort upon.

I agree. The point must be to inflate the gate count and prevent
parallelisation. The second part of this isn't too hard, but the
first is more difficult. It seems to me that there are two choices.

The first is to make the hash function itself very complicated, so it
takes a fair amount of memory to express it in software. This puts
hardware implementations at a disadvantage because gates are likely to
be in shorter supply than program memory.

The second possibility is to make the computation generate a large
number of intermediate data. One possibility might be a brute force
attack on a cipher which is iterated twice.

First you choose a work factor n. Then you select two random keys k1
and k2, of size n bits. You then encrypt a nonce under first k1 and
then k2.

As we know, this construction gives a total strength of n+1 bits, not
2n, because of the meet in the middle attack. However, the meet in
the middle attack generates a lot of intermediate results. This could
mean that the complexity in an FPGA would be O(2n) while the
complexity on a general purpose computer would be O(n+1). Of course
the constant of proportionality would favour the FPGA.

You could make this even worse for the hardware people by using a
cipher like RC4. RC4 would be a real pain to implement in hardware.

Eric Johansson:

> On the point about stolen stamps, I was planning on defeating that
> by making hashcash be a client to client protocol and the only thing
> intervening machines might do is validate that the stamp is present.

A general purpose end to end protocol would be quite beneficial I
think. There are lots of things you could usefully ask the recipient
of mail, such as preferred formats (plain text, HTML, Word document,
virus...).

-- 
Pete

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]