wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Hacking an answering machine
        
(Message started by: oliver on Aug 6^th, 2002, 7:10am)

Title: Hacking an answering machine
Post by oliver on Aug 6^th, 2002, 7:10am

Ok, first of, I don't know the solution to this riddle - strictly speaking, I wouldn't call it a riddle for this reason since it may be really difficult and require lots of maths.

You know these answering machines with remote inquiry facility, where you can call the answering machine and enter a 4 digit passcode into your telephone keypad, so you can listen to your messages from anywhere you like.

Many of these machines are quite dumb in the way you can feed the codes. They let you in if they encounter the right combinations of digits, regardless what you sent before.

Example: code is 1234

if you feed the machine 1234, you're in
if you feed the machine 01234, you're in
if you feed the machine 0121234 you're in

It just waits for the right 4 digits to come in, regardless of what happened before.

In order to hack the machine, could try all numbers from 0000 to 9999, sending 40000 sounds across the wire. But since you are a smart hacker, you see that there's room for optimization.

What is the shortest series of digits you have to send to the answering machine in order to break the code in any case?

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by jeremiahsmith on Aug 6^th, 2002, 11:38pm

This is an interesting question, actually...I wonder why it hasn't been added. (Or has it, and I didn't notice?)

As far as I can tell, you're going to need at least 10003 digits in your number string. If you do it right, each number can be the start of a different 4-digit sequence. For example, with ten digits: 0123456789, you have seven combinations, 0123 to 6789. Then you tack on three more at the end so the strings beginning with the last three digits (7, 8, and 9) will all be four digits long. So, with a string of 10000 digits, we can get 9997 combinations since the last three won't be long enough, so we stick on 3 more and go on.

It would be a relatively simple exercise, I think, to lower the number of digits from 40000...for example, just start out with 0123456789 and then do every combination that's not in that sequence. But finding the optimal solution is a toughie. I suppose you could write a program to do it...
Start with three numbers.
Find a number so that, when added to those three, won't make a sequence that's been used before. To make things more defined, start at 0 and work up, so if xxx0 is used, try xxx1.
Add the number and start with the new last three numbers.

So, we start with 000.
The next unused code starting with 000 is 0000, so add 0 to get 0000.
The next unused code starting with 000 is 0001, so add 1 to get 00001.
The next unused code starting with 001 is 0010, so add 0 to get 000010.
Und so weiter.

I suppose if you ever got stuck, you could simply start with a new sequence and add it to the end. There might be some overlap, so you might have to do 10021 digits instead of 10003, or something, but you would at least cover all the numbers. Hopefully, this won't be necessary.

The only problems I could see would be in writing the program to go fast enough for your needs. But a brilliant hacker such as yourself would probably do that nicely. (Not to mention that you'd probably have a nice fast computer.)

Although my math skills are not as finely-honed as others on this forum, this seems like it would work.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by jeremiahsmith on Aug 7^th, 2002, 12:33am

Okay, so my solution's not QUITE optimal...

Starting with 000, and adding digits to form the lowest unused code, you would eventually get this:

0000100020003000400050006000700080009000

Then you're stuck. All the codes beginning with 000 are used. And, if you do the math, all sequences will eventually go to this. Take 123. Since the lowest number beginning with xxx is xxx0, you would keep adding zeroes: 123000 and there we are.

Hm. I think perhaps we could add a little thing...if a sequence of 3 digits is all used up (i.e., all codes beginning with those three digits), add that sequence to the list of sequences not to make.

Thus:

0000100020003000 etc etc 0008000900 and since if we added 0, we would get a used-up 3-digit sequence (000), we add 1 to get 00080009001. I don't know how we would get 9000; maybe it would come out later. If worse comes to worst, we could stick 9 at the beginning. 90000 etc...

I really wish I had more of a mind for riddles.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by AlexH on Aug 7^th, 2002, 2:17am

Oliver, you can achieve the optimal result of 10003 numbers, but you'll want some basic graph theory. Graph based solution follows so SPOILER ALERT:

A cycle within a graph which uses each edge exactly once is called an Euler tour of the graph. Directed graphs have Euler tours whenever the in-degree and out-degree match for every vertex (as is the case here) and there is a fairly simple algorithm for generating the tour in O(V+E) time.

Make a graph with 1000 verticies labelled by all possible strings of 3 digits (think of these as represeting the last 3 digits typed in). Add edges from each node labelled xyz to all nodes labelled yzd for every digit d. For example you'd have edges from node 052 to nodes 52[0-9]. Compute an Euler tour of the graph. Select some vertex, type the 3 numbers of its label, then follow the Euler tour and type whatever number corresponds to each edge you follow. Every combination of "previous 3 digits" plus "current digit" corresponds to exactly one edge in the graph so the tour will hit all 4 digit combinations.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by oliver on Aug 7^th, 2002, 4:54am

Very nice answer Alex, thanks.
I heard this problem like 4 years ago, and I remember having such a graph in my mind. Sadly, I lack even basic knowledge of graph theory ;).

