Saturday, August 13, 2016

Cabinet of curiosities: A bunch of cryptographic protocol oddities

In this short trivia article I will list a few unusual cryptographic design choices in some real applications/protocols. Specifically, I will focus on two types of “oddities”.

1) Unusual or weird design choices, maybe bordering voodoo/superstitions territory.

2) Choices that may have been very reasonable historically, but will be perceived as unusual for a reader in 2016 who has the benefit of hindsight.

I will not list design choices that have simply been broken, instead focusing on oddities that are maybe more interesting. Hopefully it will make you say WTF at least once. :-)

We have learned a lot over the years, and protocols designed by experts in the year 2016 are typically fairly sane, at least lacking in surprises. That was not always the case however, leading to choices that were made with a poorer understanding of cryptography engineering than what we have today.

The point of this article is not to point fingers or make fun of designs. It is simply to highlight design choices that may have made sense with the knowledge we had of crypto design at the time when the protocol was designed. Some of the choices may still be controversial.

Oddity: Unexplained “strengthenings”

Sometimes you come across a design that does some unusual construct to make the design “stronger”, without explaining why the construct is needed or how it works. This kind of cargo culting is especially common in non-cryptographers hobby designs, but sometimes it gets deployed broadly. One interesting example of this is in MS-CHAP v2.

MS-CHAP v2 is Microsoft's version of the CHAP protocol, used among others as an authentication option for PPTP. It implements a challenge-response mechanism that as a very high level works like this: The server sends the client a challenge message. The client hashes the combination of a challenge and a secret. The server verifies by doing the same (the secret is shared).

The protocol is described in RFC 2759 (so it’s quite old) and the main curiosity in this protocol is revealed in the function GenerateAuthenticationResponse. After (roughly) hashing the password/secret and the challenge, it ends with hashing in a magic 41 byte string called Magic2. So roughly it does the following, ignoring some detail.

Digest = SHA1(password || challenge || Magic2)

What, you may ask, is Magic2? It’s the following string: "Pad to make it do more than one iteration".

The reason for hashing in this string is not explained, but you can only guess that the protocol designer wanted to make the SHA function do more work, or be “more random”, by lengthening the input string enough to make it longer than 512 bits, the block size of the SHA-1 algorithm. An input longer than the block size makes SHA-1 do one more iteration in the hashing step, as explained by the string.

Oddity: Hedging against future breaks (in hindsight)

Being conservative is often good when designing cryptographic protocols. There are many cases when protocols and applications decide to use two different primitives in the same class to still offer some security in case one of the primitives is broken. That’s often a good idea, but may lead to surprises down the road for people who have the benefit of hindsight. One such surprise can be found in TLS version 1.1 and older, for people who read the spec today (or in recent years).

When setting up a TLS connection the client and the server need to construct keying material that is used as keys for various cryptographic primitives. A pseudo random function is used to construct new pseudo random strings from an original pseudo-random string. In TLSv1.2, this is simply done using SHA-256 in a specified way.

In TLSv1.1 and older, however, there were concerns which hash algorithm to use. The outcome? A function that uses both SHA-1 and MD5, XOR:ed together. (For completeness: there is another part of the TLS 1.1 protocol that instead use a MD5 and SHA-1 hash concatenated together).

The original rationale was that, if one of the hash functions is broken, there’s a “hedge” by still having hopefully one that is not broken. Is this reasonable? Most certainly. The decision to change the function to use SHA-256 only, in the design of TLSv1.2, was controversial. If you are interested in the discussion, see for example the discussion “[TLS] PRF in TLS 1.2” from 2006, on the TLS IETF mailing list.

Oddity: Protocols designed in the 90:s have weaknesses due to iterative improvements on a legacy base

Highlighting problems with OpenPGP is maybe beating a dead horse, but it highlights well the generic problem of bolting on security on a 90:s era protocol.

The current version of the OpenPGP specification, as implemented in for example GPG, is mostly backwards compatible with older versions of the specification, which were designed in the olden days. This leads to a few problems with OpenPGP that are well known. I will list two of them.

#1. If you sign, but not encrypt, a message, then the signature does not include some of the metadata in the OpenPGP message. For example, there’s a metadata field that includes the proposed file name of the signed data. This field name can be tampered with and the signature check will still hold.

$ echo "hello world" > helloworld.txt
$ gpg --sign helloworld.txt
$ sed 's/helloworld.txt/tamperedxx.txt/' helloworld.txt.gpg >
helloworld.txt.gpg.tampered
$ gpg --verify helloworld.txt.gpg.tampered
... gpg: Good signature from …

