Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

My area of expertise is reverse engineering, specifically embedded systems. I do attack cryptographic systems, but this largely involves key recovery or exploiting the implementation.

I was asked to reverse engineer a simple Windows executable used as part of a challenge-response protocol used for intruder alarm systems. This was trivially easy. I would like some assistance in describing the protocol/algorithm, so that I can look into the security of the system more.

The protocol

The protocol is designed to stop users resetting their alarm without contacting their alarm receiving centre.

  1. When the alarm is triggered, a message is displayed:

    CONTACT ARC   
    QUOTE 83647
    

    This is called the "quote code" and is always numeric and 5 digits long. I don't know how it is chosen, but it appears random.

  2. The alarm user calls the alarm receiving centre and informs them of the quote code.
  3. The alarm receiving centre inputs the quote code into a piece of software (the "decoder") which returns the numeric 5 digit "reset code".
  4. The user is informed of the "reset code" and inputs it into the alarm. It is accepted and the alarm is disarmed.

    The alarm and alarm receiving center share a secret which is a number from 0-255, this is called the "version".

    So at a superficial level, both the alarm and alarm receiving centre are doing:

    ResetCode = F(QuoteCode, Version)
    

    Where the QuoteCode and ResetCode are integers in the range 00000-99999 and the Version is a number between 0-255.

Algorithm implementation

This is my basic implementation of the algorithm used to generate the reset code given the quote code. The vector at the top is altered, but the rest is the same.

# Taken from the data in the exe
vector = [3,3,5,5,8,1,3,9,8,0,5,9,3,9,4,1,1,0,9,4,3,0,2,2,8,4,3,2,8,4,9,4,1,3,3,3,3,8,5,3,0,2,4,3,2,1,8,9,0,5,4,3,9,5,8,3,9,9,1,0,0,9,9,3,3,8,2,
         1,4,9,1,4,9,2,9,0,9,5,3,9,5,3,3,5,9,1,0,2,9,3,2,1,2,9,8,0,4,9,4,2,3,9,4,0,1,8,5,3,3,9,9,1,0,5,9,3,8,9,4,8,4,2,3,1,0,3,9,4,8,2,0,4,3,3,
         1,0,5,2,8,3,3,5,2,8,3,2,9,5,2,1,2,4,4,3,0,4,2,3,4,1,8,2,9,1,0,5,1,8,2,4,3,5,1,0,3,8,5,3,2,1,1,3,9,3,2,3,5,8,3,9,0,3,2,3,5,3,8,4,0,3,9,
         1,9,3,0,2,9,3,8,1,4,2,8,4,0,1,9,1,0,1,2,1,3,5,3,3,9,0,2,1,4,1,2,3,4,3,4,9,5,3,5,9,3,1,3,9,4,0,3,2,3,3,4,4,2,1]


def generate_reset(quote, version):
    i = 0
    tens = 0
    reset = []

    while i <= 4 :
        j = 0
        result = 0

        while j <= 4:
            offset = (version + tens + quote[j]) % 256
            result = result + vector[offset]
            tens = tens + 10
            j = j + 1

        reset.append(result%10)
        i = i + 1

    return reset

print(generate_reset(quote = [0,0,0,0,2], version=131))

I have run several simulations (simply by looping through all combinations of inputs), and noted the following:

  1. The coverage of reset codes for any given version number across all quote codes is ~63%. This means that you have a higher than 1/100000 chance of guessing the correct reset code randomly.
  2. Given a quote code and reset code, most of the time there is only a single valid version number. At most, two pairs of quote and reset codes are needed to derive the version number. The "version" isn't very secret as a result.

Questions

I hope these aren't too vague, or broad.

  1. What would you call the type of algorithm? To me it looks like a hash with a key - does this make it a MAC?
  2. Does this specific implementation have a name? It looks very "roll your own" but the vendor uses the phrase "military grade".
  3. Are there any glaring issues with this algorithm? (I'm not expecting someone to do a full analysis, just some pointers would be great). My gut feeling is that the secret "version number" is not long enough to provide adequate secrecy.
share|improve this question
add comment

2 Answers

The intend appears to be that vector is secret and the main key; and version (that, we are told, is secret) is an extension of that key (or variant selector).

1) I could say that ResetCode is a MAC of quote with key vector and version.

