Cryptography Tutorial

Cryptography is currently a very widespread requirement of multiple corporate organisation. It protects us with the confidentiality (or privacy) of data only & implementing it at the right layer will help to ensure we have the entire CIA triad met.

Before digging deep into the types of Cryptography, let’s understand cryptography in a basic way.

A proven method through which the data is securely exchanged between two parties using a key that is known to the sender & receiver alone (encrypted by the sender and decrypted by the receiver). This was further developed as days passed to increase the chances of someone cracking using a brute force attack. Now the most commonly used type of keys are Symmetric and asymmetric. 

Symmetric key encryption has a single key for both encryption and decryption of the data. This is faster however has a downside from a security standpoint as the Keys are to be kept secret during transmission to a receiver by some trusted modes or tools. It doesn’t rule off the chances of interception to decrypt the message. 

With all the above downside, asymmetric key encryption (also known as public-key algorithms) came into the picture and uses two keys (quoted as public & private key) for encryption and decryption. Here, the sender will encrypt the message with the public key and the receiver can use their private key to decrypt the same. If anyone is trying to intercept the data, the encrypted message will just see puzzled data. Here the burden of transmitting the key to the sender in a secure manner is reduced as the public key can be shared with anyone & private key is secured by the recipient

Cryptography implementation can be done at various layers and the deploying complexity varies accordingly.

• Full Disk Encryption (FDE)
• File Level Encryption
• Database Encryption
• Application Layer Encryption

Check out Great Learning Academy’s course on Cryptography course.

Full Disk Encryption (FDE)

You can mostly see this type of established on your laptop if you are using Windows 10. You would have wondered why a blue screen is asking for a password before you enter your company LAN credentials (AD Credential). 

This is nothing but Bit locker, an FDE capability provided by Microsoft bundled with OS. This ensures the entire disk is encrypted and in turn ensuring the data stored in your laptop hard drive are secure in worst cases such as laptop getting lost or theft. 

This is the simplest & cost-effective form to get your data encrypted but has its own share of cons associated with it. FDE doesn’t offer any options of enabling a granular level of encryption and is very dependent on the SED (Self Encrypting Drive) type of drives. 

File Level Encryption

As the name suggests, File Level Encryption is concentrating at a file-level and can go very granular to give the concerned individual to secure a single file in a more effective manner. 

A common example that you can relate is the Shared Drive or Share Folder in which you are saving your files in an office. While many think that the data saved by the individual can only be accessed by him/her, this is not the fact. Data can be read/copied by anyone who has access and sometimes the admins who have full access can even overwrite the data.

This particular issue can be overcome using file-level encryption which can help protect both structured and unstructured type of data by using certain agents that will be installed according to the OS that you are using. The downside of this type also arises from the same agents as they have restricted to a certain flavour of OS and not all custom OS that is deployed. 

Database Encryption

In my views, this is the most important type of encryption as this deals with DB that carries all your data. 

For your better imagination, please take your phone backup stored in some database which is secured using a different type of encryption mechanism that’s more suited for Database

A common one that is now widely recommended is TDE (Transparent Data Encryption) that offers encryption at the file level and meets various regulatory requirement such as PCI DSS

While there are a lot of positives of using this encryption type, this does have certain operational & technical limitation

Operational Constraint – Since Database downtime is highly impactful, DB admins ensure that they don’t want to have too many fancy things on the DB that can possibly impact the performance and crash the system. 

Technical Constraint – TDE doesn’t encrypt data in transit or use and encrypts columns or tables of a database, leaving configuration files, logs, etc. unencrypted. 

Application Layer Encryption

This is by far the strongest method of encryption & the most time consuming one to enable. Application-level encryption offers a high level of security with the encryption & decryption happening at the application layer which means that the data can be encrypted before transmitting or getting stored. 

While variants of application-layer encryption can reduce the impact on the Database, the downside to this type is more on the operational front as you need more dedicated development effort and resources to have the application level encryption enabled. 

Static vs ephemeral keys and crypto-period

With all processes and policies recommendation coming up, Cryptographic keys are static (designed for long term usage) or ephemeral (designed to be used only for a single session or transaction) depending on the requirement. The lifetime of static keys poses a possible threat and is always recommended to be rotated yearly as a best practice. In general, having a clear rotation standard of cryptography in your organisation will help you to meet most of the audit bodies that validate your standards. 

What is Key length and what is the type of algorithms?

In general, the longer a key is, the better security it provides (assuming it is truly random). The length of the key will be depending on the algorithm used by the system. 