#2. In the original Pretty Good Privacy specification there were no support for integrity protecting messages. Nowadays it’s standard practice to not touch (decrypt) a message before the MAC has been verified. That was not the case in the 90:s. When the OpenPGP RFC 4880 spec was written, integrity checking was “bolted on” the old design. It works like this:

You hash the plaintext with SHA-1. Then you append the SHA-1 hash to the end of the plaintext. Then you encrypt the combination of the plaintext and the hash. So it’s “MAC”-then-Encrypt.

The RFC is pretty apologetic about this design choice. I quote RFC 4880 section 5.13 (here “MDC” means Modification Detection Code):

It is a limitation of CFB encryption that damage to the ciphertext
will corrupt the affected cipher blocks and the block following.
Additionally, if data is removed from the end of a CFB-encrypted
block, that removal is undetectable. (Note also that CBC mode has
a similar limitation, but data removed from the front of the block
is undetectable.)

The obvious way to protect or authenticate an encrypted block is
to digitally sign it. However, many people do not wish to
habitually sign data, for a large number of reasons beyond the
scope of this document. Suffice it to say that many people
consider properties such as deniability to be as valuable as
integrity.

OpenPGP addresses this desire to have more security than raw
encryption and yet preserve deniability with the MDC system. An
MDC is intentionally not a MAC. Its name was not selected by
accident. It is analogous to a checksum.

Despite the fact that it is a relatively modest system, it has
proved itself in the real world. It is an effective defense to
several attacks that have surfaced since it has been created. It
has met its modest goals admirably.

Consequently, because it is a modest security system, it has
modest requirements on the hash function(s) it employs.

Oddity: Too many knobs leads to difficulty reasoning about security

This entry is maybe less exciting, and more problematic, than the other ones, but are still worth discussing. A design feature of IPSEC is that it allows a lot of flexibility. Maybe a bit too much flexibility. With great power comes great responsibility, and it’s quite easy to configure IPSEC in a potentially problematic way.

To recap, IPSEC supports a few different protocols, each with their own cryptographic goal. One of the protocols is called ESP, Encapsulated Security Protocol. It can provide confidentiality and (optional) data origin authentication for the encapsulated packet. Another protocol is called AH, for Authentication Header. It provides only data origin authentication for the payload.

The flexibility gotchas of IPSEC are many. The administrator can configure his deployment to use either AH or ESP for data origin authentication. You could also skip authentication altogether, as the ESP packet has support for not using this. To further complicate things, AH and ESP could be applied in any order: first AH then ESP. Or first ESP then AH. To even further complicate things, IPSEC then allows for both encrypt-then-MAC and MAC-then-encrypt configurations.

This does not even mention the various cryptographic primitives each of the protocol supports, that give even more choice during setup.

IPSEC is, arguable, an instance of the problem of giving too many knobs to the user, and very little guidelines how to not shoot yourself in the foot. Fortunately as of 2016 there are lots of advice on how to configure IPSEC by the vendor implementations and other documentation (see for example RFC 7321 from 2014), but it can be argued it’s still problematic that the protocol offer so many options. Newer protocols typically go the other way: allow as little room for screwing up as possible.

(Minor) Oddity: Status quo vs personal choice

Daniel J Bernstein is arguably one of the most influential cryptographers (and cryptographic engineers) working for the internet today. He also seems to be the only one who has a soft spot on using little endian representations of integers in his cryptographic designs. This in a world that is largely dominated by big endian protocols.

Is this a security issue? Of course not. And it may or may not lead to some performance improvements in some cases. It does, however, lead to to less unified designs, and maybe some bikesheds.

Conclusion

In this article I’ve shared a few unusual creations. If you know others, please share your favorites.

Wednesday, December 23, 2015

I challenge you to compute this: Specializing BREACH and Cross-Site Search attacks to steal private keywords

In the real world there are many cases when we are more interested in how well a system protects a few specific keywords, rather than how well it can secure data “in a broader sense”. If an attacker can learn those keywords (say medical history/diagnosis), then the system’s security fails from the perspective of the user.

In this article I will try to raise awareness of two side channel attacks that are often practical in stealing such strings. Specifically, I want to emphasize how these two known attacks can be used against websites to exfiltrate private information about a user by associating the protected data with a set of sensitive strings, such as from a domain specific dictionary.

The question that I want you to keep in the back of your mind when reading this article is: As an engineer, what kind of data am I actually protecting? Is the data I’m protecting a sensitive set of words from a small corpus, and how do I deal with the fact that the data I’m protecting is “low entropy”?

As an attacker, can I learn something sensitive even without decrypting your TLS channel, circumventing the same-origin policy, or by taking over your account? Everyone likes to steal session tokens, but do I really have to, to get the user data? Can’t I just throw my sensitive keyword at the target and see if it sticks?

A Contrived Example To Get Started: Payload length

