Eventually, I expect a new generation of AEAD modes will be standardized that explicitly provide key-commitment.
Isn’t Ascon key committing? It’s the winner of NIST’s Lightweight Cryptography Standardization Process.
Seems like you might as well use that instead of chacha20 if you don’t have backwards compatibility concerns.
A system that decrypts the output of this exploit under key1 will see some plaintext, followed by some garbage, followed by 1 final block of garbage.
If the same system decrypts under key2, it will see some garbage, followed by some plaintext, followed by 1 final block of garbage.
Invisible Salamander is not completely invisible. The moderation use-case or maybe also the DLP use-case could detect that the plain text has high-entropy garbage and is likely to hide other data. For the DLP use-case, this wouldn’t be so different than having encrypted data with Key2 inside the file encrypted with Key1.
At the end of the day, the ciphertext that can decrypt to two different meaningful plaintexts has to store twice the entropy, either in the plaintext or in the key itself.
Correct, but meaningful effort must be expended to mitigate it, and even then it can’t be fully addressed: some will come through undetected. With committing AEAD however we know for a fact there’s no invisible salamander. It works every time, and we don’t even have to check.
Well, unless steganography is involved, and we need to check for hidden meanings in the plaintext itself (there is such a thing as hiding encrypted stuff in audio files or similar).
Okay, the exfiltration thing probably can’t be helped at this point (unless you just jail whistleblowers & journalists — wait…), but steganography doesn’t matter for moderation, so there’s still that.
I didn’t follow how the commitment prevents this. Couldn’t the exfiltrator just ignore the commitment part of the cyphertext and continue to use the alternate key?
<Long argument about why commitment would prevent the thing…>
Oops, you’re right, we can indeed ignore the commitment part for this one. I totally missed that the verification could be skipped, and the only guarantee for key commitment is that the message is the same for all parties that actually verifies the commitment.
Thinking through the operational security though is kind of difficult, so I wouldn’t bet my hat just yet.
Tbh I’m somewhat skeptical that this matters more than any steganography. In the example given, the leaked data could just be encrypted twice. The scanner would have to be able to recognize that the inner ciphertext is something bad. If it can recognize ciphertexts it can recognize garbage blocks.
I’m somewhat skeptical that this matters more than any steganography.
In regular steganography the hidden message is only revealed to someone who is aware of and looking for the message specifically.
In the invisible salamanders attack, it’s possible for an attacker to choose which message to show to the system at a particular time. The concern is not that the message is hidden, but that an attacker can choose which thing to show you. In the original paper, the hypothetical attack involved sending messages which harass the recipient but appear innocuous to moderators.
Ok but practically so what? In either case regular encryption with no salamander attack can prevent the moderator from reading the message, and steganography can make it harder to detect. In the harassment case the harassed receiver can forward the plaintext.
Yes this is an attack, but I can’t think of a practical system it subverts.
But if the harasser can control what they show to moderators, doesn’t it just devolve into “A said, B said” because they can just point to their innocuous message and say “I sent this, I dunno what they’re talking about”? If the moderator can’t read the message, they’re probably more inclined to believe the receiver’s report because there’s (effectively) no contradictory evidence, right?
The group chat case is a weird one to lump in here. I don’t need salamanders to get this, I can just send each participant a wholly different message. Even with key committment I can execute this “attack”.
Not in popular contemporary systems where a centralized service (that isn’t key-bearing) handles the fanout of a single message from a key-bearing client to all group participants.
There’s something I don’t understand about commitment. I’ve seen around the terms key commitment, and message commitment, and I never could get a straight answer as to whether they’re any different. This post seem to hint that they’re exactly the same, could someone confirm? If they’re not the same though, I came up with what one might consider somewhat key-committing, but not message-committing:
Encrypt the message with some random message key Km. (With a classic AEAD.)
Encrypt Km with a wrapping key Kw. (With a key committing AEAD.)
Send both ciphertexts.
As far as I can tell, the wrapping key Kw should be safe from any partitioning attack. No fancy password guessing or de-anonymisation there, since the ciphertext here is committing, and only one message key could possibly be extracted from it. The message key Km is not safe from a partition oracle, but we don’t care, since it was taken at random¹.
The message however could be decrypted under more than the one Km. If there are multiple wrapping keys, each could lead to a different Km, leading to different plaintexts… the invisible salamanders. But then I’d like to defend the idea that for some use cases, this is exactly what you want. For plausible deniability.
Not that you’d use actual salamanders to do that, it’s too easy for a forensic analyst to notice the suspiciously high-entropy garbage your plaintext file contains. Once the suspicion has been establish, they can just reach for the $5 wrench. Thus, the actual way to do it in my opinion is to hide stuff in the padding. Make it look like the message contains embarrassing porn, and hide the government secrets in the padding. Which is plausibly deniable, if the whole file format looks entirely random.
If we want this other kind of invisible payload in the file format, would we care about the invisible salamanders at all? I suspect not.
[1]: Using a partitioning attack on random keys wouldn’t work if there are 2^256 of them: sure we can make much fewer queries than 2^256, but we still need to craft a message for each key bucket, and doing that takes slightly worse than linear time in the number of keys in the bucket. Overall, this is no better than a brute force offline attack.
Isn’t Ascon key committing? It’s the winner of NIST’s Lightweight Cryptography Standardization Process. Seems like you might as well use that instead of chacha20 if you don’t have backwards compatibility concerns.
I feel this part is glossed over a lot:
Invisible Salamander is not completely invisible. The moderation use-case or maybe also the DLP use-case could detect that the plain text has high-entropy garbage and is likely to hide other data. For the DLP use-case, this wouldn’t be so different than having encrypted data with Key2 inside the file encrypted with Key1.
At the end of the day, the ciphertext that can decrypt to two different meaningful plaintexts has to store twice the entropy, either in the plaintext or in the key itself.
Correct, but meaningful effort must be expended to mitigate it, and even then it can’t be fully addressed: some will come through undetected. With committing AEAD however we know for a fact there’s no invisible salamander. It works every time, and we don’t even have to check.
Well, unless steganography is involved, and we need to check for hidden meanings in the plaintext itself (there is such a thing as hiding encrypted stuff in audio files or similar).
Okay, the exfiltration thing probably can’t be helped at this point (unless you just jail whistleblowers & journalists — wait…), but steganography doesn’t matter for moderation, so there’s still that.
I didn’t follow how the commitment prevents this. Couldn’t the exfiltrator just ignore the commitment part of the cyphertext and continue to use the alternate key?
<Long argument about why commitment would prevent the thing…>
Oops, you’re right, we can indeed ignore the commitment part for this one. I totally missed that the verification could be skipped, and the only guarantee for key commitment is that the message is the same for all parties that actually verifies the commitment.
Thinking through the operational security though is kind of difficult, so I wouldn’t bet my hat just yet.
Tbh I’m somewhat skeptical that this matters more than any steganography. In the example given, the leaked data could just be encrypted twice. The scanner would have to be able to recognize that the inner ciphertext is something bad. If it can recognize ciphertexts it can recognize garbage blocks.
In regular steganography the hidden message is only revealed to someone who is aware of and looking for the message specifically.
In the invisible salamanders attack, it’s possible for an attacker to choose which message to show to the system at a particular time. The concern is not that the message is hidden, but that an attacker can choose which thing to show you. In the original paper, the hypothetical attack involved sending messages which harass the recipient but appear innocuous to moderators.
Ok but practically so what? In either case regular encryption with no salamander attack can prevent the moderator from reading the message, and steganography can make it harder to detect. In the harassment case the harassed receiver can forward the plaintext.
Yes this is an attack, but I can’t think of a practical system it subverts.
This should convince you https://eprint.iacr.org/2020/1491
Probably this one as well, but I haven’t read it: https://eprint.iacr.org/2020/1456.pdf
But if the harasser can control what they show to moderators, doesn’t it just devolve into “A said, B said” because they can just point to their innocuous message and say “I sent this, I dunno what they’re talking about”? If the moderator can’t read the message, they’re probably more inclined to believe the receiver’s report because there’s (effectively) no contradictory evidence, right?
The group chat case is a weird one to lump in here. I don’t need salamanders to get this, I can just send each participant a wholly different message. Even with key committment I can execute this “attack”.
Not in popular contemporary systems where a centralized service (that isn’t key-bearing) handles the fanout of a single message from a key-bearing client to all group participants.
There’s something I don’t understand about commitment. I’ve seen around the terms key commitment, and message commitment, and I never could get a straight answer as to whether they’re any different. This post seem to hint that they’re exactly the same, could someone confirm? If they’re not the same though, I came up with what one might consider somewhat key-committing, but not message-committing:
As far as I can tell, the wrapping key Kw should be safe from any partitioning attack. No fancy password guessing or de-anonymisation there, since the ciphertext here is committing, and only one message key could possibly be extracted from it. The message key Km is not safe from a partition oracle, but we don’t care, since it was taken at random¹.
The message however could be decrypted under more than the one Km. If there are multiple wrapping keys, each could lead to a different Km, leading to different plaintexts… the invisible salamanders. But then I’d like to defend the idea that for some use cases, this is exactly what you want. For plausible deniability.
Not that you’d use actual salamanders to do that, it’s too easy for a forensic analyst to notice the suspiciously high-entropy garbage your plaintext file contains. Once the suspicion has been establish, they can just reach for the $5 wrench. Thus, the actual way to do it in my opinion is to hide stuff in the padding. Make it look like the message contains embarrassing porn, and hide the government secrets in the padding. Which is plausibly deniable, if the whole file format looks entirely random.
If we want this other kind of invisible payload in the file format, would we care about the invisible salamanders at all? I suspect not.
[1]: Using a partitioning attack on random keys wouldn’t work if there are 2^256 of them: sure we can make much fewer queries than 2^256, but we still need to craft a message for each key bucket, and doing that takes slightly worse than linear time in the number of keys in the bucket. Overall, this is no better than a brute force offline attack.