Bombe Machine on an FPGA | Hacker News Reader

Bombe Machine on an FPGA

people.ece.cornell.edu

83 pointsvha317 comments

Thanks for posting, this can be a fun and excellent entry level project for newcomers to embedded system.

Having said that, I believe that the DE1 board being used in the project is not the same as DE1 board being used in the excellent book by Prof Hamblen of Georgia Tech [1]. I'd highly recommend this book if you're starting out but the tools and the software are outdated because it is already more than a decade old.

The manufacturer of Altera embedded system boards Terasic, bizarrely decided that they wanted to re-use and retain the DE1 name although there are already DE1 and DE2 boards produced by them before this new DE1 board.

[1]Rapid Prototyping of Digital Systems: SOPC Edition:

https://link.springer.com/book/10.1007/978-0-387-72671-7

The board used in this project is the DE1-SoC, which is not the same as the DE1, you're right. They have different names, so I'm not sure where the confusion comes from. they definitely could have named it better, however.

I think you are sure you know where the confusion comes from. You admitted it in your last phrase?

"lightbulb" and "lightning" both start with the same 5 letters, and no one confuses those.

I just think, in general, people could be better at naming things.

We could probably go probably go deeper into this. ;-) Deep learned vs shallow learned something something. But I understand what you are saying. cheers!

I would like to have seen the decryption of a known WWII German message to verify that all the little details are correct.

The Bombe doesn't decrypt Enigma encrypted messages.

What it does is figure out which keys (initial rotor positions and plugboard settings) are logically consistent with the information you have, eliminating the bulk of possibilities and leaving humans to do the remaining work. In an actual Bombe (or the replica at Bletchley today) this results in a "stop" - the machine trying every possibility halts because the combination it's trying now isn't logically impossible. Humans then take the result of the "stop" and check whether they can decrypt the message, the Bombe can continue searching for other possibilities.

The logical inconsistency results from the fact that Enigma guarantees that any symbol X will encrypt to some different symbol. It will never encrypt to X. If that seems to happen it's an inconsistency and this can't be the correct key, try again.

This is a grave problem with designs like Enigma, and it's one reason why Enigma is the dying gasp of this approach, if you've got something like Lorenz you can't rule out any of the keys by logical contradiction like the Bombes, just as you can't with modern ciphers.

To elaborate a little further:

The attack this device implements requires you to have a run of known plaintext and its corresponding ciphertext, with correct alignment between the two.

The bombe searches for keying configurations that could have produced that encipherment. When you find one, you can go test if it decrypts the rest of the message into german or gibberish.

Excellent summary and explanation. Just to add; imagine you know the start of a message is the weather forecast for the day, or the date, or fixed greeting (or for something more modern - a known file header).

The "known plaintext" might be something you can observe/predict.

A more concrete (and possibly apocryphal) example is if the message ends like so:

"XXXX XXXXXX"

Fair odds that's "Heil Hitler"

Well there were no spaces in enigma messages, but you can use the aforementioned property that no letter encrypts to itself to look for possible plain-texts and figure out their alignment.

e.g. "?E????????" is not HEILHITLER, at least not with that alignment.

IIRC one cryptanalyst realised that the first 4 characters in ciphers from one particular operator never included the letter 'L'. They deduced that that operator always sent 4 Ls as an initial test, since L was on the right hand side of the keyboard and therefore the easiest key to hit for a right-hander. With LLLL as your known plaintext, decoding that operator's messages became a lot easier!

Let's not forget one German message, one time, was undecoded to this very day. A paranoid conspiracy theorist of course, how could anyone doubt the security of the Enigma? How could anybody be onto Blechley Park's shit? A troll, if you will, in the forties.

I divine he rolled dice.

JCRSAJTGSJEYEXYKKZZSHVUOCTRFRCRPFVYPLKPPLGRHVVBBTBRSXSWXGGTYTVKQNGSCHVGF

This is of course a very short message, and almost certainly "broken" in some sense, e.g. perhaps part of it is missing or the operator mistakenly changed something part way through. It was sent towards the end of the war, the U-boat which sent it is being chased at the time and will be sunk before Germany surrenders a few days later.

Dice-rolling seems unlikely as humans think repetitions like "KKZZ" or "VVBB" seen in this message are "wrong" and "don't look random enough" which is why you can't let humans do this work. Also the radio operators probably have better things to do than risk getting executed for wasting resources on such games at a point where Germany has definitely lost the war.

On the other hand, screw-ups due to being stressed by people trying to kill you in a war you're probably aware you've lost already are very likely. I'd be a complete wreck if I was that operator.

Well it probably tied up a lot of resources at Bletchley Park. I don't think the German screwed up.

But I can decode it myself. Says "FUCKYOUFUCKYOUFUCKYOU" to the enemy.

Students implemented a Bombe Machine on a DE1-SoC.

Does anybody know if something like this could be implemented using a library like Jax?

It's a bit outside my area, but I've seen a few encryption, or maybe signature breaking tools that somehow managed to apply some very cool linear algebra to guess at the bits directly using the gradient of the encryption function (can't find a nice link now)

Reply on news.ycombinator.com