Say that your doctor office launch a website, https://getmydiagnosis.foo (to the horror of the security and privacy community). After logging in you are presented with a /diagnosis endpoint which, due to this being an early beta, will print one of the following two strings to the user:

“You are healthy!”
“You have cancer! Here’s some information about that…”

What do I do as an attacker sniffing your connection? I look at the TLS length fields or TCP packet lengths. The data is very well encrypted, but because the content that is encrypted is only one of two options I can use some other information (packet lengths) to figure out what is encrypted. I have learned the plaintext even without decrypting it.

The important point in this silly example is as follows: what we really want to protect here is the keywords “healthy” and “cancer” (or even just the binary predicate of the presence of one of those). The description text is often not really important at all from a privacy perspective.

About BREACH: A compression side channel

Let us take a less contrived example. Go to any popular website and look at the HTTP traffic. You are likely to find that the payload, be it HTML or JSON or XML, is compressed.

Content-Encoding: gzip

The whole idea of compression is to make the output data “shorter” in a sense. The string "hello world, the world says hello!" will intuitively compress better than a string of random characters, because of the re-use of the substrings “hello” and “world”. If I as an attacker can inject a string that will be reflected in a payload that is then compressed, then I can exfiltrate some private data by trial, error and observation.

Let us look at the doctor example again. This time the website is out of beta and is capable of listing all possible health issues, not just two options. Once logged in you are taken to the following page that unfortunately tells you that you have cancer and that you should contact your doctor's office for more information.

https://getmydiagnosis.foo/diagnosis?office=Stockholm
.. Cancer .. Stockholm


The payload is compressed and sent over TLS. For the sake of this example the query parameter “office” is reflected in the payload, whereas the rest of the data is not (say it’s pulled from a database). If I can make the target I’m attacking visit the specially crafted page:

https://getmydiagnosis.foo/diagnosis?office=Cancer
.. Cancer .. Cancer


Then the payload will compress slightly better if the diagnosis (the static content) is Cancer compared to strings not in the static content. Armed with a dictionary of diseases, I want to force the target to visit all these pages and record how well the data compress, by looking at packet lengths:

https://getmydiagnosis.foo/diagnosis?office=Flu
.. Cancer .. Flu
https://getmydiagnosis.foo/diagnosis?office=Mononucleosis
.. Cancer .. Mononucleosis
https://getmydiagnosis.foo/diagnosis?office=Cancer
.. Cancer .. Cancer


Doing this, I can maybe learn your diagnosis.

How do I make the target visit those specially crafted pages? For one, if you can inject data in a WiFi network, just look after a non-https traffic (the target may have many tabs open for example) and inject something like

<script src="https://...">

Which often works, especially if the website lack CSRF protection. You can also trick the user into visiting your website that does the above.

This class of attacks works better the less noisy the target endpoint is. JSON xhr endpoints that reflect input via a GET query parameter are often very nice to attack as they are much less noisy than if data is embedded directly into a large HTML payload.

Let's take a step back here and think about what the above attack means:

If I as an attacker have domain knowledge about what the plaintext can be, and the plaintext can be from a limited set of strings, I can quite easily (in some cases) learn your information without decrypting the TLS channel.

About Cross Site Search attacks: A timing side channel

A consequence of the BREACH attack is that it only works in practice if I can record packet lengths. That is how I learn if the injected data compress well or not.

A similar side channel attack that works in many cases is to do a cross site request to instruct a browser to make search queries on the target website, and record the timing. The purpose is, of course, to to find keywords for a user when the target website has a per-user search function. Results with words that are in the search index will often return with different timings than when the words are not indexed, depending on how the search result is constructed. This can be due to server-side processing, caching, database lookups done on the search results etc.

As a concrete example, if I search in GMail for a random string, that will typically return in about 0.3 seconds. If however I search for a string that is in my index, it will take significantly longer (0.6 seconds or more) due to GMail fetching the individual results server side and constructing the response.

Quite often, a search function on a website is non-mutating GET request, so it may not have CSRF protection.

Going back to the doctor website example, say that I can search my journal for medical history. Armed with the same dictionary as I used in the BREACH attack, I just construct a special website that asynchronously visits the below endpoints, and records the timing it takes for the page to load.

https://getmydiagnosis.foo/searchmedicalhistory?query=...

I no longer need to be in the middle to learn interesting data, I just have to trick the target into visiting my attack website, and record how long the “challenge” searches take compared to a known hit or miss. Often a fairly simple statistical model is needed to learn the search output, depending on how big the search space you are interested in is.

This attack can also be fairly advanced if done correctly, even constructing whole keywords from parts. Amir Herzberg and Nethanel Gelernter [1] successfully used this timing attack against GMail to figure out the name of the account holder, by a special divide and conquer search approach that is faster than just trying names in a dictionary one by one. Their paper offer many super cool techniques to make this kind of attack very practical.

