Re:Superpermutations
by Zanni on Monday October 22, 2018 @01:57AM
(#18272497)
I was introduced to this idea on the comp.risks forum, where it was presented as an attack on an answering machine with a 5-digit passcode, which, naively, would require an average of 50,000 guesses of 5 digits each, or 250,000 key presses. But this particular device not only didn't lock out after some number of incorrect guesses, it didn't require a separator character between guesses. It just listened for the correct five digits consecutively, regardless of what you had entered before. So a superpermutation just 153 digits long was sufficient to crack every device.
[ Parent
| on HN ]
I think you must be misremembering; if you dial a sequence of 153 digits, you can't possibly test more than 149 different 5-digit substrings.
Possibly. It was 20 years ago. I'm reconstructing via my (possibly flawed) understanding of the linked article. (My vague recollection was something like 250 digits for a 4-digit passcode.)
And I just realized I mistakenly conflated 5-digit permutations of 5 digits with 5-digit passcodes of 10 digits. Whoops.
Why not just re-read RISKS?
* https://catless.ncl.ac.uk/Risks/7/69#subj5.1
You’re thinking of De Brujin sequences, not superpermutations, unless there’s an additional restriction that a digit cannot be used twice in a password.
Yes, and in this case the sequence is specifically the "classic" De Bruijn sequence [1]; however, there are other sequences that bear De Bruin's name, such as the Moser de Bruijn sequence, which is the one I reference most due to its relation to Z-order curves and pairing functions.
NB: I suspect the number you are thinking of is a 2530 digit sequence on a 4-digit lock, not 153 on 5...