Cipher Systems: possible extras

Wildon's Weblog 2018-03-12

This year I’m lecturing our course Cipher Systems for the first time. The purpose of this post is to record some of the ideas that I hope to at least touch on in the course.

Cryptocurrency (1) RSA Scheme

Of course the Bitcoin blockchain is a splendid advertisement for hash functions. But here I want to give a much simpler example of a toy cryptocurrency in the RSA setup.

TTTT (Totally Trusted Transmission Technology) is going into the cryptocurrency game. In readiness, its RSA modulus $N$ and encryption exponent $e$ are prominently posted on the corporate website. TTTT issues currency units by signing the string ‘TTTT promises faithfully to redeem BitFlop $x$ for £100′, where $x$ is the serial number of the relevant BitFlop. Let $f(x) \in \{0,1,\ldots, N-1\}$ be the number representing this string for BitFlop $x$ . (The function $f$ is public knowledge and is injective.) We say $f(x)$ is an unsigned BitFlop.

In the proposed protocol, a customer wishing to buy a BitFlop sends TTTT a self-addressed envelope stuffed with $20$ used fivers. TTTT removes the fivers and inserts a signed Bitflop $f(x)^d$ mod $N$ , neatly typed out on letterhead paper. The serial number $x$ is inscribed in red ink in the company’s ledgers. Alice, as well as anyone she gives the signed BitFlop to, can calculate $(f(x)^d)^e = f(x)$ , read the string containing the serial number, and know they have a legitimate BitFlop signed by TTTT. To redeem a BitFlop the postal process is reversed, and $x$ is crossed off from the ledger.

One of the many problems with this scheme is that there is nothing to stop a nefarious Alice (with access to a photocopier) from passing the same signed BitFlop onto both Bob and Charlie. To get round this, TTTT decides to publish its ledger of issued BitFlop serial numbers on the web, reasoning that Bob can then check that he has received an unredeemed BitFlop.

Another drawback is that if Alice buys a BitFlop from TTTT and then gives it to Bob, who then redeems it, TTTT can connect Alice and Bob. (Admittedly not necessarily as parties in the same transaction because of the possibility of a chain Alice to Charlie to Bob.)

Blind signing

To get around the second drawback, TTTT decides to use blind signing.

