twitter logo linkedin logo facebook logo

The Carnac protocol – or how to read the contents of a sealed envelope

Dr Michael Scott

Johnny Carson as long time host of the Tonight show often appeared in the spoof role of Carnac the Magnificent, a mentalist who could magically read the contents of a sealed envelope. This is in fact a well known stock-in-trade trick of the mentalist’s craft, known as “billet reading”. Here we propose a cryptographic solution to the problem of billet reading, apparently allowing a ciphertext to be decrypted without direct knowledge of the ciphertext, and present both a compelling use case and a practical implementation.

Download this Paper and learn about the Carnac Protocol

1 Introduction

A credit card owner, a customer of a credit card company, wants to carry his credit card number (CCN) around on his mobile phone, but stored in an encrypted form (lest his mobile phone should be stolen), that is tied to his identity. We call this the Ciphertext. However no encryption or decryption keys are available to the owner. So although the owner may know his own credit card details, the owner cannot either encrypt another’s details, or indeed decrypt his own Ciphertext.

At some point the owner decides to make a purchase from a merchant. The merchant knows nothing about the owner or their credit card, and has nothing stored locally related to either. Ideally the credit card owner wants to enter into a protocol with the merchant using the Ciphertext such that (a) the merchant learns nothing about the Ciphertext (lest a dishonest merchant should use the Ciphertext for their own purchases), but nonetheless (b) the merchant is able to determine the credit card number and the associated authenticated identity of its owner.

An immediate objection might be that in this scenario a stolen Ciphertext is as good as a CCN, as it can clearly be used to make purchases from the merchant. Later we shall show how, in a practical implementation, the Ciphertext can be adequately protected just using a short PIN number. Using a PIN number to protect credit card transactions is a well known and trusted mechanism, and the same familiar PIN can be used here.

Clearly a trusted authority (TA) must be involved, probably belonging to the credit card company, as otherwise there is no way to encrypt the CCN. Assume that this TA is known to both the customer and the merchant. The TA has its own master key s. The customer approaches the TA who encrypts the CCN using the encryption keys to create the Ciphertext Es(CCN), which is given to the customer. Note that it is not essential that the customer actually knows their own CCN. The TA also issues to the merchant a value Ds, derived from s, but from whichs cannot be extracted.

The idea now is that the customer should be able to enter into a protocol with the merchant, using Es(CCN), such that the merchant ends up knowing CCN and the identity of its owner, but in the process learns nothing about Es(CCN). By analogy the customer is able to magically determine CCN without touching the “sealed envelope” that is Es(CCN). The trick is (and there has to be a trick!) is that the mentalist/merchant has in their possession the apparently unrelated secret Ds.

For the purposes of this paper we assume that a credit card number consists of 5 blocks of 4 decimal digits each.

2 A simple authentication protocol

To realise our solution, we will use pairing-based cryptography. To be concrete we assume the use of a BN elliptic curve [1] at the AES-128 level of security. This is (and for our purposes must be) a type-3 pairing [3], where e : G1 × G2 GT. The groups G1,G2 andGT are all of the same prime order q. We make standard pairing-based security assumptions, including the XDH assumption that the decisional Diffie-Hellman problem is hard in G1.

First consider a simple protocol, in which a client tries to authenticate its identity to a server. We assume that the server is authenticated to the client in a standard way, perhaps using the well known SSL protocol. HereID is the client identity andH1(.) is a hash function which hashes its input to a point on G1.

This protocol attempts to prove in zero knowledge to the server that the owner of the claimed identityID is in possession of the valuesA issued to it by the TA, where A = H1(ID). The same TA has issued the secretsQ G2 to the server, whereQ is a fixed public point in G2. Correctness follows immediately from the well known bilinearity property of the pairing. See Table 1.


Table 1: A simple authentication protocol

Table 1: A simple authentication protocol


As an authentication protocol this has some obvious deficiencies (for example it is subject to a simple replay attack), but for the moment we will ignore them. Next we introduce a small errorϵ into the client’s secret sA. See Table 2.


Table 1: The subliminal channel

Table 2: The subliminal channel