In the case of symmetric key encryption, the key length will help you increase the security as it becomes more difficult for the attackers to do permutation & combination using various brute force attack tools. Asymmetric keys usually are longer and it is more uniform. There is a trend to have stronger asymmetric keys across many organisation. 

However, for any key (symmetric or asymmetric), its absolute strength also depends on the algorithm that the key is being used with – some algorithms are inherently stronger than others for any given key length.

Hence key length should be chosen based on a number of factors such as:

• The algorithm being used
• The strength of security required
• The amount of data being processed with the key
• The crypto-period of the key

However, there are cases that your standard has defined what needs to be done for each type of keys

What are the functions of cryptographic keys? 

Usage of cryptographic keys is now a regular BAU requirement as many regulatory bodies have started to enforce the standards to comply if they are dealing with any confidential or PII data. Some common functions are highlighted. The properties of the associated key (e.g. type, length, crypto-period) will depend on its intended function.

Data Encryption Key

As we read in the above sections, Data confidentiality can be protected using either a symmetric key or an asymmetric key. Symmetric algorithms such as 3DES (currently not recommended by many of the standards) and AES have key lengths varying between 128 and 256 bits, and a typical asymmetric algorithm is RSA with a key length between 1,024 (deprecated and not recommended now) and 4,096 bits. Symmetric encryption keys may be either ephemeral or static depending on the use case with a crypto-period commonly in the range of a day to a year, whereas asymmetric keys are usually having a great key length (at least more than 1 year). Destroying a key can be determined only if the data encrypted is no more required. If the same is required, then the keys need to be retained for the period until if the data can be destroyed and will not need decryption. 

Authentication Key

Without getting too much into the reason why this is existing, the basic terminology of authentication is used to provide assurance about the other important factor in the CIA triad which is the integrity of the associated data and is very often paired with symmetric encryption. This is done using the tested keyed-hash message authentication code (HMAC) mechanism, which works with a symmetric key. Using the SHA-2 algorithm, the typical key length can vary up to 512 bits and maybe ephemeral or static, but usually has a short lifetime. There are certain encryption algorithms that provide authentication without the need for a separate authentication key.

Digital Signature Key

As with authentication, digital signatures provide assurance about the integrity of its associated data. It does go one step further to include the concept of non-repudiation as well through validating the signature. This requires an asymmetric algorithm such as RSA (key length 4,096 bits is preferred nowadays) or ECDSA. The private key lifetime as we saw can be for a longer duration, but the corresponding public key has an indefinite lifetime, as it may be necessary to verify the signature at any arbitrary point in the future.

Key Encryption Key (aka Key Wrapping Key or Key Transport Key)

KEK is used for wrapping the secret key to ensure the key is secure during transporting using an authenticated encryption mechanism to ensure its CIA triad is met. Encryption key type varies from application to application type. The key used for this encryption is mostly static in turn the key life is also long-term (its purpose being to support frequent updates to the key that is being transported) and the length will directly depend on the algorithm being used.

Master Key  

A master key as the name says is the major key in the key hierarchy. It is a symmetric key that is used to encrypt multiple subordinate keys. Key length and the life cycle is usually the strongest used and is well protected either in a certified hardware security module (HSM).

Root Key

A root key is a topmost key in a Public Key Infrastructure (PKI) hierarchy, which is used to authenticate and sign digital certificates of an organisation. The key generation happens through a process called as Key Ceremony where the entire activity is witnessed by several individuals to ensure the key is protected from the time it is generated and is usually protected in HSM similar to Master Key. Most of the root keys are asymmetric key-pair with a length typically now at 4,096 bits depending on the digital signature algorithm used. Root key lifetime is longer and will be carrying the most governance policy surrounding it. 

Below are a few known algorithm used in the past & present.

Triple-DES Encryption

Triple DES is currently by far the oldest which came to existence to replace the Data Encryption Standard (DES) algorithm, which was defeated many times without big effort leading to data compromise. Until 2015, 3DES was widely recommended as the most trusted one along with the most widely used symmetric algorithm in the industry.

Triple DES uses three keys with 56 bits in key length each. The total key length adds up to 168 bits, but experts say that 112-bits in key strength is more like it.

Though it is not part of any encryption standards at PVT orgs or is being slowly being phased out, 3DES is still a decent enough hardware encryption solution for all the sectors that want to have this type of encryption. There are few HSM that still supports 3DES

RSA Encryption

RSA Rivest–Shamir–Adleman which is denoting the founders of the algorithm, is a public-key encryption algorithm and the standard for encrypting data sent over the internet. It also happens to be one of the methods used in Symantec PGP and other such programs used in Linux (GPG, GNUGPG, etc..)