I won’t spoil the paper for you but I just want to mention one technique that I believe is awesome: By short circuiting challenge search queries, you can often trick a search engine to perform some very time consuming work if the first search keyword is not found. That will aid your data gathering.

The concern with XS (Cross Search) is the same as for BREACH: Relatively few queries are needed to learn the presence of a single keyword from a dictionary (more advanced searches may require more queries and a better model).

Sensitive Data Everywhere!

There are many places on the Internet where the content being protected is from a small set of strings, and those places can sometimes be attacked using these techniques, with a relatively small set of queries.

Before writing this article I, by cheating a little bit, used the compression attack against Google Location History. It reflects query parameters in the payload and it does contain the countries/places you have visited, which lends itself nice to this kind of “dictionary” attack. Note that in practice this is difficult to do against Google Location History because the compressed payload is very noisy, so both myself and Google Security Team consider this attack against them to be more on the academic than practical side. If Location History was less noisy, the attack may have worked in practice.

Of course, I am fairly certain that the general class of attack can be successfully mounted against other targets. Consider for example:
  • Medical data requires a small dictionary of diseases.
  • Search history requires a small dictionary of sensitive keywords that are interesting to the attacker.
  • Communication/chat data requires a small dictionary of common first/last names to enumerate contact information.
  • Location history data requires a small dictionary of the place names in the world (countries, cities etc).
  • Financial data requires a small dictionary of, for example, names (money transfer recipients), company names (stock investments), numbers (credit card numbers, salary data) etc.
  • … and others. A particularly scary case is if the information you are after is a simple predicate, or a set of very small options.
If you can exploit search functionality, then that is typically a very viable approach as you don’t need to be in the middle of the TLS connection. If not, be the man in the middle and look for a compressed endpoint, with a normally small/clean output, where you can inject the challenge string you are looking for.

Protective Measures

Search fields can be enhanced with CSRF protection. There may be other places that are “search like” that will also leak timing data. It can be fun and terrifying to ask what other GET queries may leak significant timing data.

BREACH can be avoided by not compressing sensitive output. Here the best bang for the buck would be to disable compression on endpoints that reflect query parameters or (especially) have a small output size (because it’s typically less noisy and thus easier to compromise than the larger payloads).

Rate limiting can sometimes help, if the search space is large enough that a significant number of queries is required to exhaust the dictionary. Of course, even a strict rate limiting can not protect content where the set of possibilities is very small.

A noisy output can help against BREACH by obscurity, by design, or by accident. A very ugly workaround that may increase the cost of the attack in some cases could be to introduce a random byte string in the payload that has a random length. Invoking information theory the fact that the string is random makes it generally not compress, so by also making the “token” random length will result in the output getting a jittered length as well. This will often not work though, for two reasons. First of all, the compression algorithm may break this band-aid in various ways; window sizes/lookback and compression contexts may make your random string not affect the compression. Secondly, it may be possible to differentiate between a hit (that compress) and a miss anyway, by doing enough requests.

Conclusion

Hopefully this article will raise awareness of these side channel attacks and how they can be of particular concern to systems that are meant to protect a small set of keywords.

In general, a useful question to ask when designing secure systems is this: What is the most important data I am protecting, and how large is the domain?

Thanks to my friends Gunnar Kreitz, Nenad Stojanovski and Alex Rad for valued feedback on this post. Any mistakes are solely my own.

[1] http://dl.acm.org/citation.cfm?id=2813688

Tuesday, July 07, 2015

Let’s construct an elliptic curve: Introducing Crackpot2065

This article is meant to demystify some aspects of elliptic curve cryptography. The target audience is people who already have a basic understanding of applied cryptography but would like to close some gaps in knowledge when it comes to elliptic curves in general, and elliptic curve domain parameters in particular.

The first half of the article will lay the foundation on how ECC works, with examples from the “sage” mathematical software system. It will cover elliptic curves, curve equations, finite fields, addition/multiplication within the system, the Elliptic Curve Discrete Logarithm Problem (ECDLP), the group laws and the meaning of orders and subgroup orders. It will briefly mention some systems using the curves, such as ECDH and ECDSA, but the main focus is on the curves themselves and their properties.

The second half will focus on how to create a curve from scratch, suitable for cryptographic use. I will introduce a curve I call Crackpot2065 which is “safe” according to one criteria. I do not advise anyone to use the curve I’ve created for real purposes as there are many more well studied curves that have better security guarantees and implementations. I am just doing this for educational/expository reasons and that because I think it’s fun. With that said...

mad-hatter-2.jpg

