Cryptocurrency

Throughout this chapter, we've followed the development of DragonBucks (which was succeeded by CryptoniaCoin) and learned how certain mathematical functions can be used to secure a currency system.

However, along the way we hinted at some potential security flaws with the Cryptonian system, and you may have picked up on some of them yourself.

In this exploration, we’ll point out some of the weaknesses of CryptoniaCoin and start to look at ways to resolve them. We won’t be able to patch all the security holes in this quiz, but we will address each of them by the end of the course.

Cryptonian Vulnerabilities

                       

One requirement of the CryptoniaCoin system is that we're able to represent everything as numbers. This means that we need a way to convert transaction notes into a unique message{\tt message} (which is also a number).

Consider a simple way for converting a transaction note to a number: concatenate the transaction amount, the public keys of the parties involved, and the date. For example, if we wanted to send 1515 coins from the account (pk:5284)({\tt pk: }5284) to account 42954295 on 10/17/2019,10/17/2019, then message=155284429510172019.\tt message = 155284429510172019.

What’s wrong with this method of converting a transaction note into a number?

Assume that all account numbers are the same number of digits and the date is always expressed with 88 digits.

Cryptonian Vulnerabilities

                       

Suppose you wrote a note to buy a loaf of bread, but then realized you actually needed two loaves of bread, so you go back to the store and write another note to buy the second loaf.

If the cost of each loaf is the same, you pay using the same account, and it’s on the same day, then using the system we proposed on the last pane, those two notes would be converted to the same message.\tt message. This is problematic because the two identical messages would have the same signature, so either

  1. you would have to disallow notes that are a copy of an existing note (which is inconvenient), or
  2. someone could use unlimited versions of the same note once they have the valid signature of the first note (which is not secure).

Cryptonian Vulnerabilities

                       

Suppose we make a rule that notes that are identical to an existing note are automatically invalid. Then, if you tried to use two notes with the same message\tt message and the same signature, only the first would be honored.

If we want someone to be able to make two similar payments on the same day, we could try changing the way the message\tt message is constructed:

  1. the message\tt message could include the precise time in addition to the date, or
  2. the date could be replaced by a "transaction counter" associated with the sender's account that increments by 11 for each new transaction.

Would either of these changes allow you to make two similar purchases on the same day?

Cryptonian Vulnerabilities

                       

For security, we never want a signature to be able to be used more than once, even for similar transactions. Fortunately, there are relatively easy fixes we can implement so every transaction results in different message numbers and therefore requires different signatures.

Different cryptocurrencies use different techniques to make this work in practice, and they’re all valid.

Because the fixes are relatively easy, this doesn’t represent a major security concern for cryptocurrencies, but it's something we need to be conscious of when designing a verification scheme.

Cryptonian Vulnerabilities

                       

In DragonBucks, the dragon doesn’t need to know anyone’s secret key — the system we built allows anyone to verify signatures. Whether you’re in charge of updating the account tallies or not, you can verify a signature using public information.

However, if you don’t tell the dragon (or anyone else, for that matter) your secret key, then there's no one to ensure that it’s actually different from everyone else's.

If you did have the same secret key as someone else, it would be pretty obvious since you’d also have the same public key. But you could also have a different secret key from someone else, yet still have the same public key.

Cryptonian Vulnerabilities

                       

We can see this using the calculator below, which implements the modular arithmetic of the DragonBucks system.

Try using n=29,g=17,s=35,n = 29, g = 17, s = 35, and an mm of your choosing. Next, use the same n,g,n, g, and m,m, but set the secret key s=64.s = 64.

With the sample values above, s=35s=35 and s=64s=64 should lead to the same public key. If you had the same public key as someone else but a different secret key, would your accounts be distinct?

Cryptonian Vulnerabilities

                       

Even if the modular arithmetic of our system protects someone else from being able to back-calculate your (smodn)\left(s \bmod{n}\right) from your publicKey\tt publicKey or a signature\tt signature you've issued, it's still possible for someone else to pick the same public key for themselves by chance.