Compared to 3DES, RSA is considered more secure as it an asymmetric encryption algorithm because it uses a pair of keys. The public key is used to encrypt a message and a private key to decrypt it. A normal individual will take quite a bit of time if he/she has the infra support to do a brute force attack to break this encryption code.

Advanced Encryption Standards (AES)

Currently, by far the most trusted standard by various government bodies is the Advanced Encryption Standard (AES).

Its size can be 256 bit for the strongest heavy-duty encryption and is considered to be very resistant to all type of attacks except the brute-forced attack where the system will do all possible combination to crack the cipher. 

While all said, AES is going to be the standard at least for the next few years across all corporate organisation and will be referred back to the standards. 

AES is considered resistant to all attacks, with the exception of brute-force attacks, which attempt to decipher messages using all possible combinations in the 128-, 192- or 256-bit cipher. Still, security experts believe that AES will eventually become the standard for encrypting data in the private sector.

Part 1

Cryptography is a complex subject, to say the least, and implementing real-world protocols and schemes is best left to highly trained mathematicians whose world revolves around esoteric subjects like Finite field algebra, Discrete logarithms and Lattice Structures. “NEVER DO YOUR OWN CRYPTO” is an often-repeated mantra and developers are encouraged to use well-known crypto libraries as well as stick to patterns that have been verified and endorsed by experts.

This is easier said than done and history is replete with examples where cryptographic primitives have been incorrectly implemented with disastrous consequences. I will illustrate this with a general class of attacks called the “Padding Oracle” attacks. But first some background….

You would probably know that there are two kinds of cryptographic algorithms used for encryption — Symmetric and Asymmetric Algorithms. Without going into too much theory and to keep the discussion focussed on the current topic, I will ask you to take a leap of faith and take my word that modern Symmetric key algorithms operate on ‘blocks of text’ of fixed length (Usually 128, 192 or 256 bits). This is known as a ‘Block Cipher’ and is formally defined as an encryption method that applies a deterministic algorithm along with a symmetric key to encrypt a block of text, rather than encrypting one bit at a time as in stream ciphers. The ’key’ for such ciphers would be equal to the block length (128, 192, 256 etc). Currently accepted NIST standards like AES (Advanced Encryption Standard), Triple DES (Data Encryption Standard) etc are all Block ciphers.

As a gross over-simplification, block ciphers operate as illustrated below (Pl note that Electronic Code Book is an insecure mode of operation and is not recommended to be used, however it does provide an intuitive feel as to what is happening under the hood and hence it’s usage here):

The plaintext is broken into fixed blocks (based on the actual encryption algorithm – for example 128 bits, for AES128) and the same fixed key is used with the plaintext block to arrive at the Ciphertext. At the receiving end, the process is reversed and as long as the encryption and decryption keys match, the original plaintext is retrieved. An obvious question is ‘what happens to the last block if the length of the plain text is not exactly a multiple of the block size?’. In such cases, the last block of the plain text is ‘padded’ using a pre-defined scheme to ensure that the block size matches. This is illustrated below for an assumed blocksize of 64 (pl note that this is only for illustration and a recommendation would be to use a block size of at least 128 bits):

The padding scheme illustrated above is called PKCS#5 and it works as follows:

If the block length is B then add N padding bytes of value N to make the input length up to the next exact multiple of B If the input length is already an exact multiple of B then add B bytes of value B In the table above, the plaint text ‘hello world!’ can be broken into two blocks of length 64 bits (8 bytes) each. As can be seen, the first block is complete, but since the text itself is 12 bytes long, there are four bytes that are to be padded in the second block. As per the PKCS#5 scheme described above, since there are four bytes to be padded, each of the four bytes is set to a value of 04.[By the way, the numbers in the Padded Plain Text column are the ASCII values of the letters above them – illustrated in the output below]

Similarly, the plain text ‘data protection’ is 15 bytes long – and therefore there is only one-byte padding that is required. Again, as per the scheme described above the value of the pad for this one byte is 01. The last plain text example ‘security’ is exactly 8 bytes (64 bits) long. As per the padding scheme, a new block is added to the plain text and since there are no actual plain text values here, all the 8 bytes are padded with a value of 08. Can you think of why this additional block needs to be introduced when we have the plain text which is an exact multiple of the block size? [Hint: Think what happens when the last byte of the actual plain text is 01.]

The CBC Mode of Operation:

I alluded to the fact that the Electronic Code Book mode of Block Ciphers is insecure. The main reason is that ECB encrypts identical plaintext blocks into identical ciphertext blocks, it does not hide data patterns well. In some sense, it doesn’t provide serious message confidentiality, and its use is not recommended in any real-world system.

