Is there a way to give out secure tickets wihout storing them?

Question

I'm building a website on which I want to make it very easy for users to create pages anonymously and later be able to come back and edit those pages. One way to do so is to give out confidential tickets which are derived from the page ID to those users when they create the page. Later I would be able to derive the page ID from the ticket and allow a user in possession of the ticket to edit that page.

Of course this needs to be secure, so: 1) third parties shouldn't be able to derive the page ID from a given ticket, and even more importantly: 2) third parties should not be able to predict the ticket for a given page ID.

I could of course easily do this by randomly generating the tickets and storing them in a database, however I would like to try and do this without having to store the tickets.

In other words I'm looking for something like this:

1. Let A be a unique public page ID.
2. Let S be some kind of unchanging master key or other secret I possess and don't give out.
3. Using S, transform A to B, such that I can later transform B back to A, but someone not in possession of S cannot.
4. It should not be possible, or be very hard, to derive S even if you have a large collection of A-B pairs.

Does such a process exist? One thing I thought of is a simple XOR, however that would be easy to crack with just a few examples of A-B pairs. I can't use a hash, because they are intentionally irreversible; I can't derive A from B if B is a hash of A.

Answer 1

This sounds like the perfect use of an HMAC. You create a secure random secret S. Then the ticket for each page will be ID + HMAC(S, ID). When you get a ticket you extract the ID, redo the HMAC and then compare your result with that in the ticket.

While this is likely be simpler and faster than an encryption solution, it will only work if you don't mind ID being in clear-text in the ticket.

Answer 2

Looks to me like standard public-key crypto should work. For example, using RSA (with public key N=p*q and e, private key d):

• S would be your private key d.
• Transforming: B = A^e mod N.
• Transform back: B^d = B mod N.

Your requirements seem to then naturally fit the security assumptions of RSA. The one wrinkle here is that anyone can compute B from a given A (which violates your original statement, but not the formal requirements below that). I think this can be fixed by keeping e private as well (and sufficiently large and random), but that would require more careful analysis.