Hacker News Reader

Comment by Sohcahtoa82 | Hacker News Reader

> Opening an encrypted connection means one very large multiplication. On a 4.77 MHz 8088 it takes minutes.

I've done it.

It took a lot of loop unrolling and optimizations in order to get the TLS 1.2 handshake to complete before the server timed out the connection, but I've successfully gotten it to work, and with only 384 KB of RAM.

The implementation doesn't verify the server certificate (would certainly take too long), but it successfully performs an HTTPS request to Wikipedia as a proof-of-concept.

One of these days I'll clean up the code and post it here.

View on HN

I‘ve recently tried implementing the Noise protocol on a 7.8 MHz 68000, while it runs in 10 seconds I don’t think there is a way to make it constant time without using addition and running an order of magnitude more slowly :(

MULU operations are not constant time but depend on popcount. That has an easy work around just also do the MULU of the bitwise inverse, both instructions sum to a constant cycle count.

The brick wall I hit is related to the Macintosh SE ram being shared between CPU and video system. Every few cycles the CPU stalls instruction fetching, which turns the both MULUs together take the same amount of time each time into there is slowdown depending on the popcount of the first instruction.

I don’t know if anyone has any solution for this, there is prefetching of one instruction so all should be well, but it seems like the cpu stalls the in progress instruction if the prefetch is stalled.

If there is a portion of the frame where the cycle stealing doesn't occur, e.g. during vertical blanking, maybe you can schedule your multiplications to only happen there. It will not strictly be constant time of course, and it will be slower, but timing would be invariant of input. Timing characteristics would instead reveal to the attacker where the raster beam was when the calculation started :)

That’s a great idea but that takes away a lot of compute! I didn’t pursue this further since at that point we might as well do the adds vs muls.

I thought about calculating the worst case execution time by hand and than just doing a literal report solution on a timer after time has passed

The issue with that strategy is that I would like the OS to stay responsive (and there is interrupts that fall into that time frame) so could overshoot the budget and then we’re back to square zero.

I think at this point I probably have no choice other than unrolling it into addition :(

There is mitigations for those kind of things that make delta analysis impossible but I would REALLY just like the perfect solution that doesn’t depend on the secret for timing at all.

and with only 384 KB of RAM.

A 2048-bit RSA key is 256 bytes. A 256-bit symmetric key is 32 bytes and ECDH keys are roughly the same size. The state size of AES is 16 bytes and its S-box is 256 bytes. Efficient implementations use only a few KB of state. The vast majority of cryptographic algorithms just aren't that big, relatively speaking; although as you mention, they are very computationally intense. Hash states are in the dozens to low hundreds of bytes. For TLS implementation, the record buffers are probably going to use the most RAM; 16K each direction + additional overhead.

So the loop unrolling must have increased the resident code size quite considerably, on the order of two to three hundred kilobytes?

That and a TCP/IP stack.

Better off just using http://frogfind.com/

Reply on news.ycombinator.com