TheNet authentication - cryptanalysis
This investigation focuses on vulnerabilities resulting from evesdropping on transmitted data. This is the easiest way for an attacker to obtain information, because all communication takes place using unsecured radio broadcasts.
How does the mechanism work?
System and user are the only ones in possession of a secret password.
If the systems needs to verify the users identity, the following protocol is executed:
- The system sends five distinct random numbers of which each represents the position of a character of the password.
- The user sends a reply containing the five characters from the password specified by the systems request in the same order and following one another. Positioning of this "block" inside the answer is random, as well as the answer's length. (but minimum is 5) All other characters of the answer are random.
- The system checks if it can find the "block" it compiled from it's copy of the password inside the answer. If this is the case, the system assumes the user knows the password and therefore believes he is who he claims to be.
Attack using set intersection
Because the password does not change, it must be containted in the intersection of all sets of password candidates resulting from evaluating obtained authentication data. The following obvious conclusions show how candidate sets are extracted:
- The requested password characters must be contained in the answer, thus all characters which are not in the answer string can be safely removed from the sets of possible characters for the requested numbers.
- Due to the fact that the contained password characters must be properly ordered, only answer characters on position 1 to n-4 are possible for the first requested password character. 2 to n-3 for the second and so on. (n is the length of the answer)
- But better reduction is possible due to response order: Only characters which are in the same relative positions to a character which is a candidate for one requested number are candidates for the respective other numbers.
Using this method it is possible to calculate more than half of the characters of a password having length 60 after intercepting only 10 authentication processes, each using answers of length 50. Because it is probably hard to believe that this protocol is so easy to break, you can find a simulator as well as a cracker for your real data right here: (Java Applets)
Attack using entropy discrepancies
Unlike the first, this attack is limited to manual answers. The idea is, gibberish entered by the user to disguise the actual password chunk is less random than the chunk itself, because humans are bad random generators - especially when going through authentication schemes in a hurry.
This approach was not pursued any further after the intersection attack turned out to be so highly effective.
Attack using frequency analysis
For each position in the password, a frequency analysis is performed, using all intercepted answers where this position had been requested. The character which goes at the position is statistically nearly once more contained in each answer than all others - because the rest of the answer is random.
This approach was not pursued any further either, but it may prove useful for passwords and answers which are relativly long and only use a very small character set.
Protection
If you read the text above and/or played around with the simulator, then there is no need to explain why using this authentication is suicide and not to any extend secure - unless you plan using your password only once.
Those who feel lucky should at least read these tips on how to increase the number of logins that need to be intercepted before the password can be cracked:
- Maximize password length.
- Maximize answer length.
- Password and random part of answer must use exactly the same character set.
- When it comes to the character set, less means more!
The fewer characters are used, the more often a particular character is contained in an answer, this slows down the set reduction. But reducing it too much will result in increased chance of guessing the right password during authentication by an attacker. I recommend using digits (0123456789) for password and answer.