4
$\begingroup$

I would like to learn more about a specific set of non invertible functions:

  • The function should accept 2 inputs: one hidden and the other visible. The output and the function should also be visible.
  • The hidden input will not change, the visible will.
  • The function should be deterministic. Collisions are acceptable given there are not too many.

An important requirement is that given a long enough hidden parameter 10-20 characters it will not be possible calculate the output of the function given another visible input (which includes not being able to calculate the hidden parameter…).

When I say possible to calculate I mean that one would have to basically brute force all the possible combinations for 10-20ish characters and that there is no simple mathematical shortcut.

This is my current algorithm:

x- hidden input string  
v- visible input string  

I first mix the inputs. Once one of them is finished append the rest of the other on the end, so for example :

if len(x)>len(v):
    s = [x[0],v[0],x[1],v[1], … ,x[len(v)],v[len(v)], … ,x[len(x)-1],x[len(x)]]

Now calculate the output by:

associating each character in s with a predefined number such as  

a:1  
b:2   
…

and

output = 1
for each item in s:
    output += truncate(sin(output+item)) // truncate for similar behavior
                                         // on different sin implementation

The output should be a number between -1 and 1.

Questions:

  1. Will this algorithm fulfill the requirements I mentioned above?

    More specifically – for the same hidden input, given multiple visible inputs and their associated visible outputs – can an attacker easily find the output for an additional visible input?

  2. How do I name these functions (So that I can read more about these constructs)?
$\endgroup$
6
$\begingroup$

If I understood your question correctly, you want a message authentication code (MAC). The "hidden input" is usually called key and the "visible input" is just the message. The output of the MAC is called tag (or also MAC).

The main security goal for MACs is resistance against forgery: It should be computationally infeasible for an attacker who does not possess the key to obtain a valid tag for any message whose tag they have not observed before.

Common variants of that primitive include HMAC, CMAC, or Poly1305-AES, just to name a few.


Now, about your algorithm: Usually, homebuilt ad-hoc constructions are a very bad idea. Unfortunately, I did not find a trivial way to completely break yours during the few minutes I thought about it, even though I'm sure the mathematical properties of the sine function are highly useful to attack it. However, if you look at the examples I just linked, you will see that these are quite a bit more complicated than your proposal — and there is a reason for that. Many simple constructions suffer from unforeseen vulnerabilities once examined a bit more carefully: My favourite example is the "keyed hash" $\mathit{msg}\mapsto H(\mathit{key}\Vert \mathit{msg})$, where $H$ is a Merkle-Damgård hash such as MD5, SHA1 or SHA2. This suffers from a length extension attack and is thus not a secure MAC even it may seem so at first.

The bottom line is: Crypto is hard. Please use one of the well-established primitives from a well-established implementation if you have to protect anything of importance.

$\endgroup$
5
$\begingroup$

The other answer already explains that what you are looking for is a message authentication code, but did not show a clear attack against your construction. At the very least it seems to be vulnerable to length-extension type attacks, like the keyed hash mentioned:

  1. Take the output for some known message, where the length of the key x and message v is equal.
  2. You can append one character to v and calculate the next output normally, forging a correct authentication tag.

Additionally, you can go backwards in the sine function using the inverse. Due to the truncation you may have a range of possible values for the previous steps, but you should be at least able to narrow down the options. That means you could be able to modify the last characters of the message and at least have a higher than random probability of having the correct MAC.

It also clearly leaks information about key bytes for a similar reason. Reusing a key would let an attacker learn more and more, and eventually recover the key. Typically MACs allow using the same key for (almost) any number of messages.

$\endgroup$
  • $\begingroup$ Oh right, I did not realize that s can end in a non-key byte. Nice answer. $\endgroup$ – yyyyyyy Jan 17 '16 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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