Why Digital Signature Algorithms- 20 min read - Text Only
Each day you visit a website, receive an email, a phone call, or even update an app on your phone—you benefit from an incredible technology: digital signatures. Ed25519 is one of several digital signature algorithms that make digital signatures possible. Before diving into how to apply Ed25519 from start to finish, I'd like to draw an analogy on how we use tools like it.
How integrity is managed in reality
First, let's consider an extreme example.
If you received a damaged package, you'd complain about it right? This product was not received in its original state, its integrity had been violated.
But what if you could not see inside? Or you're not necessarily supposed to see inside? Well we use sensors for that, sensors that are visible and auditable on the outside.
This is actually a great analogy, see computers aren't smart. Computers cannot look inside some packet of data and tell through human experience that a package has been delivered with integrity. But what we can do is provide something similar to these tilt sensors. We need a mechanical way for the recipient to accept or reject digital messages.
Integrity in computers: The Checksum
So how can a computer tell a message was damaged or altered? We use a checksum for that, a method that provides data integrity in regard to its data. A checksum takes some amount of variable input; it could be one word, it could be two gigabytes; and then produces a fixed output.
If any bit of the data checksum'd changed then one would expect the checksum to change too.
Checksums protect against accidental changes. When you said "Friday, the thirteenth", did you actually mean "Friday, the eleventh"?
What if the data were intentionally changed? Here's the weakness of non cryptographic checksums: it is relatively easy to produce data that has the same checksum.
# Create a file with some text
$ echo -n "Hello this is a test, I really like bbq chicken wings" > input.txt
# Create another which we will edit
echo -n "Hello this is a test, I really like *cough* teriyaki chicken wings" > input2.txt
# Now find out what the real CRC32 value is
$ crc32 input.txt
# Use a program to create a collision
$ forcecrc32 input2.txt 38 2c6b18bf
Original CRC-32: 7BB0E5AD
Computed and wrote patch
New CRC-32 successfully verified
# Preview the corrupted collision
$ cat input2.txt
Hello this is a test, I really like *c��* teriyaki chicken wings%
# Show that a collision has been made
$ crc32 input2.txt
In the above example, I use forcecrc32. If the modified file were presented as the original message, and I trusted that
2c6b18bf was the correct checksum, then I might assume the sender likes teriyaki chicken. Attacks here commonly manipulate data in unimportant places, the
*cough* for example might be ignored. By creating a second message with the same checksum value, I made a collision.
Checksums like CRC32 are not enough when intentional tampering is a possibility, collisions are easy to perform with CRCs and do permit naive acceptance of modified data.
To provide a higher assurance that a data is not altered in such a way that the checksum is still the same, cryptographic hash functions are used as they are by design not reversible. In fact, it has to be so computationally difficult that finding a single collision would take years of brute force effort. When a collision attack is found, the hash algorithm is considered broken.
Hash functions can be used in the place of non-cryptographic checksum functions when intentional tampering is a threat. Like CRC32, hash functions produce a fixed output. For example,
128 bits, while
Authentication in Reality
Consider: what if someone ripped off the tilt sensor to hide their changes and put on a new one, or even a fake one?
In reality one might look to see if a seal (which is hard to reproduce) is broken. There's a variety of technologies here too, ones that leave evidence if tampered, and technologies that inhibit tampering.
For example, on my personal MacBook there are tamper resistant screws, a specialist screw driver is necessary to open one of these devices. This gate keeps out inferior hands from changing anything inside.
Authentication in Computers
How will a computer know that a checksum is authentic, that it was calculated and left intact by the sender? The sender knows what checksum is when they send it and the sender expects the receiver to get the messaged data without any tampering, such that the receiver sees the same data and the same checksum. The problem then is how will the receiver know the checksum on the message is what the sender had intended?
This is where digital signature algorithms (DSA) provide a solution. Without inspecting the inside, anyone with public knowledge can verify the integrity of the message it is for. The verification capability is a mathematical operation. Exactly how verification works depends on the DSA.
For RSA, this depends on if it is RSA-PSS (see PKCS#1 v1.5), or RSS-OAEP (see PKCS#1 v2.2), or
*gasp* textbook RSA. While these RSA variants do use the same mathematical RSA operation as encryption, the parameters are different to the RSA operation. What is important here is the protocol built to meet security expectations on top of a deterministic algorithm. If you're interested in the differences between PSS and OEAP and what they do see this helpful answer.
For ECDSA and EdDSA, it is a yet again a mathematical operation that can be performed with the public key point, the signature, and the hash. EdDSA can operate faster and with less complexity, as the underlying curve (such as Curve25519 and Curve448) are designed to be safe against attacks which ECDSA curves (chosen by NIST) are vulnerable to.
The great thing about DSA verification is that anybody can do it. With the public knowledge, any receiver of a message can verify that it not only came from a known sender, but also discard the message if it is damaged or manipulated. Whether validation is performed or it is blindly forwarded along is another thing. Not all middle-men, boxes, processes, whatever you want to call them will inspect the contents of the message, know the sender and their public information, and perform verification. It is very important though that the intended recipient perform verification before acting upon a message.
Computer authentication meets reality
With computers being ubiquitous in our lives, DSAs are found in use nearly everywhere. Have you ever used contactless payments at the store or gas pump? EMV Chip Technology uses DSAs to securely pay whomever without sharing your card number.
DSA's are used for about anything and everything where identity matters. For example an inbound call from a loved one will be marked as verified with STIR / SHAKEN, where as robo-calls from Twilio may not.
DSAs can support something as important as verifying an operating system update.
Digital Signature Algorithms (DSAs) enable us to build technology that can confidently accept or reject messages that are received. Assuming private keys stay private and never are used by others, DSAs provide a reliable foundation for delivering and processing data where tampering can make or break real world expectations.