Now the question is if there is a even more elementary proof, i.e. one which doesn't require (basic) knowledge of graph theory.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by icon on Aug 7^th, 2002, 10:00am

hehe

its an intresting problem

u shouldnt need to know much to code a bruceforcer for this

and more intresting if thats the way it works u can even code a direct pcb board and hardwire it to the phone to test it out hehe

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by drbhoneydew on Aug 11^th, 2002, 9:28pm

To start off with, consider the case when the pin is 1 digit. Obviously, the minimum number of keypresses is 10.
Next, consider a 2 digit pin - 100 possible codes, 200 max keystrokes. To optimise, notice what happens when you input the first 10 digits naively:
00010203040506070809
We obviously don't need that leading 0, so put it on the end:
00102030405060708090
In crossing off the first 10 numbers, we have simultaneously captured the multiples of 10 - 10, 20, 30 etc.
Let's put the next few combinations in:
112131415161718191
In getting the numbers from 11-19, we've also got 21, 31, 41, etc.
To see what's happening here, picture a 10x10 grid with all our numbers on. (0-9, 10-19 etc) Every time we cross off a row, we can also cross off a column, so long as we move the extra leading digit to the end of our sequence. In other words, we are crossing off a series of interlocking |_ shapes that have their corner on the codes with repeating digits.
Using this method, I was able to cover every possible 2 digit code in 110 keystrokes.
Extending to 3 digit pins, we are now constructing a set of sequences to cross off faces on a cube. Visualising this without an actual cube is rather difficult so I'm actually having fun with 10 10x10 grids in Excel (joy!). Starting off the "0" grid we get:

00100200300400500600700800900
1101201301401501601701801901
02102202302402502602702802902
03103203303403503603703803903
04104204304404504604704804904
...
I can see that this isn't quite optimal, but it is still pretty good. At the moment, I'm working through this and have crossed off all of the "0" grid in 299 keystrokes. In addition to the "0" face, this process has crossed off the first |_ in each of the other 10 grids. I'm not sure what this would look like on the cube. The joins between the lines aren't great - just in the sequence above, I've got 102 in twice (end of row one - start of row 2) I don't know whether it's possible to prevent some of these cropping up.
The next stage after this I guess is to try to generalise for the n to n+1 dimensions and see if I'm right for n=4, which is the actual question. :o

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by drbhoneydew on Aug 11^th, 2002, 9:56pm

The minimum of 10003 cannot be possible as there is no Euler tour of the graph. There are at least 10 odd vertices (those codes with 4 repeating digits). Euler proved that if there are more than 2 there cannot be such a tour.
So I'm guessing that the "optimal" result is found by constructing the subtours as described in my previous post, then using an algorithm to find points in 1 tour that can connect to points in another.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by jkemp on Aug 11^th, 2002, 10:50pm