This may also lead to a ‘Dictionary kind of an attack as the same plain text maps to the same cipher text as long as the key is not changed. In Crypto speak ECB lacks diffusion ie ‘if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one-half of the plaintext bits should change’

The CBC (Cipher Block Chaining) mode introduces diffusion by XORing (Exclusive ORing) each block of plaintext with the previous ciphertext before being encrypted. This way, each ciphertext block depends on all plaintext blocks processed up to that point. To make each message unique, an initialization vector must be used in the first block. (The IV is a common construct in Cryptography – it is unique to each message but unlike a key, it is not a secret and for all practical purposes, is considered known to the attacker).

The CBC mode of encryption and decryption is shown below:

Finally, the ‘Padding Oracle’!

The setup for the padding Oracle is as follows:

The attacker has access to the encrypted ciphertext and the IV for a block cipher encrypted using the CBC mode The attacker can submit this cipher text or the cipher text modified as per the attackers wishes to an Oracle(think a web application)

The attacker with just this information should be able to figure out the decrypted value of a block of cipher text or even the entire cipher text. It so happens, it is indeed possible to do so! The Oracle sends back a response to the attacker indicating whether the decrypted plaintext is correctly padded or incorrectly padded (for example a webserver sending a 200 ok response for a correctly padded value and a 400 Bad requesterror for an incorrect pad) [Example of an incorrect pad would be a 04 in the last byte of the decrypted plain text, but some other values in the three bytes preceding that]:

Part 2

In Part- I of this series, I have set the stage for illustrating how the ‘Padding Oracle’ attack is actually carried out. Just as a recap, this involves the use of a block cipher and the CBC mode of encryption. The attacker has access to the cipher text and the initialization vector (IV). He/she has the ability to modify the cipher text one bit at a time and submit this modified ciphertext to an application which sends a response back to the attacker indicating whether the padding for a particular block is correct or incorrect.

Say the encryption algorithm used is AES128 and the attacker has access to just two blocks of the ciphertext.

Attacker has ciphertext c = (c[0], c[1],) and wants m[1] which is the original plaintext corresponding to the c[1] block

Remember that in CBC mode m[1] is obtained (decrypted) as follows:

Block c[1] which is 128 bits long is decrypted independently using the same key used during encryption This decrypted value is Xor’d (exclusive ored) with the previous cipher text to produce m[1] which is the plaintext.

We also know, if m[1] were to be the last block, the last few bytes would need to follow an agreed-upon padding scheme (refer part – I for a detailed explanation). Valid padding schemes would be:

*All numbers are in hexadecimal: ‘01’ would convert to 00000000 00000001 and ‘15’ would convert to ‘00000000 00001111 – typically written as 0X01 and 0X15 to indicate that we are dealing with hexadecimal numbers

The key Idea for the Padding Oracle attack is this — we change one byte of the cipher text block c[0] so that the value of the corresponding byte in the plaintext, m[1] changes. If the final value results in a valid pad, we would be able to guess the actual plaintext corresponding to that particular byte and if it does not, we keep trying repeatedly with another value till a valid pad result. What makes this so elegant is that there is only a maximum of 256 guesses for us to unveil the actual plaintext byte! This would be perhaps best be explained with an illustration.

Suppose ‘g’ is our guess for the last byte of m[1]. We replace the 16th (last) byte c16[0] of c[0] with c16[0] ⨁g ⨁0x01 [⨁ is xor] . This would effectively mean that the original last byte of m[1] would be xor’d with g ⨁0x01. One key thing to remember about xor is that ‘ X ⨁ X = 0 ’ ie. Anything xor’d with itself cancels out. So the value of c16[0] cancels itself above and if our guess ‘g’ were equal to the last-byte, then that would result in cancelling out the ‘ last byte ’ making the last byte as 0x01 – a valid pad and the Oracle with responding to with a ‘True’ value !. In effect, we have the value of the last byte of m[1] in plaintext. If the guess were not valid, it would result in some other value at m16[1] and as per our setup, the Oracle with respond with a ‘False’ value. So what do we do, in this (False) state?. Simple – change the guess ‘g’ to another value and repeat the test. Since ‘g’ is a byte long (8 bits), the maximum number of values that it can assume is 2^8 which is 256. So in a worst-case scenario, we would need to make 256 guesses before we uncover the actual last-byte of m[1] and in the average case, it would just be 128 guesses. The small code snippet below illustrates this point when we assume that m16[1] = ‘e’ and c16[0] = ‘t’

So what do we do once we get the last byte?. It is now pretty easy to guess, isn’t it?: what is the next valid pad?. The last two bytes of m[1] should obviously be:

02 02 We now actually know what the last-byte of m[1] is and therefore we know what value must be in the last byte of c[16] to make this value 02. So we fix the last-byte of c0 to this value and now we are just left with solving for the second last byte of m[1] which exactly maps to the process described above. Rinse, repeat and we now get the second last byte of m[1]. This essentially is repeated for every byte of m[1] to obtain the entire block of plain text.

A visualization of this entire process is available online here. Have also created a toy program that essentially solves the Padding Oracle problem for two bytes. Use one of the online python IDE’s to play around with this. Paste the python code attached to this post into the IDE here to get a sense of how this works.

Real world ‘Padding Oracle’ Attacks

In the real world, there have been many attacks that exploited this technique successfully with extremely serious implications. Some examples (all examples listed below have subsequently been patched):

SSL/TLS padding oracle by exploiting timing information that is available upon submission of correctly and incorrectly padded ciphertexts. (fixed in OpenSSL 0.9.7a) Hundreds of thousands of ASP.NET applications were affected by incorrect AES implementation in the framework [this is dated and modern versions of this framework are not affected] The Lucky thirteen attack on TLS protocol Several web frameworks like Ruby on Rails, Java Server Faces were affected by this class of attacks Attacks on IPSec protocols POODLE attacks on SSL 3.0 use a combination of a downgrade attack along with a Padding Oracle attack IMAP over a TLS was subject to a variation of this attack which allowed recovery of the IMAP password

Despite this attack vector being first documented in the year 2002, it remains relevant even today. For instance, researchers at the Ruhr-University Bochum reported they found nearly 100 variations of padding oracle attacks in the wild in 2019 including in well know products like Citrix and SonicWall.

Recommendations:

While CBC by itself does not have inherent vulnerabilities, it has been proven to be an extremely difficult block cipher mode to correctly implement in real-world protocols. So, it is best to avoid this altogether. Instead, it is recommended to use better alternatives like AES-GCM which is a specific implementation of AEAD – Authenticated Encryption with Associated Data. Specifically, AEAD is a special combination of a cipher and a MAC (Message Authentication Code) algorithm into a single robust algorithm, using a single key. There are several secure AEAD schemes that are provably secure (For example GCM, OCB, EAX, CCM etc) and the exact choice would depend on many factors like speed, parallelizability etc

PKI Part 1

In an Oscar-winning performance in the 1997 movie ‘As Good as it Gets’ Jack Nicholson while professing love to Helen Hunt mouths this classic line towards the end of the film – ‘And the fact that I get it makes me feel good, about me’. If you have been in the security business for some length of time, you would have come across bugs/vulnerabilities that are so elegant, so simple and so downright stupid that the mere fact that you ‘get it’ brings about a warm fuzzy feeling and you cannot get yourself to wipe the grin off your face, at least for a couple of days.

Despite the usual staid language of vulnerability announcements, there was something unusual about CVE-2020-0601 – apparently, NSA had tipped Microsoft on this one. This is unheard of and intriguing and I decided to investigate.

*This vulnerability has its own special name now: Chain of Fools or CurveBall

The official announcement quickly establishes that the vulnerability (a) is related to Elliptic Curve Cryptography (ECC) (b) is something to do with certificate Spoofing and (c) the vulnerability itself is in Crypt32.dll library and the way it handles certificates. A quick check on my go-to security news sites and mailing lists gave me additional insights into what was exactly going on – apparently, the library was not checking that the ‘Generator’ of the Elliptic Curve used for verifying digital signatures was matching with what is specified in the standard. If this is sounding a little outlandish at this moment, please be patient – I will try my best to explain this in subsequent paragraphs.

First a little bit of a background on Public Key Cryptography and Elliptic Curve Cryptography

You would be aware that modern-day trust and by extension, almost everything that we do digitally is built on Public Key Cryptography – the form of cryptography that uses two keys, one private and the other public. The private key is well – ‘private’ and the public key can be shared with anyone who cares and while it can be used for encryption, public-key cryptography is almost exclusively used for (a) Exchanging Symmetric Keys and (b) Digital Signatures. There is one other complication – How do we make sure that I do not raise my hand and claim that your public key belongs to me? That is where the concept of Certification Authorities (CA) comes into play. The CA signs your public key and every one that trusts the CA can now trust you because the CA is considered totally trustworthy and unbreakable.