Observe now that the value ofg as calculated on the server side can be used to recover ϵ. Strictly speaking as an authentication protocol we might consider that the authentication has failed. Or we may permit a small deviationϵ and judge the authentication a success. In either case we claim that the successful transmission ofϵ represents a secure narrow-band subliminal channel [6] whereby a short secretϵ can be communicated from the client to the server.

For the server to findϵ requires the calculation of a pairing and the solution of a discrete logarithm problem in GT. The appropriate algorithm is the method of Pollard’s Kangaroos [4]. This is a “square root” algorithm, which means that for a 4-digitϵ usually only a few hundred multiplications inGT will be required to find ϵ, which is completely practical.

To establish the security of the subliminal channel consider a powerful passive observer who has recorded the communication and subsequently somehow captures the un-adjusted client secret sA. Now they are in possession of sA,xA and x(s - ϵ)A. However even this does not reveal ϵ, as a consequence of the XDH assumption,

Finally we upgrade our protocol to use a non-interactive version of a provably secure zero-knowledge protocol for proof of identity [2], section 5.3, introducing a time stampT to prevent replay attacks. See Table 3, where the hash functionH(.) hashes its input to an element in Fq, and the symbol| indicates simple concatenation of the inputs.


Table 1: The final protocol

Table 3: The final protocol


3 Our use case solution

The way forward is now quite straightforward. The TA issues to the customer whose identity is proven to beID the secrets (s - ϵn)H1(ID|n) whereϵn is n-th block of 4 digits of the CCN. This is done for each of the 5 blocks of the CCN, forn = 1 to 5. This now constitutes our ciphertext Es(CCN). On the server side Ds = sQ. To communicate the CCN to the merchant’s server, we run the above protocol 5 times. In practice the 5 client to server communications can all be batched into a single blob of data, sharing the same time-stamp.

4 Discussion

In the particular use case considered here, the identity used in the protocol is of no particular significance, and may be a pseudonym in a predetermined format to preserve anonymity. However this identity is authenticated in the course of the protocol, and is assumed to be bound to the associated CCN in the back-office payment centre.

To protect the Ciphertext a simple idea borrowed from [5] is to subtract from each component of it a PIN number, so that the secrets are now (s - ϵn - PIN)H1(ID|n). This PIN can then be re-inserted when the protocol is run. Clearly without the correct PIN, a valid CCN will not be received by the server.

If the merchant’s secret is stolen then clearly all captured Ciphertexts can be decrypted. However a stolen merchant secret cannot by itself be used to make purchases from honest merchants.

To remove any single point of failure, the TA can be distributed. In the simplest scenario the client can retrieves1H1(ID) from one TA,s2H1(ID) from a second TA, and simply add them together to create sH1(ID), where s = s1 + s2. In this case the adjusted secret for our use case would be created by subtracting theϵi from just one of the TA master secret shares. Also the equivalent server secretss1Q ands2Q can be applied separately ase(X,sQ) = e(X,s1Q).e(X,s2Q) due to the bilinearity property of the pairing.

An alternate viewpoint would be to observe that the original input secret, if protected by a human-memorisable password, might be subject to an off-line dictionary attack. Here we first convert the secret to be protected into a form where it is no longer vulnerable to such an attack, and indeed can be protected by a simple PIN number.

References

1. P.S.L.M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. In Selected Areas in Cryptology – SAC 2005, volume 3897 of Lecture Notes in Computer Science, pages 319–331. Springer-Verlag, 2006.

2. M. Bellare, C. Namprempre, and G. Neven. Security proofs for identity-based identification and signature schemes. In Eurocrypt 2004, volume 3027 of Lecture Notes in Computer Science, pages 268–286. Springer-Verlag, 2004.

3. S. Galbraith, K. Paterson, and N. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156:3113–3121, 2008.

4. J. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32, 1978.

5. M. Scott. Authenticated ID-based key exchange and remote log-in with simple token and PIN number. Cryptology ePrint Archive, Report 2002/164, 2002. http://eprint.iacr.org/2002/164.

6. G. Simmons. The subliminal channel and digital signatures. In Eurocrypt 1984, pages 364–378. Springer-Verlag, 1985.

Get the MIRACL memo in your inbox

Get in touch to learn more

You can opt out at any time. See our privacy policy here.