3 ms·

I don't know if the mechanism is loose enough to accept multiple combinations as valid inputs but it can drastically reduce the search space. For instance, if t

I don't know if the mechanism is loose enough to accept multiple combinations as valid inputs but it can drastically reduce the search space. For instance, if the safe also accepts the numbers before and after the correct one the search space is divided by 3^[number of 'digits']. Feynman was famous for "cracking" safes in his time (more like cleverly trying all possibilities): https://www.youtube.com/watch?v=Waw11zhaKSk https://www.youtube.com/watch?v=Waw11zhaKSk

tomxor 7y ago
I think you mean de Bruijn sequence [0], can be hard to reach via search if you don't know the name. > a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length k^n, which is also the number of distinct substrings of length n on A; de Bruijn sequences are therefore optimally short. That is, it reduces the total number of input symbols required to traverse all permutations from (k^n)*n to (k^n)+n-1. i.e each sequence attempt takes only one extra input symbol regardless of the code length (n) or alphabet (k). Once I learned this (actually originally ended up figuring out for k=2 since google failed to reveal this page), I started to notice the critical difference between short 4 digit permutation keypads on doors: those that accept a continuous stream of input characters without a reset are vulnerable to this shortened brute force sequence; whereas those that require you delimit sequences with a separate key are not. Specifically: a non-delimited 4 digit decimal keypad takes at most 10003 input chars to crack, whereas a delimited one with a reset button takes 50000 (~5 times more, n+1 for the reset button). I'm not sure if continuous form are merely cheaper or the delimited form are simply newer and lock makers a little wiser? [edit] I suppose in the worst case for the non-delimited 4 digit keypads, if you also figure out the subset of alphabet used (i.e UV light button trick), then it reduces to (n^n)+n-1 = 259 input symbols !! except it adds the requirement of generating the sequence dynamically... but that's hardly difficult for n=k=4... and if any buttons are used more than once it reduces k further! e.g if a button is used twice then (4^3)+4-1 = 67! [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence
- tomxor 7y ago
  Yes i'm replying to myself. > I'm not sure if continuous form are merely cheaper or the delimited form are simply newer and lock makers a little wiser? Found this article [0] on exactly the same thing. Except he goes further to ask the difficulty added by simply increasing the alphabet by one (without adding delimiter key, and remaining vulnerable to de brujin sequences) vs adding a delimiter key. Answer: It depends on whether n > k. The reduced alphabet attack works equally on both forms as far as I can see. [0] https://www.johndcook.com/blog/2019/10/22/hacking-with-de-bruijn/ https://www.johndcook.com/blog/2019/10/22/hacking-with-de-br...
LorenPechtel 7y ago
It pretty much has to be this way, otherwise an exhaustive code search would not have a 70% chance of success. The robot is relying on that sloppiness and not doing every number.
- tomxor 7y ago
  If the parent is referring to de Bruijn sequences then it should in theory be 100% reliable since the device will be traversing every permutation. I suspect the 70% success is more to do with mechanical reliability, since the device must be compatible with multiple different mechanical combination locks that have different physical characteristics and may be far from in perfect operating condition - and also be able to operate at a reasonably high speed to be able to traverse all combinations in reasonable time even when using a de Bruijn sequence.

tomxor 7y ago

I think you mean de Bruijn sequence [0], can be hard to reach via search if you don't know the name. > a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length k^n, which is also the number of distinct substrings of length n on A; de Bruijn sequences are therefore optimally short. That is, it reduces the total number of input symbols required to traverse all permutations from (k^n)*n to (k^n)+n-1. i.e each sequence attempt takes only one extra input symbol regardless of the code length (n) or alphabet (k). Once I learned this (actually originally ended up figuring out for k=2 since google failed to reveal this page), I started to notice the critical difference between short 4 digit permutation keypads on doors: those that accept a continuous stream of input characters without a reset are vulnerable to this shortened brute force sequence; whereas those that require you delimit sequences with a separate key are not. Specifically: a non-delimited 4 digit decimal keypad takes at most 10003 input chars to crack, whereas a delimited one with a reset button takes 50000 (~5 times more, n+1 for the reset button). I'm not sure if continuous form are merely cheaper or the delimited form are simply newer and lock makers a little wiser? [edit] I suppose in the worst case for the non-delimited 4 digit keypads, if you also figure out the subset of alphabet used (i.e UV light button trick), then it reduces to (n^n)+n-1 = 259 input symbols !! except it adds the requirement of generating the sequence dynamically... but that's hardly difficult for n=k=4... and if any buttons are used more than once it reduces k further! e.g if a button is used twice then (4^3)+4-1 = 67! [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence

tomxor 7y ago
Yes i'm replying to myself. > I'm not sure if continuous form are merely cheaper or the delimited form are simply newer and lock makers a little wiser? Found this article [0] on exactly the same thing. Except he goes further to ask the difficulty added by simply increasing the alphabet by one (without adding delimiter key, and remaining vulnerable to de brujin sequences) vs adding a delimiter key. Answer: It depends on whether n > k. The reduced alphabet attack works equally on both forms as far as I can see. [0] https://www.johndcook.com/blog/2019/10/22/hacking-with-de-bruijn/ https://www.johndcook.com/blog/2019/10/22/hacking-with-de-br...

LorenPechtel 7y ago

It pretty much has to be this way, otherwise an exhaustive code search would not have a 70% chance of success. The robot is relying on that sloppiness and not doing every number.

tomxor 7y ago
If the parent is referring to de Bruijn sequences then it should in theory be 100% reliable since the device will be traversing every permutation. I suspect the 70% success is more to do with mechanical reliability, since the device must be compatible with multiple different mechanical combination locks that have different physical characteristics and may be far from in perfect operating condition - and also be able to operate at a reasonably high speed to be able to traverse all combinations in reasonable time even when using a de Bruijn sequence.