Part 1: How Does Elliptic Curve Cryptography Work?


At a high level, Elliptic Curve Cryptography can be split in two broad areas. The first broad area concerns the mathematical “environment” in which we work, that is the elliptic curves themselves. The second broad area concerns the algorithms and systems using these structures to perform some interesting cryptographic operation, for example signing or key agreement. To namedrop some terms that you may have heard before: The first broad area is about structures such as the elliptic curve Curve25519 or NIST P-256. The second broad area is about algorithms such as ECDH and ECDSA.

Informally we can describe the “environment” as follows: ECC uses a mathematical structure called an elliptic curve over a finite field. An elliptic curve is a set of (x, y) points satisfying an equation that typically looks something like y^2 = x^3 + ax + b, where a and b are curve parameters that have constraints. The finite field is often the field of integers mod a prime number. That means that the set of points on the curve are also on integer coordinates. It is possible to define addition, and by extension multiplication, on these elliptic curve points. ECC works because if Alice has a secret integer s and a public key point s*P, then Eve cannot easily find s from the published point s*P. This is called the Elliptic Curve Discrete Logarithm Problem and it is believed that this is a very difficult problem to solve. The ECDLP problem form the basis of the security of the algorithms.

Let us understand the above paragraph by some examples. The examples below will use the computer algebra system Sage:

sage: ec = EllipticCurve(GF(2**255-19), [0,486662,0,1,0])
sage: ec
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
First of all we have (as seen above) created an elliptic curve over a finite field, called “ec”. The number 2**255-19 is a big prime number. The equation is an elliptic curve where the equation is given on a Montgomery form. The three equation forms that we will discuss in this article are:

The short Weierstrass form: y^2 = x^3 + ax + b, where 4a^3+27b^2 is nonzero in GF(p).
The Montgomery form By^2 = x^3 + Ax^2 + x, where B(A^2-4) is nonzero in GF(p).
The Edwards form x^2 + y^2 = 1 + dx^2y^2, where d(1-d) is nonzero in GF(p).

All of the above equations are elliptic curves. It is possible to convert a curve written on one form to the other. Normally in the cryptographic literature the most common way to express an elliptic curve is on the short Weierstrass form. Many modern curves are using the other forms for performance reasons.

sage: Point = ec([9, 14781619447589544791020593568409986887264606134616475288964881837755586237401])
sage: Point
(9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1)
Next we create a point on the curve on (x, y) coordinates. We have chosen a specific point with x coordinate 9. Using the (x, y)-coordinates directly in the obvious way are called “affine coordinates”. For performance reasons it is often desirable to use other coordinate systems instead. On the “projective coordinate system” the curve points are instead written as a 3-tuple (X : Y : Z) where x=X/Z and y=Y/Z which means that (x, y) = (x : y : 1). These are just two examples of coordinate systems that can be used when computing on elliptic curves.

sage: 80 * Point
(23817343013128792117854356851130396784845341481516229275406643496458380679609 : 35116296009168191515727253524688666433668212002350538291544025151813503173711 : 1)
sage: Point + Point
(14847277145635483483963372537557091634710985132825781088887140890597596352251 : 8914613091229147831277935472048643066880067899251840418855181793938505594211 : 1)

It is possible to do multiplication and addition on the points, as shown above, which will be discussed soon. What is not shown above is that elliptic curves often have a special point called the “point at infinity”. When dealing with curves on Montgomery or short Weierstrass form, the point at infinity exists. Edwards curves do not have a point at infinity.

What all curves have though, regardless of form, is a neutral element. Addition over the curve forms an abelian group. Consider the addition operation on the curve, then the laws for the abelian group hold (shamelessly copied from Wikipedia):

Closure: For all a, b in A, the result of the operation a • b is also in A.
Associativity: For all a, b and c in A, the equation (a • b) • c = a • (b • c) holds.
Identity element: There exists an element e in A, such that for all elements a in A, the equation e • a = a • e = a holds.
Inverse element: For each a in A, there exists an element b in A such that a • b = b • a = e, where e is the identity element.
Commutativity: For all a, b in A, a • b = b • a.

Lets have a look at this.

sage: ec(0) # The point at infinity is the neutral point for our curve
(0 : 1 : 0)
sage: Point + ec(0) == Point # Identity
True
sage: some_point = ec.lift_x(4)
sage: Point + some_point == some_point + Point # Commutativity
True
sage: -Point + Point # Additive inverse
(0 : 1 : 0)
sage: some_point_2 = ec.lift_x(1)
sage: Point + (some_point + some_point_2) == (Point + some_point) + some_point_2 # Associativity
True