Public Key Cryptography behind the scenes is just Math (what in life is not?) and depends heavily on the concept of ‘Trapdoors’ which are mathematical functions that make it easy to move from point ’‘A’ to point ‘B’ but make getting back from ‘B’ to ‘A’ almost impossible without the special knowledge of something (private key). The most commonly cited real-life example is mixing of paint – given two colours it is easy to mix them and get a third colour. However, just by looking at the mixed colour, it is extremely difficult to get the exact shade of the two original colours back. Public Key Cryptography has been around since the mid-seventies and the algorithm that is almost the de-facto standard is the RSA. The trapdoor function for this algorithm is based on ‘factorization of large numbers’: Given two large prime numbers, we can quickly multiply them and get the third number, but just with this third number, we cannot factor out the two numbers efficiently to get back the original primes. However, if we were to have one of the original numbers, we can quickly calculate the second number from the third. This is a classic Trapdoor – easy in one direction but difficult in the other.

RSA, works well, but it has a fundamental problem – it is slow and resource-intensive. ECC which was publicly announced in 1985 offers an alternative to RSA in the public key domain. The main advantage of ECC is that it uses smaller key sizes for the same or better levels of security as the RSA. This translates into a direct benefit in terms of computing resources. ECC is most popular in resource-constrained devices (Embedded/IOT devices) and is the algorithm of choice in Bitcoin and other blockchain related protocols.

Comparable Key Sizes; Source: RFC 4492

Fundamentals of Elliptic Curve Cryptography

Elliptic Curves are essentially equations of the form y2 = x3 + ax + b which when plotted look as below:

Notice, that the curve is symmetric about the ‘X’ axis. Intuitively the left-hand side of the equation has a square term (y2) so, for each value of x, there are two terms one positive and one negative for y. What makes this equation interesting from a cryptographic perspective is that we can define mathematical operations on this curve. Remember, the whole exercise is to discover a ‘Trapdoor’ function that will form the basis of the ECC Public Key system.

Addition on the curve is best understood graphically:

*Generated from software under MIT license (https://andrea.corbellini.name/ecc/interactive/reals-add.html)

To add two points, P & Q we draw a line from P to Q. This line intersects the curve at a third point. Reflecting this point about the ‘X’ axis (x co-ordinate remains as is and y becomes -y) we arrive at a point R which is equal to P + Q. The important thing to note here is that this is computationally a ‘light’ operation with standard formulae for calculating the (x,y) coordinates of R [akin to the determinant of a quadratic equation]. An interesting thought experiment to carry out would be to imagine what it means when the point Q comes closer and closer to P and eventually coincides with P. The astute would have realised, that the line joining P & Q would become a ‘tangent’ to the curve and this line intersects the curve at only two points.

Mathematically here P = Q and therefore R = P + P = 2P. Effectively, this means that we have doubled the original point P. This becomes a very important property as we can extend this logic by adding the point 2P to itself to arrive at 4P and 4P to 4P to arrive at 8P and so on. Hope you get the drift. Why this becomes important is that it helps us arrive at the promised land – the Trapdoor function for elliptic curves which is scalar multiplication or nP = P + P + P + …. +P (n times)

Using a binary representation of n we can arrive at an algorithm to compute nP in polynomial time (computer speak for reasonably efficient). For example, if n = 25(11001 in binary) and we wanted to compute 25P, we would compute (16P+8P+P) as we have an efficient method of doing so. This scales very well and even when n is in the range of 2384 (around 115-digit base 10 number) which is approximately the size of n in the real world. Exactly how fast – about 9ms on my six-year-old laptop (Pentium i5 with 6GB RAM using Ubuntu 18.04 LTS) which is reasonable by any standard.

In reality n the scalar multiplication factor is the Private Key in ECC. The question that remains to be answered is “Why is scalar multiplication on an elliptic curve a Trapdoor function”. If we try and visualize what happens when n is a large number (order of 100+ digits) we can almost see the point P bouncing around the curve as we go through the process of doubling and adding that we had outlined above.

So, if we start with a point P on the given elliptic curve and multiply this with a large n, we eventually arrive at point Q and this as we saw above was an inexpensive operation. However, it transpires that given just the final point Q and the starting point P, there is no efficient way to derive or calculate n. This is a logarithmic problem. In fact, the only way possible seems to be to try out all possible values for n and see, if we can reach Q. It is estimated that the time taken to brute force ECC, even with the best-known method today, with a key size of about 280 bits using the entire computing power existing in the world today, would theoretically take more time than the entire life of the Universe so far!

So now we have our Trapdoor function – easy in one direction and hard in the other. We can consider the final point Q as the public key and share it with the world as long we keep n, the scalar multiplication factor to ourselves. Therefore, n is our Private Key. The starting point P is called the Generator and from the point of the specific vulnerability under discussion, it becomes crucial to understand that it is hard to reach the final point Q from P without the knowledge of n. However, if we remove the restriction that we have to start from P and pick another point Pnew, it transpires that we can calculate new which when multiplied by Pnew reaches the original final point Q trivially. I will summarize the discussion on Elliptic curves as follows:

Addition over Elliptic curves is easy (P + Q) Doubling is actually addition, where Q = P and is also easy We can use the Doubling trick to quickly calculate 2P, 4P, 8P……. 2nP. Step 3 helps us with an efficient algorithm for scalar multiplication of P (nP) to arrive at the final point Q. Q can be considered the public key Calculating n from Q and P is infeasible. P is called the Generator However, if we are given the flexibility of choosing another Generator, we can calculate new so that we can arrive at the same Q easily I will close the discussion on elliptic curves by making two points:

The Generators used in ECC in the real world are fixed and standardized as are the equation of curves. We cannot arbitrarily use a random Generator, even if it is a valid point on the curve. This is a key point. I have grossly simplified the discussion on Elliptic curves by considering curves only in the Real domain. In the actual world, Elliptic curves are taken over Finite Fields which is are sets with only a finite number of elements (unlike the real domain which extends on both sides forever). An example of a finite field is the set of integers modulo p, where p is a prime number. It is generally denoted as GF(p). I have also taken extreme liberties with what the actual Public and Private Keys are, choosing simplicity over pedagogic rigour – I will do a post on this if there is appetite but a warning, sleeping on a bed of nails might be easier than Finite Fields! However, the basic operations (addition, multiplication etc) are similar in respect of Elliptic curves in Finite Fields and the logarithmic trapdoor becomes the Discrete Log problem which is considered to be a hard problem and hence still considered suitable for a trapdoor function. If at all, Finite fields make the problem harder due to non-linearities intrinsic to such fields.

Back to the Original Problem

You might have guessed what this vulnerability is all about by now. Apparently, Windows CryptoAPI Crypt32.dll does not verify whether the Public key of the CA (embedded within an X509 certificate) has been arrived at from a pre-defined and authorized Generator point on the standard public curve if the certificate already exists in the cache (ie, if any certificate signed by the particular CA has been used before). It is, therefore, possible, to generate an arbitrary certificate, spoof the public key of the CA embedded in the certificate with a value corresponding to the original public key but generated using an arbitrary Generator point – I had pointed out that this was easy and will demonstrate it with actual code in Part II of this post. To give a crude analogy, imagine that there is a highly secured vault to which access is granted only to Joe Smith. The first time he comes to the vault, he is strip-searched, fingerprinted and subject to TSA level scrutiny before he is allowed entry. However, next time onwards, any person showing up at the entrance and announcing himself to be Joe Smith is let in without any validation. This is how silly this vulnerability is! It is to be noted that this is not a problem with the ECC, Crypto or with the underlying Math. It is simply that the implementation of the library is flawed.

Conclusion – Part 1

CVE-2020-0601, dubbed ‘Chain of Fools’ is a very interesting vulnerability, potentially with wide-reaching ramifications. As with most attacks on Cryptography, this is due to faulty implementation rather than any flaw in the underlying algorithms. I will build on this in Part II of this series where I demonstrate how easy it is to derive private keys from valid public keys if the Generator is not validated. I will also explore attack vectors and possible defences.

PKI Part 2

In Part-I of the post, I had discussed in some detail, CVE-2020-0601 and established that the problem is related to the manner in which the MS CryptoAPI (Crypt32.dll) on several Windows versions handles the verification of the Elliptic Curve Cryptography (ECC) signatures. I had also talked about Public Key Cryptography in general and the requirement of ‘Trapdoor’ functions. Having done that, I had tried to explain the fundamentals of Elliptic Curve Cryptography and in particular, establish that scalar multiplication nP is a Trapdoor on Elliptic Curves in that it is easy to compute, but given the result of this multiplication, it is practically impossible to calculate/guess n. The number n is the Private Key and the result of nP which is Q is the Public Key.

I had also introduced the concept of the Generator and alluded to the fact that if this Generator is not validated during the verification of the ECC signature, it is trivial to calculate a totally different Private Key nnew which can be made to map to the original public key Q. I will expand on this theme and try and generate multiple Private Keys which generate the same Public Key. To see why this is so, let us look at how the original Public Key was generated:

1. We chose an originating point P on an Elliptic Curve and randomly a large n.
2. We chose a standard elliptic curve and, on this curve, carried out a scalar multiplication of n and P and to arrive at point Q which is the Public Key

Mathematically nP = Q. The aim is to now generate a rogue private key nnew which maps to the same Q. Obviously P which is the generator would also need to be changed to Pnew so that we arrive at the same Q. ie nnew .Pnew = Q. The same equation can be written as Pnew = (nnew)-1. Q [We have multiplied both sides with (nnew)-1]. So, we now have a methodology for generating a rogue Generator and a Private key that map to the original Public Key. Steps to do so would be on these lines:

Choose an arbitrary number and set this to (nnew)-1, For example, let (nnew)-1 = 3 Multiply this value with Q to obtain new Generator point Pnew. In this case Pnew = 3P and we already know that this is easy to compute Finally, find the inverse of (nnew)-1 which is [(( nnew)-1)-1)to arrive at n( Double inverse is n itself) which is the Private Key. The inverse is an easy problem on Elliptic Curves (ie there are standard algorithms available to do this in polynomial time) So what has just happened? We have managed to generate a value that is the same as the original Public Key using an arbitrary Generator. In the bargain, we have also been able to calculate a totally new Private Key unrelated to the actual Private Key. We can use this new Private key to create a Digital Signature that seems valid (It actually is not, since the Generator we have used is arbitrary and does not map to the standard associated with the specified elliptic curve). If the software verifying the Signature, does not notice that the Generator is not valid, we have fooled the system into accepting our fake Public key as valid. Bingo!. This is the crux of CVE-2020-060.

Let’s try and put this into practice..

We begin by generating an ECC public/Private key pair over the curve P-384 (the NIST defined standard curve) and save the content into a file called ecc-private.pem. We verify the content of the generated file and notice the private key, as well as the public key, are stored in the file.

Next, we extract the public key from this file and save it in ecc-public.pem.

Now that we have the public key in a separate file, we programmatically, extract the point on the ECC curve corresponding to the public key. Then using the technique explained in the paragraphs above, we choose an arbitrary point on the curve and invert it using a Python library (gmpy2) to obtain the new private key (nnew). This inverse multiplied by the original Public key (Q) will provide a new Generator which is also a valid point on the curve. Just to make sure that this works, we multiply this generator with the private key to see whether we indeed obtain the original public key value

The output of this program is as below

Public Key-Value Remains the same, for different Private Keys

As can be seen, we have generated the same public key using three different private keys. Even at the risk of repetition, this is possible because we have chosen a new Generator each time and made sure that this Generator when multiplied by the current private key produces the same output.

What can an attacker do, with this knowledge? A typical attack vector would be as follows:

The attacker downloads a valid certificate signed by a well-known public Certification Authority (Digicert, Globalsign, Microsoft etc) He extracts the public key from the certificate and using the technique outlined above, manipulates the Generator and derives a Private Key that corresponds to the same public key He now generates an arbitrary public/private key corresponding to the certificate he wants to spoof. Using this public key, he generates a CSR (Certificate Signing Request) with fields exactly matching the downloaded certificate (excepting, of course, the spoofed signatures) He signs the CSR impersonating the actual CA with the Private Key he generates at step 2. He includes the rogue Generator from which he is obtaining the private key explicitly in the CSR so that the default one is not used He ensures that the CA certificate is in the cache of the computer he wants to attack (For example, he could send across a genuine link to a site signed by the CA he is spoofing and wait for the user to click – in all probability, if he were spoofing a popular CA, the certificate would already be in the cache)

Once this is done, he has three ways of carrying out the attack:

He can carry out a Man-in-the-middle attack to intercept traffic between the user and the server He can induce the user to install software appearing to be from Microsoft signed using the malicious certificate. He can set up a rogue server with a certificate appearing to be signed by a legitimate CA and essentially view all traffic directed to that server. There are a large number of other nasty things that can be done using this vector(Drive-by download, serving up malicious software – really only limited by his imagination)

Possible Defences and Mitigating Circumstances

The obvious defence is to Patch swiftly. Other than this, good change management practices around software installation, and Defence-in-depth mechanisms at the network level, good monitoring and incident response practices would help in minimizing the impact. Also, for carrying out a MITM attack (unless he is a state actor), the attacker would need, in all probability, to be on the local network either on the client or the server which is quite a big assumption.

Conclusion

CVE-2020-0601 is a classic example, of developers overlooking something which should have been obvious, either because of a lack of understanding of the underlying algorithm that they are implementing or simply through sheer oversight. As is often the case with Crypto, the issue is with the implementation and not with the underlying math. Typically, It is drilled into developers that they should not implement their own crypto but should use something that is accepted as a standard that has withstood the test of time. What if the reference implementation is itself flawed as seems to be the case on this occasion? This is when often used terms like Defence in Depth and Zero Trust cease to be platitudes and actually might start to mean something!