For a password length 2, there are 10^2 (100) combinations to test.

Every digit except for the first and last is used to test 2 combinations. The first and last digits are each used to test 1 combination. This means that if x is the length of the test string, x - (1 * 2) = 100; meaning x = 102.

E.G. "100203040506070809011121314151617181922324252627282933435363738394454647484955657585966768697787988991"
Length = 102.

For 3-digit passwords, there are 10^3 = 1000 combinations.
The first & last digits test 1 combination each.
The second & second-to-last digits test 2 combinations each.
The remainder test 3 combinations each.
x - (1 * 2) - (2 * 2) = 10^3
or x = 10^3 + (1 * 2) + (2 * 2) = 1006

For 4-digit passwords, there are 10^4 = 10000 combinations.
The first & last digits test 1 combination each.
The second & second-to-last digits test 2 combinations each.
The third & third-to-last digits test 3 combinations each.
The remainder test 4 combinations each.
x = 10^4 + (1 * 2) + (2 * 2) + (3 * 2) = 10012

Therefore, the optimal string will have to be 10012 digits long.

Generalising:
For n-digit passwords, there are 10^n combinations.
The first and last 1..n-1 digits each test 1..n-1 combinations, the remainder test n combinations each.
x = 10^n + (1 * 2) + (2 * 2) + ... + ((n-1) * 2)

Jeff

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by AlexH on Aug 12^th, 2002, 12:31am

drbhoneydew:
This graph is directed so the condition we actually need to ensure an Euler tour is that in-degree and out-degree are equal at every vertex (which this graph does satisfy). The nodes which are a single digit repeated 3 times have in and out degrees of 9 while all others have in and out degrees of 10. We will of course have to include the "self-loop" one of the times we visit each of those verticies but this does not present a problem. The even-degree requirement to which you refer is for undirected graphs.

jkemp:
Its much easier to look at this just as having a 3 digit "setup" cost, followed by 1 code tested per new digit. We can also calculate this the way you suggest, but your calculation is off. Its true that in an optimal sequence the first/last only are used in 1 combination, the seconds in 2 and the thirds in 3, while all others are used in 4. But the equation this should lead you to is 2*1+2*2+2*3+(x-6)*4 = 10000 * 4. Solving for x you get 10003.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by TimMann on Aug 31^st, 2002, 1:49am

The nodes which are a single digit repeated 3 times have in and out degrees of 9 while all others have in and out degrees of 10.

This sentence is wrong: All the nodes have in and out degree of 10; those that are a single digit 3 times are no exception. For example, 000 has to have out-edges labelled 0 through 9, because all of 0000, ..., 0009 are possible combinations. Since you mentioned self-loops in the next sentence, I'm sure you realized that. Even though the edge labelled 0 is a self-loop, that doesn't stop it from counting toward the degree of the node it connects to (both the in and out degree).

The rest of what you said is quite right, of course. Very pretty solution.

A couple of years ago some friends and I were playing around with a similar problem in binary; we wanted each possible rotation of a 64-bit string to have a different low-order 6 bits. It's easy to construct such strings by brute force. I vaguely remember that one of our local mathematicians came up with a formula for the number of solutions for a given string length. I can't remember that part (or find the relevant email) offhand, but I'm pretty sure the Euler tour argument wasn't used. I'll have to dig around a bit more and see if I can find the information.

Title: Re: NEW PROBLEM: Hacking an answering machine
Post by AlexH on Aug 31^st, 2002, 9:32am

No that statement wasn't wrong, I'm the one defining the graph after all. The person I was responding to seemed to not want to allow self-loops in the graph, so rather than argue that self-loops are ok for Euler Tour (which of course they are), I explained a way to make it work where the Euler Tour algorithm doesn't allow self-loops. This is why I put the word self-loop in quotes, its not a part of my Euler Tour solution, its just something I tack on after the fact.

