Hacker News Reader

Comment by wslh | Hacker News Reader

I offered something similar here [1] and it is used by many companies including Philip Morris, and the Argentinian tax agency for the same purposes.

The technique I used (I should publish it as open source) is using a Feistel cipher [2] with a key. The Feistel network could be adjusted to almost any size and the key used in every round is an expansion of a general key using a key derivation function [3] (KDF3 if I remember well).

Basically it is a symmetric cipher of arbitrary size.

[1] https://www.nektra.com/products/secure-coupon-code-generator...

[2] https://en.wikipedia.org/wiki/Feistel_cipher

[3] https://en.wikipedia.org/wiki/Key_derivation_function

View on HN

Interestingly, it seems there might have been independent invention of the same idea[0]. Have you checked for any patents in the space?

[0] https://bytes.grubhub.com/why-we-use-crypto-when-generating-...

Thank you for the article. I was not aware of that article. My first implementation was done in 1997 or 1998. I am involve in computer security for three decades and I was familiar with Feistel networks. I am not a cryptographer but I have reverse engineered algorithms using this structure. Never checked patents because I think this is a natural construction and I always wondered why there were no other public ideas around this problem. This is not the first time it happened to me.

I'm not a cryptographer and did not understand half the things you said except symmetric crypto.

I think there are 2 problems with this approach:

How do you prevent the double spend problem, for example duplicate entry tickets. You would have to mark the ticket as used in a central database anyway to prevent it

What happens if the secret key material is compromised? Anyone can issue new valid numbers, etc..

Please correct me if I'm wrong.

No problem, the two answers here:

1/ You don't have duplicates because a Feistel network assures you there is no duplicates: every input has a different output with a fixed key in every round.

2/ If the secret is compromised anyone can issue valid numbers in the same way that if your secret encryption keys for encrypting your data exposes it. The idea is that the secret key material is never compromised as it is assumed in all security cases. You should custody with the right measures based on the attack vectors you have. The custody of secrets is independent of this method.

Please let me know if you have more questions.

>The idea is that the secret key material is never compromised as it is assumed in all security cases.

That's not true, we have (perfect) forward secrecy, backwards secrecy and key rotation mechanisms because we often care what happened after the key is inevitably compromised. In this case the problem makes it hard to "rotate" the keys in a meaningful way, but I'm yet to see a proof it's impossible.

I think we are talking about different things here or the conversation is not clear.

The assertion you mentioned is the "what" assumption while what you said is the "how" we came to that assertion. Most probably you take my word idea in a specific sense other than I wanted to use. My answer was informal because we are here in HN and not writing a paper.

Feistel ciphers are a good technique for doing just this but it's also worth noting that if all you are looking for is "produce a pseudorandom permutation of 1..N without actually shuffling a list of numbers" you can also use an LFSR as well.

The difference is that the method is more secure than an LFSR.

of course, but an LFSR is going to be faster (provided you have a reasonable number of rounds in your Feistel cipher), have some situationally desirable statistical properties and is easier to adapt than a format-preserving encryption technique like a Feistel network.

Sorry, but faster for the computing capabilities we have in every electronic device is no significant in the application. I have not seen a customer inquiring about the speed of this process. They were looking to a method that is more secure than others.

For example, in the case of Philip Morris was about winning prizes and imagine if they tried other methods before where some smart people reversed the method.

Securecouponcodes.com is down. Was looking for PHP example.

Reply on news.ycombinator.com