Why Digital Signature Algorithms

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
2c6b18bf

# 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
2c6b18bf

Cyclic Redundancy Checks (CRCs) are a common checksum tool. However because CRCs are reversible, it is not appropriate for use in digital signatures.

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.

Cryptographic Digests

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.

Debian Release files provide cryptographic checksums so that .deb files downloaded from a repository can be checked for integrity by the receiver of a .deb file.

Debian's method protects against mirrors (servers that have the same files available) from serving corrupted content to users. The file might not be fully copied over, or it could have crashed during a copy operation, or whatever.

For a while Debian used SHA1, and they still use MD5, which are both broken. I am still disappointed that they serve packages over plain insecure HTTP instead of HTTPS.

They at least use GPG to sign their release files (which have the signatures) so integrity and authenticity of downloaded content is maintained. Without a secure transport however, confidentiality is not provided.

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, md5 has 128 bits, while sha256 has 256 bits.

The amount of bits a hash outputs does not directly suggest one is stronger than the other across algorithms (md5, sha1, sha2, sha3, blake). See Key Length NIST Recommendations (2020)

Don't fall for numbers out right, like the game console race to 32-bit, 64 bit, and even 128 bits. When everyone was pushing for faster and faster processors, processor manufacturers hit a ceiling of about 4 Ghz. Next they built more and more cores and we have names like "Thread Ripper". Like anything out there, one metric cannot be evaluated alone.

The design of the algorithm and its defenses against known attacks is what matters. These days we have competitions held by NIST to select the best recommendation for security. Review the expert recommendations and do some research for what fits your use case best. And maybe don't roll your own cryptography, use libraries that do it all for you.

Don't use RSA 8192 bit just because you can. You can, don't get me wrong, it is technically possible. However, it is a sign you're not doing the right thing.

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.

So while you see warranty void if removed stickers (which is illegal); take note that preventing, recognizing, and deterring tampering is a hard problem. Thankfully in research into digital cryptology has advanced a lot in 50 years, the methods we employ now to detect tampering are reliable when done right. But education in how to use these tools effectively and correctly is sorely lacking in this field.

Sometimes places call their products "tamper proof", but like anything physical, it is only "resistant" to a determined adversary. In computers, technologies are "tamper proof" until broken. 🙂

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.

This section is highly technical, feel free to skip over

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 mathematical operations between RSA DSA, ECDSA, EdDSA, and post-quantum solutions cannot be compared or equated; like apples are to oranges they are both fruits but their flavors, biology, agricultural husbandry are different.

That said, do not mix encryption and signing just because RSA uses similar textbook techniques for signing as encryption. If you say this on stack overflow, you may get corrected. Take a moment to read RSA Signing is Not RSA Decryption.

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.

I've mentioned public knowledge above but what does that exactly mean? You may have heard of "public" and "private" keys and "public key cryptography". When public information is available, that means we're working with asymmetric cryptography. Public and private information is in use.

In asymmetric cryptography, it is safe to share and publish public information, public keys, that kind of thing. Sharing your public key and having it be re-shared does not reduce the security strength of your application. These algorithms are designed so that anyone can have public information and it operate safely and securely.

It is never safe to share private information. This is part of how people get scammed on crypto currency. They share their private key, intentionally in the moment, or inadvertently which allows the rest of the distributed system to accept the actions of someone else as the owner of a wallet.

By the way, if you're reading about cryptography and authenticity, you might stumble upon message authentication codes (MACs), these work for contexts with private knowledge, whereas DSAs involve public knowledge. This utilizes symmetric and asymmetric cryptography respectively.

If you hear about HMAC and how it has keys useful for signing things, it is not public key cryptography, the key is private. Do not share your HMAC keys. Using HMAC for authenticity is only useful when you hand out messages that eventually get returned and you are the verifier of your own messages.

An update from 2023

This advice still stands, but be careful about calling the output of HMAC 'a signature,' it is instead safer to call the output a 'tag.'

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.

Or as mundane as making sure a We're updating our privacy policy! email is authentic and not spoofed.

In 2009, I pulled a trick on my psychology professor by spoofing emails. He ran a simulation on Diffusion of Responsibility on the class. He asked that someone would remind him as an email before the next week's class about something. Having read ahead a few lessons, I recognized this problem and predicted its result. That no one would remind him, and he'd point this out to prove this psychological phenomenon.

I used a hand-me-down laptop with windows xp on a CF card (a poor man's SSD), and developed a PHP cron job that would randomly send an email with some randomly tweaked text to remind the professor. It ran on one of my servers at the time. Everyone but me was on the list of students, this was intentional. Then, every 15 minutes it would send an email reminding the professor about that thing. After 4 hours, he caught on something was really weird.

He said he was cool with it to me after, but not to do that again to any other teacher in the future. Not all teachers would accept something so crafty as a joke. Now however, email spoofing is pretty hard. We have digital signature algorithms in place to ensure content comes from who it says it is from.

DSAs do not stop emails from visually spoofing another's brand style or having similar names. This applies to reality too... My ISP frequently sends me cards in the mail which look like hand written holiday well-wishes. Turns out they just want me to buy a phone line.

Another ISP story. One called me up and I humored the sales person on the other side by listening. A mistake... I don't watch TV. So I said I don't have one.

As if grasping for the weakest straw ever, knowing I'm on a cell phone, the sales person said I could get a phone line so I could send and receive faxes.

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.

In the next article I will share step by step how Ed25519 can be used with OpenSSL in the command line. For those wanting to see all the obscure secrets read on!

This article is a happy accident. I was trying to introduce Ed25519 signatures, but I discovered that there is hardly enough content online to explain digital signature algorithms for those unfamiliar with cryptography. I previously wrote about QR Date, a trusted timestamp for real-time media, which uses Ed25519 signatures for its small size. Do check it out!

Hey, the next post A deep dive into Ed25519 Signatures is out! Make sure to at least skim it to see a real modern Digital Signature Algorithm in action!