Title: Re: Hacking an answering machine
Post by Alfihar on Apr 6^th, 2004, 7:33am

hmm, well the posts here seem to be fairly old by now, but i thought id give my 2 cents anyway :P

the minimal solution length (IF the perfect solution exists) of course would be 10^N + N - 1, where N is the length of the code and the charset is 0, ..., 9 (otherwise the 10 changes, obviously)
question was whether this solution exists (for any charset and N).. and i still cannot prove it does, but some previous posts were quite convincing there..
what interested me was creating those strings.. and i had a couple of very BAD algorithms (even tho id like to say that they were interesting at least ;P) which were very slow or not usable at all..
recursions are impossible, obviously.. due to the huuuuuuge amount of recursions needed. but an iterative algorithm which basically mimics the recursions works surprisingly fast (and this has been mentioned here before, yepyep)
so.. i wrote this lil thing that spits out strings for given N/charset...
what i wanted to find out now is how many solutions there are.. and indeed the number is incredibly large for N=2 already.. and i havent even managed to find all solutions starting with 00-.. yet.
finding those would be enough, because all solutions form rings, hence.. will end in the same N-1 chars the string started with (can easily be shown that this must hold true for all minimal solutions)
so all 00*0 solutions for N=2 are *unique* even when they are rotated, this is due to the fact that "00" cannot show up inside the string again.
thus.. the number of 00*0 strings is the number of unique solutions, one might want to divide them by 2, still.. to not count the mirrored strings (this is safe, because no solutions can be symmetrical)

so if anyone has a formula for this.. (or remembers it, as one was mentioned quite early in the thread) id be interested =P

Title: Re: Hacking an answering machine
Post by John_Gaughan on Apr 7^th, 2004, 7:27pm

on 08/06/02 at 07:10:05, oliver wrote:

Many of these machines are quite dumb in the way you can feed the codes. They let you in if they encounter the right combinations of digits, regardless what you sent before.

This reminds me of the keycard entry system at a place where I used to work. Pins were four characters, but the system only cared about the last four digits. There was a time limit, so after about three seconds the system would time out and you would have to start over. Most people did not know this, so those of us bored programmers in my office would try to punch as many numbers as possible and set records for the longest PIN that still allowed entry. Bystanders usually thought we were either crazy or stupid, possibly both, and usually correct. I think I eventually got up to about twelve numbers.

Title: Re: Hacking an answering machine
Post by oregontrail256 on Jun 24^th, 2009, 11:21am

Since each node in the graph represents a distinct code, shouldn't you be looking for a hamiltonian path (hits all the vertices), not a eulerian path? I don't see how traversing all the edges (and thus hitting each vertex 5 times) gets the optimal solution.

But even if I'm right, finding a hamiltonian path is NP-complete so I don't think this solves the riddle.

Title: Re: Hacking an answering machine
Post by oregontrail256 on Jun 24^th, 2009, 11:28am

Nevermind, I recognize how the graph translates to 4 digit codes... (node -> first 3 digits, edge -> last digit).

Title: Re: Hacking an answering machine
Post by Hippo on Jun 27^th, 2009, 1:10am

As the thread was reopened:
This sugests that having odd number of digits is a complication for heckers
(of course reducing 10 to 9 does not increase the number of typed digits).

How long should the string be for 9 resp. (2k-1) digits?

Lower bound is of course increased by the number of odd vertices divided by 2.
Can we achieve this bound?

Title: Re: Hacking an answering machine
Post by Grimbal on Jun 27^th, 2009, 8:57am

Actually I don't think it matters if there are an even or odd number of digits.

If we have d digits and n-digit codes, we define the graph that has (n-1)-digit sequences as nodes and n-digit sequences as edges. Edges are directed and the from and to nodes are defined respectively by their first and last (n-1) digits.

So you have d^(n-1) nodes having each c incoming and c outgoing edges. In some cases the edge loops back.