2) Never met this particular one. Anyone with common sense should laugh at it as snake oil if it pretends to be military-grade cryptography.

3a) When seen as a MAC, an obvious algorithmic flaw is that adding 1 (mod 256) to version and subtracting 11111 from any quote which has each of its digits non-zero leaves the ResetCode unchanged; this can be classified as a related-key weakness. That observation can make a usable paper tabulation of the function over twice less bulky (only entries with quote including a 0 need to be tabulated). Adding 10 (mod 256) to version also has special properties.

3a') Update: there's much worse! For constant version and vector, changing a particular digit in quote into another digit causes a difference (mod 10) in any particular digit of ResetCode that is independent of the 4 other digits of quote. With this observation, from the ResetCode for a small set of quote values, we can compute the ResetCode for any quote value, without knowing vector or version. The set of 46 quote values having at most one non-zero digit is convenient for hand calculation, but even random quote from a significantly smaller set often allows trivial linear algebra to pull that trick. In fact that MAC is so linear and with poor mixing that it could be broken from examples alone, without knowledge of the algorithm or reverse engineering the code or extracting vector!

3b) In the usage context, after vector has become public (e.g. if it is common to all alarms of the type), most often a single intercept of (ResetCode, quote) is enough to find version, leading to total break. Even a theoretically perfect cryptographic MAC is expected to have this property, given the ridiculously small size of what remains of the key (version), and the larger size of ResetCode. Any theoretical weaknesses of the algorithm seen as a MAC is moot compared to this system weakness of a small version when an adversary can obtain all key material beside version, or has access to a black box computing ResetCode for any chosen input (quote, version).

share|improve this answer
    
Thankyou for your answer. I had not observed 3a) but I had run a simulation on 3b) - on average a single pair is enough to guess the key. –  Cybergibbons May 16 '13 at 19:41
    
I guess I should start another question about MACs where the input is the same length as output and key length is smaller. –  Cybergibbons May 16 '13 at 19:56
    
@Cybergibbons: in a secure MAC with $k$ possible keys small enough that all keys are enumerable, and $o$ possible outputs, little more than $\lceil k/o\rceil$ examples are necessary to find the key. Here $k=256$ (after vector becomes public), $o=100000$, thus little more than one example is enough. In fairness, an adversary was not supposed to get the program that you reverse-engineered to extract vector; but even considering this, the algorithm is ridiculously weak, see 3a' –  fgrieu May 17 '13 at 13:58
add comment

Whilst your altered vector value will influence the results, this extension of your script demonstrates that typically obtaining a single quote/reset pair is enough to reveal the secret version:

def find_versions(quote,reset):
    """ Brute force search for version keys that produce reset from quote """
    versions = []
    for version in range(256):
        if generate_reset(quote,version) == reset:
            versions.append(version)
    return versions


multiples = defaultdict(int)
tests = 10000
for i in range(tests):
    vector = [random.randrange(0,10) for _ in range(256)]
    quote = [random.randrange(0,10) for _ in range(5)]
    version = random.randrange(256)

    reset = generate_reset(quote, version)

    found_versions = find_versions(quote,reset)
    if len(found_versions) != 1:
        count = len(found_versions)
        multiples[count] += 1

    assert(version in found_versions)
print("Recovered version from {} random vector/quote/reset inputs".format(tests))
for length,count in multiples.items():
    print("There were {} pairs that returned {} possible values".format(count,length))

Example run:

$ python3 reset.py 
Recovered version from 10000 random vector/quote/reset inputs
There were 28 pairs that returned 2 possible values

Edited: now generating a random vector for each test, to show that the example vector wasn't pathological in some sense

All this is just reinforcing fgrieu's point that value is too small.

share|improve this answer
    
Thanks Michael. I ran something really similar but it was a simple search in order rather than random. The average number of possibilities is very close to 1 indeed. I wonder if there is any way of expressing this more formally? –  Cybergibbons May 16 '13 at 19:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.