I don’t understand this post at all. In real life, what matters is how long it takes to determine if one number is the correct one (the eval function), and if that process leaks any information via timing or energy consumption or similar. What’s the point of all this? If you can control the oracle and re-write it for SIMD, why do you need to guess a number?

I tried to address this in the blog post since I expected a question like this, but obviously I didn’t make my point.

So the goal of this wasn’t to offer a new (and expensive) way to find whether an oracle verifies a 64-bit number.

The point was to show that problems that at first seem insurmountable or impractical may be well within reach, and that spending some time looking at available hardware resources and how to formulate the problem can make huge difference over the naive approach.

I can’t quite remember the details, but the original impetus for this came from a real issue. We wanted to know which would be faster: to run some analysis passes or just brute force the answer. This led to a discussion about how hard it is to brute force a 64-bit compare, with the original consensus being “wait until the end of the universe”. Obviously, it doesn’t take that long even for a naive approach, so then I got curious about exactly how insurmountable the “guess a 64-bit number” problem was.

Actually not the conclusion I expected! Good article.

If someone here can make an OpenCL and/or an ARM NEON version I would be most thankful :)

ARM is particularly interesting since then it’d be possible to do a cost analysis of ARM-based cloud instances, to see how they compare to x86.

There is an accompanying github repo with code to reproduce the results: https://github.com/trailofbits/sixtyfour

I don’t understand this post at all. In real life, what matters is how long it takes to determine if one number is the correct one (the eval function), and if that process leaks any information via timing or energy consumption or similar. What’s the point of all this? If you can control the oracle and re-write it for SIMD, why do you need to guess a number?

I tried to address this in the blog post since I expected a question like this, but obviously I didn’t make my point.

So the goal of this wasn’t to offer a new (and expensive) way to find whether an oracle verifies a 64-bit number.

The point was to show that problems that at first seem insurmountable or impractical may be well within reach, and that spending some time looking at available hardware resources and how to formulate the problem can make huge difference over the naive approach.

I can’t quite remember the details, but the original impetus for this came from a real issue. We wanted to know which would be faster: to run some analysis passes or just brute force the answer. This led to a discussion about how hard it is to brute force a 64-bit compare, with the original consensus being “wait until the end of the universe”. Obviously, it doesn’t take that long even for a naive approach, so then I got curious about exactly how insurmountable the “guess a 64-bit number” problem was.

iirc, it was random numbers used as verifiers; we had someone that we were attempting to persuade to use 128bits for something, and this came up.

noteArtëm and I work together!Sorry I missed the point, I was just really confused about how/why one would even think to ask the question in particular.

In my defence, the question basically boils down to “how quickly can I search for a number that equals 7”

Rule of cool, man, rule of cool.

@artem says below, it did actually come from a real life issue, so whilst cool, it definitely was more of our “I wonder if…” line of thinking.