[rusk]

>Entries were posted as Twitter replies and DMs, containing only the PRG byte-length and an MD5 hash of the PRG file.

This is clever. So basically rather than getting bogged down reviewing submissions you just pick a winner and then validate post-hoc! (because when you win the hash of your code has to match the one you submitted)

[saagarjha]

I wonder if you could brute force a particular solution with that information.

[stjo]

I would say no. 34 bytes is 256^32=7588550360256754183279148073529370729071901715047420004889892225542594864082845696 combinations, and even if you could easily narrow it down to only valid programs you would still need to simulate it, which is way slower than computing a hash.

[saagarjha]

Only a fraction of those would be reasonable programs, and you can test almost all of them immediately by computing a MD5 hash.

[userbinator]

34 bytes is equivalent to bruteforcing a 272-bit key. It's already physically impossible to do that for a 256-bit key even if you ignore everything other than incrementing the key counter itself:

https://pthree.org/2016/06/19/the-physics-of-brute-force/

[saagarjha]

But as I said, you’re not brute forcing the entire key space because you likely have an idea of at least some of the bits.

[janekm]

Or, you could evaluate whether said program draws the crossed lines in an emulator. Might not take that much longer than calculating the hash... That makes this kind of an interesting "Genetic Programming" challenge... The solution space is "only" 29 bytes long...

[IcePic]

I don't think that would be this quick either. Since the code might/will mess up zeropage and/or other dataareas in use by the C64 basic, you would have to wipe it to a known state for each test, which almost means "boot up the KERNAL and let it run complete INIT".

Not that even this have to take a long while on a 3GHz computer running full speed, but doing it 2^272 times ...

[saagarjha]

> you would have to wipe it to a known state for each test, which almost means "boot up the KERNAL and let it run complete INIT"

FWIW, if I were actually doing this I’d run it in a emulator and “save” the initial state to restore for the every test.

[FartyMcFarter]

One way to work around that is to allow authors to include comments in the code that gets hashed.

(I'm not sure if this particular competition did that)

[rusk]

are you talking about padding it out to provoke a collision?

Remember, that at the end of the day, you still have to have actual working code …

[FartyMcFarter]

No - what I mean is that if someone is worried that their code will be derived from their published hash by someone doing a brute-force attack, they can prevent (or make much harder) this brute-force attack by having comments in their source code.

I'm assuming here that the hashed string is the source code rather than the machine code.

[rusk]

Ahhh - a salt

[NieDzejkob]

I guess one should use something more expensive to compute, like a KDF.