Multiplication is defined as repeated addition. That is, 3*P = P+P+P. Multiplication can be implemented programmatically using repeated doubling and addition using an algorithm called double-and-add, or, more preferably, a similar approach called a Montgomery ladder that is similar but can be made to run in constant time instead, preventing timing attacks leaking information about the scalar (which is often the secret key).

sage: 3*Point == Point+Point+Point
True

As mentioned briefly above, the two primitive algorithms that must be implemented in an ECC system to get multiplication are double(P) and add(P, Q). The addition function often has the constraint that P != Q, which is why the specialization of addition, double(P), exists instead of just doing add(P, P) directly. If you go out of the way to try to derive an addition formula from the curve equation in short Weierstrass or Montgomery form, you will find that there can be a special “division by zero” step in the add(P, P) case. This is why most treaties on ECC always include algorithms for both add and double, to avoid making add(P, Q) riddled with special cases (the naive add(P, Q) for Short Weierstrass curves has many special cases as it is).

Exactly what is the meaning of addition on an elliptic curve, and how are the algorithms for add(P, Q) and double(P) implemented? Unlike pretty much all other ECC introduction articles on the Internet, I’m gonna leave this outside the scope of the document for the simple reason that I believe it will make the topic more confusing to understand. I can recommend Wikipedia for pointers and cool graphical illustrations. For the remainder of this article it’s enough to trust that addition follow the group laws above.

Elliptic curves on finite fields will by definition have a finite number of points. We call this the order of the curve. Counting the number of points on the curve can be done somewhat efficiently using somewhat complicated algorithms called Schoof’s algorithm or the more efficient improved algorithm Schoof-Elkies-Atkin, aka SEA.

sage: ec.order() # the number of valid points on the curve
57896044618658097711785492504343953926856930875039260848015607506283634007912

Consider an arbitrary point on the curve, for example the point “Point” in the sage example above. Repeated addition using this point forms a subgroup on it’s own: addition is cyclic in the this group which means that if you just add a point to itself (that is 0P, 1P, 2P, 3P…) you will eventually end up at the identity element 0P=0 where you started. We say that the point Point generates a cyclic subgroup using the point as the generator. This subgroup has an order on it’s own (the order in this case is the smallest n>0 such that nP=0):

sage: Point.order()
7237005577332262213973186563042994240857116359379907606001950938285454250989
sage: Point.order() * Point # order*P == 0*P
(0 : 1 : 0)

Due to Lagranges Theorem of group theory, the order of the subgroup will divide the order of the group.

sage: ec.order() / Point.order()
8

The above number is called the cofactor.
In Elliptic Curve Cryptography, the “domain parameters” of the curve include a base point which generates a subgroup of a large order. It is within this subgroup that we perform our curve operations with the assumption that the reversal of the public key s*P is a hard problem. The domain parameters must include a base point as it’s required to agree upon which subgroup to work in prior to perform cryptographic operations.

(Briefly) Introducing Curve25519 and ECDH


The elliptic curve given above, that is the equation y^2 = x^3 + 486662*x^2 + x over Finite Field GF(2**255-19) together with the base point (9, <large number>) gives the domain parameters for an elliptic curve called Curve25519, constructed by famous crypto guy Daniel J Bernstein. Curve25519 defines a public key as the x-coordinate of the point s*P where s is the secret key and P is the base point. The secret key is a random 255 bit number with the constraints that the number is a multiple of the cofactor (to prevent leaking a few bits of info during a certain class of attack called a small subgroup attack). The secret key is also constructed such that the highest bit is always set. This together with the Montgomery ladder ensure that no timing information will leak when using the secret key.

Curve25519 is not a general purpose curve in the sense that you can just take the curve and apply it to any algorithm. It is specifically constructed to be used with the Elliptic Curve Diffie Hellman algorithm. Some other curves (with “curve” here I mean the domain parameters including the base point, not just the equation) are more general purpose and can be used for other algorithms as well, such as ECDSA or others. You cannot take djb:s definition of Curve25519 as is and apply it to ECDSA because those algorithms require both (x, y) coordinate to work, and Curve25519 is only defined for the x-coordinate. y can be computed from x using the curve equation however this will result in two options due to the equations including a square root: either you will get the point A, or the points inverse -A. Curve25519 does not define which point to use in that situation. djb:s similar curve used for signing, Ed25519, does define which point to use in that case, and is as such more generic.

ECDH is the elliptic curve version of the Diffie Hellman key agreement. Alice and Bob would like to establish a shared secret. Alice has a secret key a and a public key A. Bob has a secret key b and a public key B. They both know each other public key. Alice computes aB and Bob computes bA. They use the x coordinate of the result as a shared secret. Because of the group laws, the result is the same (A is a*P and B is b*P so it follows that b*a*P = a*b*P).