If you have the same publicKey\tt publicKey as someone else, that means that your secret keys are the same in mod n,\text{mod }n, i.e. smodn=smodn.s^\prime\bmod{n} = s \bmod{n}. Though you each have a distinct secretKey,\tt secretKey, for the purposes of the Cryptonian message-signing system, your accounts are practically the same. You would be able to sign valid messages on behalf of each other.

This represents a big security flaw — if you happen to choose the same secret key that someone else is already using, then you’d be able to spend all their money.

What could we do to reduce this security risk (while keeping the rest of the system the same)?

Cryptonian Vulnerabilities

                       

Even if controlling the issuing of keys did work, it would require trust in a central authority that controlled those keys, representing a fundamentally different type of currency.

While it may seem strange, the best protection against someone else having the same public key as you is simply increasing the number of possible public keys. The more possible public keys there are, the less likely you are to find someone else’s (whether you’re trying to do it or not).

Just how many possibilities we'd need for the system to be considered "safe" will be explored later in this course. But to give you a preview, some real systems use secret keys long enough that it would take more than 1050\sim10^{50} random guesses before you could expect to replicate another user's key.

Cryptonian Vulnerabilities

                       

We claimed the Cryptonian system is secure because you can share your public key, (g×s)modn,(g\times s) \bmod{n}, without revealing the value of smodn.s \bmod{n}. Indeed, you can't invert (undo, in other words) modular multiplication by simply dividing by the original factor and applying mod,\bmod{}, e.g. (g×s)modng=?smodn,\frac{(g\times s) \bmod{n}}{g} \stackrel{?}{=} s \bmod{n}, but that doesn't mean it's impossible.

If we did have a way to "modularly divide" by g,g, then smodns \bmod{n} would not be safe. Let's take a closer look at what it would take to do so.

Suppose that, instead of dividing by g,g, we multiply by another constant k.k. The goal would be for kk to have the following effect: (k×publicKey)modn=smodn.\left(k\times \texttt{publicKey} \right) \bmod{n} = s \bmod{n}.

What property would we need kk to have for this to work?

Cryptonian Vulnerabilities

                       

If we could find kk such that (k×g)modn=1,\left(k\times g\right) \bmod{n} = 1, then it would allow us to "modularly divide" by gg. We call the kk that satisfies this equation the "modular multiplicative inverse" of g,g, and denote it g1g^{-1} (not to be confused with the reciprocal of gg outside of modular arithmetic). So the g1g^{-1} that lets us "divide" by gg must satisfy the equation:

(g1×g)modn=1.\left(g^{-1}\times g\right) \bmod{n} = 1.

Even though we multiply g1,g^{-1}, it’s effectively modular division since multiplying by g1g^{-1} cancels gg from the expression in modn:\bmod{\>n}: g1×publicKey=(g1×g×s)modn=(1×s)modn=smodn.\begin{aligned} g^{-1} \times \texttt{publicKey} &= \left(g^{-1}\times g \times s\right) \bmod{n} \\ &= (1 \times s) \bmod{n} \\ &= s \bmod{n}. \end{aligned} In effect, we use g1g^{-1} to unlock smodn.s\bmod{n}.

For small nn, we can find a g1g^{-1} quickly with just guess and check.

Suppose the Cryptonians chose g=5g=5 for their system. What is 515^{-1} in mod7?\bmod{\>7}?

You can use the modular calculator below to help to find the answer.

Cryptonian Vulnerabilities

                       

The existence of g1g^{-1} is what fundamentally threatens the security of our modular multiplication verification scheme. For a small nn like the one we just looked at, you can find g1g^{-1} through guess and check without taking too long and easily crack the system.

Making nn bigger will protect against this simple guess-and-check strategy, but as it turns out, there are more efficient ways to find g1.g^{-1}.

In the next chapter, we’ll see why this security hole can’t be plugged without changing some of the functions that make up our verification scheme, and what properties we need those functions to have in order to be sufficiently secure for a cryptocurrency.

See you there!

Cryptonian Vulnerabilities

                       
×

Problem Loading...

Note Loading...

Set Loading...