It is pretty easy to find a path covering all edges by just starting anywhere and proceed following any unused edge. As long as you don't return to the start node, you entered the node one more time than you left it so there must be a way to continue. You can be blocked only at the starting node. When that happens, you can just close the loop and re-open the loop at any node on the path that still has outgoing edges. Since the graph is connected, you can extend the loop this way until it covers the whole graph.

So as mentioned before, you just need (n-1) digits to set up an initial node, and from there each additional digit represents going over an unique edge. There are d^n edges, therefore d^n+(n-1) digits is all you need to cover all n-digit codes.

Title: Re: Hacking an answering machine
Post by Eigenray on Jun 27^th, 2009, 9:25am

Here is a program to generate the lexicographically least [link=http://en.wikipedia.org/wiki/De_Bruijn_sequence]de Bruijn[/link] sequence for any length and base. It is a shortened version of neck.c from the [link=http://www.theory.cs.uvic.ca/~cos/inf/neck/NecklaceInfo.html]combinatorial object server[/link], with non de Bruijn options removed. I'm not sure if I used to know how it worked or not... probably not.

Code:

int a[101];
int n,k;
void Gen(int t, int p) {
int j;
if(t>n) {
if(n%p==0) for(j=1; j<=p; j++) printf("%d,",a[j]);
return;
}
a[t] = a[t-p];
Gen(t+1,p);
for(j=a[t-p]+1; j<k; j++) {
a[t] = j;
Gen(t+1,t);
}
}
int main() {
scanf("%d %d",&n,&k);
a[0] = 0;
Gen(1,1);
}

Original header:

Quote:

C program to generate necklaces, Lyndon words, and De Bruijn sequences. The algorithm is CAT [constant amortized time] and is described in the book "Combinatorial Generation." This program, was obtained from the (Combinatorial) Object Server, COS, at http://www.theory.csc.uvic.ca/
The inputs are n, the length of the string, k, the arity of the string, and density, the maximum number of non-0's in the string. The De Bruijn option doesn't make sense unless density >= n.
The program can be modified, translated to other languages, etc., so long as proper acknowledgement is given (author and source).
Programmer: Frank Ruskey (1994), translated to C by Joe Sawada

Title: Re: Hacking an answering machine
Post by yevvi on Jun 17^th, 2015, 1:23am

But once you close the loop at the starting node and have to start over at some other node, this will no longer be a connected path. So then it won't correspond to a single sequence of digits, but instead we will have multiple sequences. So then we won't be able to lower bound their total length. Am i missing something?

on 06/27/09 at 08:57:23, Grimbal wrote:

Title: Re: Hacking an answering machine
Post by rmsgrey on Jun 17^th, 2015, 2:57am

on 06/17/15 at 01:23:01, yevvi wrote:

You're missing that, rather than starting over with a new sequence, Grimbal's method breaks into the original sequence and patches in a loop.

For example, if you start with 0000100020003000400050006000700080009000 then you can break after 0001 and replace the 001 with 001100120013001400150016001700180019001
(you can't use 0010 because that's part of the original sequence) to give

0000110012001300140015001600170018001900100020003000400050006000700080009000

Because each node of the graph has equal in-degree and out-degree, and the graph is strongly connected (you can get from any node to any other) you can always find an Eulerian cycle, and the method Grimbal outlines is a standard way of doing so.

Title: Re: Hacking an answering machine
Post by yevvi on Jun 19^th, 2015, 1:16am

Oh i see. So as long as we didn't cover the whole graph, there will be a node in the loop with unused edge, because otherwise it would mean that nodes outside the loop would not be reachable which contradicts the fact that the graph is strongly connected. So now we know that we can extend the loop to cover all the nodes. After all the nodes a covered, if there are still any unused edges, we can extend the loop by following each unused edge (since by the previous logic we know we will come back to where we start without hitting a dead end). I think i understand now. Thanks for the explanation.