Algorithm for message code validation

Question

Hi!

If you read this thread before - forget everything I wrote, I must have been drunk when I wrote it. I'm starting over:

I'm currently working on a project where we will be using some sort of algorithm for validating user input. There are three parties to consider;

Client - Browsing our web pages

Company - We, handling the Client requests

3rd Party Company - Handling Client messages

On our web pages we will show the Client some information about a product. If he/she wants more information about the product he has to contact the 3rd Party Company and state the products code (not unique per se, but not common either). In return the Client will receive some other code from the 3rd Party Company which he should input on our web page, where we will validate the code for approval.

The best would be if we, the Company, had no interaction with the 3rd Party Company. Pure encryption is out of the picture because it generates a string that is too long. We are doing this by SMS, so the codes has to be short.

What I've come up with so far:

For every product I generate a somewhat unique code (it doesn't matter if it's unique or not really) in base 16 (0-f). The Client who wants more info about the product sends a SMS to the 3rd Party Company stating the products code. In return the Client receives the same code, but the digits are multiplied (possibly by 2) and converted to base 36. On top of that a last character is added to the code, a control number, to make the code valid for the Luhn algorithm in base 36. The user enters the received code and we, the Company, validate it on the server side against the product code (validate against Luhn, divide by 2 and switch back to base 16).

Does this sound reasonably safe and appropriate? Is it a valid way to send messages by three parties, when two of them shouldn't need to communicate?

Sorry for the edit, but my mind must have been elsewhere when I wrote the first post.

Answer 1

I think you are confusing things, if you use the Luhn algorithm, for example, it'll just return True or False on the checksum. The sample code you gave seems to indicate that you want to have some checksum result (ex. 12345) that can be hashed from two different values. This problem would be more difficult.

How will the third party create this value? Will you give them some Javascript code for them to execute, or some other language? Couldn't you have a shared secret key and they could symmetrically encrypt the value with that secret key, you could have them prefix the part they encrypt with some known value so you could verify it quickly.

Their code:

  to_send = encrypted(shared_key, 'check' + code)

Your code:

  unencrypted = decrypt(shared_key, to_send)
  if not unencrypted.startswith('check'):
    return False # failed check

Answer 2

OK, so you want no interaction between the other application and your application. And you would like to limit the codes to 6 characters. Here are my thoughts:

• Use 10 characters, that will make brute-force attacks harder;
• Use all Latin letters and digits - that will give you 36 possible character values;
• Why not use some big number library and simply multiply your code (taken as a Base36 number) by some ludicrously large value (say, 2048 random bits). Then convert it to Base36 and take the last 10 digits. Or maybe first 5 and last 5. Or maybe some other combination dependant on the original code. I've no idea how cryptographically strong this will be (probably not much), but the effort to crack the code will doubtfuly be smaller than simply paying for the service.
• Alternatively you could salt (prepend some secret string) your code and then calculate MD5 of it. Return the MD5 (or some N characters of it) to the user as your code. This should be pretty cryptographically OK, although I'm no expert. By converting the MD5 result to Base36 you could increase the strength of this algorithm.

Answer 3

Why a "checksum"? Can't the 3rd party run any little utility that you give them? All you need is a 5-digit encryptor that the 3rd party can run on their computer, feed the product code into, and send the 5-digit result to the client as the key code.

The encryptor always produces the same result from the same input.

Then, the client sends you the product code and the key code. You run the product code through an exact copy of that encryptor, and compare that result to the key code.

The security of this system can be enhanced without changing the fundamental architecture.

-Al.

Answer 4

Edit after some clarifications:

I still think that the product code and the matching 3rd party response cannot be constant - otherwise it can be shared will other users, which will thus be able to give the response code without going to the 3rd party.

If the product code is constant, a possible approach is that the 3rd party response depends on both the code and the user's phone number, and so is your validation. This way, each response is both product and user specific.

The specific permutation of the Luhn algorithm isn't too important in my opinion - if someone can crack one variation, he'll probably be able to crack another one.

Original Answer:

In short, I think you can use the Luhn algorithm, if you give the user a one-time ticket, valid for a limited amount of time.

• First, if I understand the problem correctly, your product code cannot be constant - otherwise the response created by the 3rd party will always be the same for this product. This means the user will be able to use this code again later, or even give it to another user.
• Therefore, I think you should generate and give the user a random new code per his request of information/access to the product. This code should be valid for this product for a limited period of time (an hour, a day, depending on your needs).
• The response sent by the 3rd party to the user should be valid only when entered together with the code you provided to the user.
• After validation, this code cannot be used until the specified time period is over.
• As an option, I think you and the 3rd party can append something like the current date to the code and response pair during computation, so they are not always the same pair.

Answer 5

After long debates with the 3 Party Company we've concluded that the best solution will be if they pass the Clients SMS to me, I generate a new code and send it back to them which in their turn send a new SMS to the Client with the code I generated. Not optimal from my point of view, but at least I can now do it in any way I want.

Thanks for your input thou.