For the author:
"Benchmarking page to choose good parameters..." seems to spin forever and I don't feel the device getting warm. Don't have an error console on mobile so not sure what's up but this is on an Android webview browser. Maybe add an onerror event handler to at least show the user this spinner is going nowhere?
Edit: wait, it did complete now that I've not used the skip to demo link and read the article. "Benchmark complete! Using 29000 iterations". Maybe mention that it can take several minutes on a modern device? Or a progress indicator?
Now that I'm running the password guesser, the device does get warm in the usual spot for cpu load. Cool way to visualise the method! After five minutes, 6 out of 10 guesses have the right first character, and of those, 2 the right second character. Am I extrapolating correctly if I guess it'll need to do this 4 more times so some 20 minutes? Battery use is 30%./hour currently so about 10% of a full charge would be 1.1 Wh
Edit2: the number of correct prefixes is decreasing after 10~15 minutes. This will take forever
This reminds me of timing side channel attacks in general. With VUSEC (VU University Amsterdam) we did flush/reload side channel attacks. I don't remember the specifics, I did this in 2018.
But yea, basically if a cache hit versus a memory roundtrip will result in different time values, then you can iterate over all 256 bytes (assuming ASCII) and when you have a cache hit for a specific value, the time should be much lower.
However, this also assumes you understand cache internals of the specific CPU and it means you need to know when caches fill up, why they fill up and how to do cache eviction. Knowing how to do cache eviction means that you need to know how many elements can be cached, and if I recall correctly that means you need to reverse engineer the cache size of the CPU. But once you can reliable evict values from the cache set and reliably fill them up, then the rough outline I mentioned above is possible.
Again, this is like 50% accurate since it has been a long while and I currently work in marketing as a data analyst (I like a mix of fluffy marketing/psychology talk and being deeply technical - if you feel the same way, feel free to reach out. My email is on my profile). There's some of what I described on this website (and a whole bunch more) [1]. I think the reverse engineering of cache lines was specifically in the accompanied paper.
A note on the Thompson sampling: classic TS is optimizing for regret, while the goal here is to identify the 'best arm' (ie. the actual secret value at that position - it's like a 0/1 loss). There is no partial credit in getting part of a password correct, it still won't work. So it's a https://en.wikipedia.org/wiki/Multi-armed_bandit#Best_Arm_Id...
Thanks! I believe the actual code is handling this correctly but would love to read that paper – you don't happen to have another link, do you? https://www.escholar.manchester.ac.uk/ seems to be down for me.
Neat post, but it doesn't seem to work in Firefox. The benchmarking just runs forever. I see a JS error about it blocking Cloudflare's beacon.min.js. Is it using that to benchmark?
For me it works in Firefox, on mobile that is (didn't try it on desktop). But it worked once. It guessed "spiderme" in ~22000 tries, but ran for longer than my patience allowed (and I'm very patient) on "hderhfsd". For some reason, it correctly guessed up to "hde", started to show some confidence in the following 'r', but then degenerated into hd... Then h... And then started guessing 'o' or 'h' as the first letter more and more.
For the author: "Benchmarking page to choose good parameters..." seems to spin forever and I don't feel the device getting warm. Don't have an error console on mobile so not sure what's up but this is on an Android webview browser. Maybe add an onerror event handler to at least show the user this spinner is going nowhere?
Edit: wait, it did complete now that I've not used the skip to demo link and read the article. "Benchmark complete! Using 29000 iterations". Maybe mention that it can take several minutes on a modern device? Or a progress indicator?
Now that I'm running the password guesser, the device does get warm in the usual spot for cpu load. Cool way to visualise the method! After five minutes, 6 out of 10 guesses have the right first character, and of those, 2 the right second character. Am I extrapolating correctly if I guess it'll need to do this 4 more times so some 20 minutes? Battery use is 30%./hour currently so about 10% of a full charge would be 1.1 Wh
Edit2: the number of correct prefixes is decreasing after 10~15 minutes. This will take forever
This reminds me of timing side channel attacks in general. With VUSEC (VU University Amsterdam) we did flush/reload side channel attacks. I don't remember the specifics, I did this in 2018.
But yea, basically if a cache hit versus a memory roundtrip will result in different time values, then you can iterate over all 256 bytes (assuming ASCII) and when you have a cache hit for a specific value, the time should be much lower.
However, this also assumes you understand cache internals of the specific CPU and it means you need to know when caches fill up, why they fill up and how to do cache eviction. Knowing how to do cache eviction means that you need to know how many elements can be cached, and if I recall correctly that means you need to reverse engineer the cache size of the CPU. But once you can reliable evict values from the cache set and reliably fill them up, then the rough outline I mentioned above is possible.
Again, this is like 50% accurate since it has been a long while and I currently work in marketing as a data analyst (I like a mix of fluffy marketing/psychology talk and being deeply technical - if you feel the same way, feel free to reach out. My email is on my profile). There's some of what I described on this website (and a whole bunch more) [1]. I think the reverse engineering of cache lines was specifically in the accompanied paper.
[1] https://www.vusec.net/projects/glitch/
A note on the Thompson sampling: classic TS is optimizing for regret, while the goal here is to identify the 'best arm' (ie. the actual secret value at that position - it's like a 0/1 loss). There is no partial credit in getting part of a password correct, it still won't work. So it's a https://en.wikipedia.org/wiki/Multi-armed_bandit#Best_Arm_Id...
You can tweak the Thompson sampling to handle best-arm, like https://www.escholar.manchester.ac.uk/api/datastream?publica... "Ordered-Statistic Thompson Sampling". I am not sure if the pseudocode TS presented by OP winds up doing the same thing.
Thanks! I believe the actual code is handling this correctly but would love to read that paper – you don't happen to have another link, do you? https://www.escholar.manchester.ac.uk/ seems to be down for me.
Oh, I'm sorry. That should be Mellor 2014, https://pure.manchester.ac.uk/ws/portalfiles/portal/54552919...
(If you are curious, I was playing around with best-arm finding algorithms for taste-testing: https://gwern.net/water )
This is great (this = both the paper and your post) but I can't believe you never made a tea-test pun
(Tea puns are generally too easy.)
Neat post, but it doesn't seem to work in Firefox. The benchmarking just runs forever. I see a JS error about it blocking Cloudflare's beacon.min.js. Is it using that to benchmark?
I can confirm it works in Chrome.
For me it works in Firefox, on mobile that is (didn't try it on desktop). But it worked once. It guessed "spiderme" in ~22000 tries, but ran for longer than my patience allowed (and I'm very patient) on "hderhfsd". For some reason, it correctly guessed up to "hde", started to show some confidence in the following 'r', but then degenerated into hd... Then h... And then started guessing 'o' or 'h' as the first letter more and more.