I’m downvoting this comment because it’s misleading.
First of all, no one has ever found an SHA-2 hash collision yet. Second of all, the chances of two SHA-2 hashes colliding is about 1 in 1 quattuorvigintillion. It’s so big I had to look up what the number name was. It’s 1 with 77 zeroes after it. We’re talking universe-goes-into-heat-death-before-it-happens type odds. Only under the most absurd definition of “quite often” could anyone ever reasonably claim that a cryptographic hash function like SHA-2 “quite often” has collisions.
Ahhhh. I misread the output on Wolfram Alpha. You’re right. I’ll leave it in the original post for posterity, but also for the record, it’s actually 1 in 100 quattuorvigintillion
Second of all, the chances of two SHA-2 hashes colliding is about 1 in 1 quattuorvigintillion.
That numbers is irrelevant because it’s for randomly chosen hashs.
The main point here is that I don’t know that there a guarantee that there exactly one signature that successfully signs a message for a single private key. Likely there are multiple.
PGP then creates a session key, which is a one-time-only secret key. This key is a random number generated from the random movements of your mouse and the keystrokes you type. This session key works with a very secure, fast conventional encryption algorithm to encrypt the plaintext; the result is ciphertext. Once the data is encrypted, the session key is then encrypted to the recipient’s public key. This public key-encrypted session key is transmitted along with the ciphertext to the recipient.
A session key that’s coming from a random number generator is an easy way to add specific entropy into the system. Is the session key really nonwhere to be found in the signature? Even if it is, the math behind public-private key crypto is complicated.
PGP advertises that if you know the signature you can be certain that the text isn’t altered. I haven’t found a promise that the signature is deterministic and that it’s impossible to add information to it.
By running your the crypto code through an obfuscator you haven’t made your code easy to read but if you actually try to read your code you find it calls things like “PublicKeyEncryptedSessionKey:a(”./public_key_encrypted_session_key.js”)”.
Sorry Christian but I am going to stop replying after this one. I’m not trying to be a dick, it’s just that at this point I think continuing our conversation is going to confuse readers more than it will help them. The concepts you are referring to and sources you are citing are only tangentially applicable to the conversation at hand.
The fact that it is possible to collide hashes, signatures, etc. is well known and obvious. The reason it is not a concern is the extreme difficulty in producing a collision. As indicated above, you would have to brute force your way through 10^77 different combinations to guarantee a successful collision.
The section you cited describes PGP encryption, not signatures. They are two entirely different things. PGP signatures do not involve session keys.
You can manipulate the output of (or “add specific entropy to”) any hash function. It is, however, absurdly difficult to convey meaningful information in the output of a hash function. See above regarding the amount of work required. Furthermore, because a private key is longer than a PGP signature, it is literally impossible to encode the key in the signature.
The code uses a library, which means it supports multiple functions. The vast majority of which are not used by the script.
You are referring to several traits which are common to almost all cryptographic systems, yet you are implying these are traits unique to PGP. Furthermore, you are describing these traits with loaded language that paints them as weaknesses, when in fact, they are known, accounted-for limitations.
Anyone familiar with cryptography will gain nothing from reading this exchange, and anyone unfamiliar with cryptography will likely be confused and mislead.
As indicated above, you would have to brute force your way through 10^77 different combinations to guarantee a successful collision.
You haven’t shown that a SHA2 collision is needed. SHA2 get’s used to create the message digest. That in turn get’s encrypted via the private key.
You are referring to several traits which are common to almost all cryptographic systems, yet you are implying these are traits unique to PGP.
No, I haven’t said anything about something being unique to PGP. My core claim is that you haven’t demostrated safety.
The standard cryptopunk way of thinking is to mistrust statements about crypto that aren’t demostrated to be true.
You can manipulate the output of (or “add specific entropy to”) any hash function. It is, however, absurdly difficult to convey meaningful information in the output of a hash function. See above regarding the amount of work required.
SHA2 in particular hasn’t been successfully attacked. Other hash functions on the other hand have been.
I remember sitting in the audience at the CCC while they explained how the broke SSL at the time via a collision and some other tricks.
and anyone unfamiliar with cryptography will likely be confused and mislead.
They will see that you haven’t demostrated what you claimed in a clear fashion. Anyone who wants safety via crypto-systems should use systems that who’s safety is well established. It’s as it should be.
Furthermore, because a private key is longer than a PGP signature, it is literally impossible to encode the key in the signature.
It doesn’t have to get out all the information in one swoop if you use the thing multiple times.
The fact that you make that argument suggests that you don’t have a real argument that demonstrates safety.
Cryptographic hashes, like those used in digital signing, are designed to be resistant to these types of manipulations.
The attack you’re trying to execute is related to the birthday attack, but somewhat stronger: you’re looking for a function f that takes messages m1 and m2 and optionally a hash h1 valid over m1, and returns a different valid hash h2 that encodes m2 in some way. To do this, you need to be able to generate an arbitrary number of valid hashes for m1 (after which you can make up an encoding scheme based on their structure), which is quite difficult and essentially requires the hash function to be thoroughly broken.
Your best bet is probably some kind of steganographic magic hidden in the signed message itself, or in whitespace around it. That’s limited only by your creativity, but without encryption in the hidden message (which is, of course, possible to add), it’s vulnerable to an equally creative attacker. For short enough carrier messages it may not even be possible.
“Algorithmically” doesn’t mean that there exactly one way to create a valid signature. Hash functions quite often have collisions.
I’m downvoting this comment because it’s misleading.
First of all, no one has ever found an SHA-2 hash collision yet. Second of all, the chances of two SHA-2 hashes colliding is about 1 in 1 quattuorvigintillion. It’s so big I had to look up what the number name was. It’s 1 with 77 zeroes after it. We’re talking universe-goes-into-heat-death-before-it-happens type odds. Only under the most absurd definition of “quite often” could anyone ever reasonably claim that a cryptographic hash function like SHA-2 “quite often” has collisions.
Not that I disagree with your general point, but… 77 isn’t a multiple of 3.
Why does it need to be a multiple of 3?
(SHA-2 = 2^256 = 1*10^77)
You wrote that the odds were 1 in 1 quattuorvigintillion. I was under the impression that all “-illion”s have exponents that are multiples of 3.
Ahhhh. I misread the output on Wolfram Alpha. You’re right. I’ll leave it in the original post for posterity, but also for the record, it’s actually 1 in 100 quattuorvigintillion
(That’s what I get for trying to be dramatic)
That numbers is irrelevant because it’s for randomly chosen hashs.
The main point here is that I don’t know that there a guarantee that there exactly one signature that successfully signs a message for a single private key. Likely there are multiple.
Quick Googling leads me to How PGP works:
A session key that’s coming from a random number generator is an easy way to add specific entropy into the system. Is the session key really nonwhere to be found in the signature? Even if it is, the math behind public-private key crypto is complicated.
PGP advertises that if you know the signature you can be certain that the text isn’t altered. I haven’t found a promise that the signature is deterministic and that it’s impossible to add information to it.
By running your the crypto code through an obfuscator you haven’t made your code easy to read but if you actually try to read your code you find it calls things like “PublicKeyEncryptedSessionKey:a(”./public_key_encrypted_session_key.js”)”.
Sorry Christian but I am going to stop replying after this one. I’m not trying to be a dick, it’s just that at this point I think continuing our conversation is going to confuse readers more than it will help them. The concepts you are referring to and sources you are citing are only tangentially applicable to the conversation at hand.
The fact that it is possible to collide hashes, signatures, etc. is well known and obvious. The reason it is not a concern is the extreme difficulty in producing a collision. As indicated above, you would have to brute force your way through 10^77 different combinations to guarantee a successful collision.
The section you cited describes PGP encryption, not signatures. They are two entirely different things. PGP signatures do not involve session keys.
You can manipulate the output of (or “add specific entropy to”) any hash function. It is, however, absurdly difficult to convey meaningful information in the output of a hash function. See above regarding the amount of work required. Furthermore, because a private key is longer than a PGP signature, it is literally impossible to encode the key in the signature.
The code uses a library, which means it supports multiple functions. The vast majority of which are not used by the script.
You are referring to several traits which are common to almost all cryptographic systems, yet you are implying these are traits unique to PGP. Furthermore, you are describing these traits with loaded language that paints them as weaknesses, when in fact, they are known, accounted-for limitations.
Anyone familiar with cryptography will gain nothing from reading this exchange, and anyone unfamiliar with cryptography will likely be confused and mislead.
You haven’t shown that a SHA2 collision is needed. SHA2 get’s used to create the message digest. That in turn get’s encrypted via the private key.
No, I haven’t said anything about something being unique to PGP. My core claim is that you haven’t demostrated safety.
The standard cryptopunk way of thinking is to mistrust statements about crypto that aren’t demostrated to be true.
SHA2 in particular hasn’t been successfully attacked. Other hash functions on the other hand have been.
I remember sitting in the audience at the CCC while they explained how the broke SSL at the time via a collision and some other tricks.
They will see that you haven’t demostrated what you claimed in a clear fashion. Anyone who wants safety via crypto-systems should use systems that who’s safety is well established. It’s as it should be.
It doesn’t have to get out all the information in one swoop if you use the thing multiple times. The fact that you make that argument suggests that you don’t have a real argument that demonstrates safety.
Cryptographic hashes, like those used in digital signing, are designed to be resistant to these types of manipulations.
The attack you’re trying to execute is related to the birthday attack, but somewhat stronger: you’re looking for a function f that takes messages m1 and m2 and optionally a hash h1 valid over m1, and returns a different valid hash h2 that encodes m2 in some way. To do this, you need to be able to generate an arbitrary number of valid hashes for m1 (after which you can make up an encoding scheme based on their structure), which is quite difficult and essentially requires the hash function to be thoroughly broken.
Your best bet is probably some kind of steganographic magic hidden in the signed message itself, or in whitespace around it. That’s limited only by your creativity, but without encryption in the hidden message (which is, of course, possible to add), it’s vulnerable to an equally creative attacker. For short enough carrier messages it may not even be possible.