sage: aliceSecretKey = 2**254 + 8 * randint(1, 2**251-1)
sage: A = aliceSecretKey * Point
sage: bobSecretKey = 2**254 + 8 * randint(1, 2**251-1)
sage: B = bobSecretKey * Point

sage: (aliceSecretKey * B).xy()[0]
16006640369170327653803989998811672408911551588929921312340351204923053532044
sage: (bobSecretKey * A).xy()[0]
16006640369170327653803989998811672408911551588929921312340351204923053532044

The observing attacker cannot recover the secret without solving the ECDLP, so ECDH is safe under the assumption that ECDLP is hard. ECDH is typically the least complicated Elliptic Curve Cryptography schema to understand. Other algorithms includes ECDSA which is a variant of DSA and it’s used for signing. Daniel J Bernstein has also created an algorithm called EdDSA, which is also an algorithm for cryptographic signatures with some other properties than ECDSA. It’s a neat algorithm where signatures are deterministic and they do not have the same catastrophic failure of ECDSA in case random numbers (ECDSA, as DSA, requires a random number “k” for signatures) are re-used by accident, which is what broke the Playstation protection a few years back.

This concludes our short overview of Elliptic Curve Cryptography fundamentals. The rest of this article will describe how to generate your own domain parameters, that is the prime for the finite field, the curve equation, and the base point.

Part 2: Let us create our own domain parameters!


For reasons that I have trouble to explain to my friends I got the strange idea to construct my own elliptic curve. That is I wanted to find a suitable prime for the finite field, a suitable equation and a suitable base point. Thankfully the SafeCurves project define a plethora of gotchas and requirements for a curve to be considered “safe”. I figured a good goal would be to create a curve that meets the SafeCurves requirements.

Step 1: Let’s choose a prime number


Because I have limited computational resources and limited patience, I quickly redefined my goal to find a curve that meets the requirements just enough. The smaller the numbers are, the faster I can find them with my 2009-era budget workstation. One of the main computational definitions of security in the SafeCurve criteria is that the work required to solve ECDLP (using Rho’s method) should be at least 2**100 operations. That means that the subgroup order O should be roughly 0.886*sqrt(O) > 2**100. Armed with this knowledge I set out to find good prime numbers around 2**200.

For performance reasons, most curves in practice have prime numbers that are very close to a power of 2. This means that the field operations, especially the modular step, can be implemented quickly using bit hacks. I enumerated all the prime numbers of the form 2**e-c where c is as small as possible and found some possibilities:

2**200 - 75
2**201 - 55
2**202 - 183
2**203 - 159
2**204 - 167
2**205 - 81
2**206 - 5
2**207 - 91
2**208 - 299
2**209 - 33

Using common reasoning I figured that the first few would be too small. So I settled for 2**206 - 5 just because the constant was the smallest which was aesthetically pleasing to me. It may be possible that the 204 or 203 one also meet the Rho requirement, but I made my choice.

It is highly desirable to pick prime numbers of the form p == 3 (mod 4) or p == 5 (mod 8) because in those cases it’s efficient to compute the square root in the finite field. This is beneficial for point compression: Given the point (x, y) you can typically “compress” that to just one of the numbers: the “receiver” can compute it on his side of the wire: for example given x you can compute y. Doing this requires the square root calculation.

The prime number I chose happens to be 3 (mod 4) which lends to quick square rooting.

Step 2: Let’s find a curve equation


Okay, now it gets a bit more complicated. What we want to do now is to, given the finite field we’ve chosen, find a curve equation that will given a base point in the curve generate a subgroup of very large order.

To make this easier, I decided to go with an Edwards curve. Edwards curves are parametrized on “d” only. By brute forcing all “d” I tried to find a curve that has a curve order that is a very large prime factor. That means I can later choose a base point that will (due to Lagranges theorem) generate a subgroup of the large prime factor order.

The pseudo code for sage would look something like this:

for all d = 2, 3, 4, …
   convert “d” to a curve on short weierstrass or montgomery form (so we can use the EllipticCurve constructor)
   find the order of the group using Schoof or SEA
   factor the number above
   pick a d such as the factors above contain one very large prime factor and some very small ones

The SafeCurves criteria additionally contains a requirement that the “twist” of the curve - which is to say another elliptic curve that is related to the one at hand - should have a large order as well. This is outside the scope of this article, but can be checked in a similar fashion. In fact, the SafeCurves criteria contain many other requirements that I’ve decided not to cover in this article at this point.

After around 8-12 hours on my slow computer I found the following:

d = 15688 gives
curve order = 2^2 * 25711008708143844408671393477455870117170824866529792321311457
twist order = 2^2 * 25711008708143844408671393477461333163539670934519578408332573