In the new protocol, if Alice wishes to transfer money to Bob, Bob (not Alice) gets TTTT to send him $f(x)$ , representing a `candidate-BitFlop’ with serial number $x$ . TTTT enters $x$ in a new ledger. Bob passes $f(x)$ to Alice, who calculates the product $a^e f(x)$ mod $N$ for some privately chosen $a$ . Alice then sends TTTT this number, along with the usual envelope of used fivers, and receives by return

$(a^e f(x))^d = a^{ed}f(x)^d = a f(x)^d \text{ mod } N.$

To transfer the BitFlop, Alice divides by $a$ and gives the signed BitFlop $f(x)^d$ to Bob. Bob can check that $x$ appears in the public ledger and later redeem the BitFlop. Over the course of the protocol:

Alice learns: $a$ , $f(x)$ , $f(x)^d$
Bob learns: $f(x)$ , $f(x)^d$
TTTT learns $f(x)$ , that Alice has paid for a signature of $a^e f(x)$ , that Bob has redeemed the signed BitFlop $f(x)^d$ .

Assumingly (generously enough) that TTTT has many customers, there is no way for TTTT to associate $f(x)$ with $a^e f(x)^e$ , or Alice’s transaction with Bob’s.

Question

What protection does BitFlop have against double spending?
TTTT decides it would be a nice touch to allow customers to choose their preferred serial number and encryption exponent. (TTTT knows the factorization $N = pq$ , so can easily compute the decryption exponent $d'$ for any invertible $e'$ . What could possibly go wrong?
While still depending on the postal system to receive used fivers, TTTT decides that email could be used for all other customer communications. Emails have to be encrypted, but no problem, TTTT already has $N$ and $e$ published on its website. What could possibly go wrong, under (a) the blind-signing scheme, (b) the original scheme?

Answers and discussion

TTTT is protected by its ledger system. Using a private ledger there is nothing to stop Alice passing the same BitFlop to both Bob and Charlie; if Bob redeems the BitFlop first, he gets its full value, while Charlie gets a nasty surprise later. Using a public ledger Bob and Charlie can verify the BitFlop is unspent at the time they accept it, but are then in a race to redeem it. (Switching from post to email doesn’t really help: it just means the race is run faster.)
This might be acceptable: for instance if Alice is in debt to Bob, and pays Bob by BitFlop, then Bob can simply wait for the envelope of used fivers to arrive before agreeing the debt is settled. Alice cannot settle two debts in this way, while Bob cannot plausibly claim to have had the transaction refused by TTTT when $x$ is removed from the public ledger.

In other cases, for instance if Alice wishes to purchase a physical object from Bob, some escrow system or degree of trust is needed even for less dubious schemes than BitFlop.
When Alice’s request for an encryption exponent $e$ such that $(e, \phi(N)) \not= 1$ is politely refused by TTTT, she learns a prime factor of $p-1$ or $q-1$ . This could be useful in a Pollard $\rho$ attack.
(a) Eve who is snooping on communications between Bob and TTTT, intercepts an encrypted message $M^e$ mod $N$ from Bob to TTTT. Eve sends $M^e$ mod $N$ to TTTT, along with the usual envelope of used fivers. TTTT, believing that $M^e$ mod $N$ is an obfuscated unsigned BitFlop $a^e f(x)$ mod $N$ , happily sends back $(M^e)^d = M$ to Eve. So for the price of one BitFlop, Eve has obtained the supposedly confidential message $M$ .
(b) One day Alice asks TTTT to start signing its messages. Clearly authentication is good practice, so TTTT agrees. A typical message from TTTT to Alice, signed using the hash function $h$ , is a pair $(M^{e_A} \text{ mod } N_A,h(M)^d \text{ mod } N)$ . Alice notes that any email to TTTT is immediately bounced back with response `Dear Ms. Alice, your custom is important to us. TTTT will reply within four months …’. She carefully crafts a message from a Ms. TYH!ubN(CZ…, such that TTTT’s automatic response $M$ has hash $h(M) = f(x)$ for some serial number $x$ . (Again this is rather easy if $f$ is bijective.) The signed message is then $(?, f(x)^d \text{ mod } N)$ , giving Alice (and anyone else snooping) the signed BitFlop with serial number $x$ . Of course this $x$ does not appear in the company’s ledger, so this is most obviously a problem for the first scheme. But even with the public ledger, a malicious Alice can bombard TTTT with emails and so acquire a large number of ‘protoBitFlops’. Publishing each $f(x)^d$ destroys an unledgered BitFlop $x$ , and creates a race to redeem if $x$ is already in the ledger.

The Boomerang Attack

For the moment this is just a link to Wagner’s original paper.

Cryptocurrency (2) Block chain

Linked lists of type Int may be defined in Haskell by Data List = Empty | Cons Int List. For example Cons 2 (Cons 1 Empty) represents the list [2,1]. We define an analogous data type HashList in which each a cons-cell with data $x$ is argumented by a hash value $h$ . At the level of types $h$ could be any Int, but in a well-formed hash list, we will suppose that $h$ is the sum of the hash of $x$ and the hash of the tail of the list. Assume that hashInt :: Int -> Int has already been defined.

   type Hash = Int   data HashList = Empty | Cons Int Hash HashList   hash :: HashList -> Hash   hash Empty = 0   hash (Cons _ hashValue _) = hashValue   cons :: Int -> HashList -> HashList   cons x tail = Cons x h tail       where h = hashInt x + hash tail

For example, if (to make a simple illustration) hashInt x = x*x then the hash list with data 3, 2, 1 is

   Cons 3 14 (Cons 2 5 (Cons 1 1 Empty))

the hash values being $1^2 = 1$ , $2^2 + 1 = 5$ and $3^2 + 5 = 14$ . Note that data values contribute to the hash (albeit at the head only) as soon as they enter a hash list.

As defined above, hash lists provide warning of accidental corruption. But they offer no protection against malicious corruption. Indeed, the function cons allows anyone to create well-formed hash lists having arbitrary values.

In the Bitcoin blockchain, malicious corruption is prevented—or at least, made as hard as inverting a one-way function—by digital signatures. Again I find the Haskell code the clearest way to present the idea. We assume there is a basic public key infrastructure in place, including functions with the types below such that (unsign m) . (sign m) is the identity for each person $m$ .

   type Person = Int   sign   :: Person -> Int -> Int   unsign :: Person -> Int -> Int   type SignedHash = (Person, Int)   data BlockChain = Empty                    | Cons Int SignedHash BlockChain   signedHash :: BlockChain -> SignedHash   signedHash Empty = 0   signedHash (Cons _ signedHash _) = signedHash   cons :: Person -> Int -> BlockChain -> BlockChain   cons m x tail = Cons x (m, (sign m h)) tail       where h = let (_, h') = signedHash tail                in  hashInt m + hashInt x + h'

It is a simple exercise to write a function verify :: BlockChain -> Bool that checks a block chain is valid.

    verify Empty = True    verify (Cons x (m, h) tail) =          let (_, h') = signedHash tail      in  unsign m h ==    hashInt m + hashInt x + h'                         && verify tail

Note that verify only calls the publically known function unsign m. For example, if (thanks to an appalling programming error swapping encryption and decryption functions in Diffie–Hellman), Person $0$ 's signature function turns out to be $x \mapsto x^3$ (modulo some large RSA modulus) then the block chain with data 3, 2, 1 is

   Cons 3 (0, 134*134*134) (Cons 2 (0, 5*5*5)                           (Cons 1 (1, 1*1*1) Empty))

which passes verification. (Person $0$ is particularly unfortunate in that his identity enters the hash by adding $0^2$ .) A well-formed length one block chain Cons x (m, sign m (hash x)) Empty is equivalent to a signed $x$ from Person $m$ .

Using BlockChain one could implement a simple cryptocurrency, along the lines of the 'ScroogeCoin' considered in the recent book Bitcoin and cryptocurrency technologies (draft available online). Here Scrooge is a trusted party who must sign every transaction, and has sole responsibility for the integrity of the currency. The brilliance of Bitcoin lies in how it achieves decentralization by rewarding (with Bitcoins) anyone willing to play the role of an honest Scrooge, while still thwarting double spending.

A minimal working implementation of BlockChain is available here.