Alright! Those orders give a Rho cost of approximately 2**101.8 which is (slightly) greater than the required 2**100. The cofactor is a multiple of 4 which is another of the SafeCurves requirements, which is good for our purpose.

Step 3: Let’s find a base point


Given the curve x^2 + y^2 = 1 + 15688x^2y^2 over GF(2**206-5) we want to find a base point with the order given above, that is 25711008708143844408671393477455870117170824866529792321311457. Again remember that Lagranges theorem states that the order of the subgroup will be a divisor of the parent group order. So we:

let L = desired order 25711008708143844408671393477455870117170824866529792321311457
let Possibilities = {divisors of curve order}
for all y = 2, 3, 4, …
   find point P = (x, y) on the curve, P != neutral
   check that L*P = neutral and that a L is the smallest integer in Possibilities where L*P = neutral

Fortunately the search was pretty quick because the first y I tried, y=2, happened to be one that had the desired order.

That gives us the base point
(21562982200376473978929601187519256941293801462850163935410726, 2). Actually there is another choice: the inverse of this point. But we go for this one because it has the smallest x-coordinate of the two choices. A common convention is to define the “negative” point to be the one with the larger integer, similar to the convention with signed integers having the high bit set.

Step 4: Let’s sanity check against SafeCurves


The SafeCurves project actually contains a verification script that will try all the criterias and output the result. Lets try that on the new curve (before we do this we have to find a point generating the entire curve, similar to above, and also we have to supply lots of prime numbers so the SafeCurves program doesn’t have to do the factoring itself. I used msieve to compute the factorizations).

$ sage verify.sage data/curves/crackpot2065/
$ cat data/curves/crackpot2065/verify-safecurve
True

Of course, just because this curve meets the requirements doesn’t mean it’s safe: that requires that the implementation of the curve is actually safe too, and that it’s used sanely with the algorithm (ECDH, ECDSA, EdDSA etc.). And just because the curve is small doesn’t mean it’s fast either. In practice, if you want to use a “small” curve go with Curve25519 or Ed25519, depending on use case, or use something such as NaCL or libsodium.

Step 5: Now what?


The above description barely scratches the surface of finding good elliptic curve domain parameters. Even assuming the parameters are safe in a sense, there are still problems that need to be solved in order to use a curve in practice. One big issue would be to implement the curve in a safe and high performing way. Another big issue would be to use the curve in a correct way with the available algorithms. Is it tempting to look at the curves separate from the algorithms because that will give a warm fuzzy feeling for software engineers who like composability. However, there’s a danger in just taking a curve and “plugging it in” in any arbitrary algorithm. That’s a part that requires some knowing what you are doing.

With that said, in practice, it is often possible to compose a curve and an algorithm and end up at a “system” (i.e. a curve and an algorithm together in a specified way) that actually works. This is the case with some of the NIST families of curves and ECDSA. In other cases more info and care needs to be taken, such as with Curve25519, which is really the “system” of the curve defined in the Curve25519 paper, together with the ECDH algorithm.

Can my Crackpot2065 curve be used in practice? There are two sides to this. One the negative side, using this curve would require more work, such as defining the secret key space (which should probably be a multiple of 4 with a high bit set), and a good implementation, and some clear thought on how to use it with the algorithms without doing something moronic. On the positive side, if everyone used the same curves then an attacker with lots of resources (or at least the theoretical attacker) would be inclined to study or do pre-computations on those curves, which would be an argument for a more diverse set of domain parameters than are commonly used today.

As a fun thought experiment, a friend of mine mentioned a scenario where curve parameters can be generated so quickly that two parties can compute them together before commencing with the rest of the protocol in question. This is of course not very practical, but imagine a situation where generating domain parameters can be done very quickly, instead of requiring hours of computations.

Conclusion


My goal with this article was to demystify the elliptic curve domain parameters. By choosing how one might go about and pick those, I hope that this has cleared up at least some confusion on the topic. I have basically written the article I would have liked to read myself before I started this project. That would have saved me about of week of work.

If you are more interested in domain parameters, please check out the excellent SafeCurves project which includes lots of good information and references on parameter selection.

… Having said that, I may have lied a bit when I told you that my curve is “safe” according to the SafeCurves criteria. Because the verify.sage script has an input called “rigid”, which is up to the person running the verification script to decide. I decided to call Crackpot2065 “fully rigid”, according to the SafeCurves definition: “Fully rigid: The curve-generation process is completely explained.” This blog post is hopefully rigid enough. :-)

Have fun and don’t shoot yourself in the foot with your new crypto gun.

Obligatory caveat: The author of this article, Björn, is not a real cryptographer. There may be mistakes in this article. I apologize for any inconvenience caused by this. If you find a problem or have questions, just email me at be@bjrn.se.