jeeq: ECDSA encryption

[jackjack]

Hey all
I read everywhere that ECDSA can't be used to encrypt
The fact is it can, I made a basic implementation: https://github.com/jackjack-jj/jeeq

It uses a kind of secret sharing and it looks like that works well
It's in python and requires no dependencies

Code:

> pubkey='0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'.decode('hex')
> print encrypt_message(pubkey,"goodbye world!")
amoAAAJQkgEDcToivOFhH0zhaytsAKbW9dKCmOJ25FMPaj/6WssXAQKsSJpnq1IlNOx7GZbg++x6ZRUXAb/3jxaxwPGqlcItmA==

Code:

> pvk = str_to_long('0000000000000000000000000000000000000000000000000000000000000001'.decode('hex'))
> print 'output:', decrypt_message(pvk, msg_to_decrypt, verbose=True)
Public header (size:2): 0x5092
  Version: 0
  Checksum of pubkey: 5092
Private header (size:6): 0x0000000e75f1
  Message size: 14
  Checksum: 75f1
Decrypted message: goodbye world!
  Hash: 75f1
  Corresponds: True
output: ['goodbye world!', True]

My concern is about the security, can a crypto-pro give it a quick look? I'm sure it's as sure as signing because breaking it would need the same discrete logarithm than in Bitcoin but well, you never know...



Edit: I'd be happy to receive some crypted messages, you can find my public key on blockchain.info

[etotheipi]

Did you look at ECIES?

[Zeilap]

You've come up with ElGamal encryption independently. Pretty impressive .

[jackjack]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

You've come up with ElGamal encryption independently. Pretty impressive .

Yeah that's true it's really similar! Not being a crypto guy (even though I'm rather good at maths) I can't imagine I'm the only one who tried that kind of things, so why is it not used?

Also, as I understand the article my implementation seems secure

[Shevek]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

AFIK, HMAC is needed only when you use a non self-authenticate symmetric encryption. For example, CTR mode must be used with external authentication (HMAC). But, in principle, CBC does not need HMAC (and so don't KDF, because the shared secret can be used as the single key).

[archaeopteryx]

Did you look at ECIES?

No, but as I understand the wikipedia article, it seems a bit more complicated (or maybe it's just because I'm not comfortable with KDFs and HMACs)
Can it be used with ECDSA private keys?

You've come up with ElGamal encryption independently. Pretty impressive .

Yeah that's true it's really similar! Not being a crypto guy (even though I'm rather good at maths) I can't imagine I'm the only one who tried that kind of things, so why is it not used?

Also, as I understand the article my implementation seems secure

I'm not a crypto expert, but if your implementation is truly the same as ElGamal, well it is being used. For example, Pretty Good Privacy implementations use ElGamal as one of the options.

[jackjack]

AFIK, HMAC is needed only when you use a non self-authenticate symmetric encryption. For example, CTR mode must be used with external authentication (HMAC). But, in principle, CBC does not need HMAC (and so don't KDF, because the shared secret can be used as the single key).

Hmm ok I think I get it, I'll look into an ECIES implementation to see how they handle that

I'm not a crypto expert, but if your implementation is truly the same as ElGamal, well it is being used. For example, Pretty Good Privacy implementations use ElGamal as one of the options.

I meant ElGamal with ECDSA. ElGamal is only with DSA, doesn't it?

[jackjack]

I just pushed a new version
You no more need to mess with the code, -i, -k and -o options handle files and data

Example:

Code:

#ENCRYPTION (-e)
python jeeq.py -e                                                 #Will ask for the text to encrypt, the recipient's public key and will print the output
python jeeq.py -e -i secretkeys.txt                               #Will ask the recipient's public key, will encrypt secretkeys.txt and will print the output
python jeeq.py -e -i secretkeys.txt -o encryptedsk                #Will ask the recipient's public key, will encrypt secretkeys.txt and will write the output to the file encryptedsk
python jeeq.py -e -k 0499a6037487a0ea0ae4867f7e60a6c4ac477103b4d3ed9ce8c84804a32f53ff802633de6e8ccd6a9b13fab97a29b0bda794576613f5abc17b40d993629c457aae
               #Will ask for the text to encrypt, will use the given recipient's public key and will print the output

#DECRYPTION (-d)
python jeeq.py -d                                                 #Will ask for the text to decrypt, the recipient's private key and will print the output
python jeeq.py -d -i encryptedsk                                  #Will ask the recipient's private key, will decrypt encryptedsk and will print the output
python jeeq.py -d -i encryptedsk -o secretkeys-decrypted.txt      #Will ask the recipient's private key, will decrypt encryptedsk and will write the output to the file secretkeys-decrypted.txt
python jeeq.py -d -k 0000000000000000000000000000000000000000000000000000000000000001
               #Will ask for the text to decrypt, will use the given recipient's private key and will print the output

The options are of course mixable

[Qwedcxza1]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

[jackjack]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

Let's say I want to encrypt 'hello' to your address

pubkey: your public key
privkey: your private key

I split my message in 32-char long chunks and put "0x00"s at the end of the last one to make it 32-char long too. That gives here only one chunk: 'hello---------------------------'. ('-' represents one 0x00)

Now each chunk is used as an X. Let's call the correponding point M (Two M's are possible but it doesn't matter as I never use Y)
Then I take a random N and calculate:

• G*N
• pubkey*N + M

Those points are the encrypted data to be sent to the recipient. As pubkey=privkey*G, M is easily calculated.



Note: Not all X values leads to a point on the EC. In such cases I just use offsets.

[oleganza]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

[Qwedcxza1]

I'm not a programmer so it's difficult to understand this without seeing a proper mathematical description of the encryption and decryption methods.
If it uses elliptic curves then I doubt if you have reinvented EIGamal crypto system.
There are hybrid cryptosystems based on elliptic curves such as ECIES but the plain text is not required to be a point on the curve.
 The problems of using elliptic curve implementations of EIGamal rather than discrete logarithm implementations relate to message expansion factors and difficulties of deterministically generating points on the curve which is why hybrid solution such as ECIES are used.
 Generally I would say that home made crypto systems should be approached with caution. There are plenty of good crypto systems out there.

Let's say I want to encrypt 'hello' to your address

pubkey: your public key
privkey: your private key

I split my message in 32-char long chunks and put "0x00"s at the end of the last one to make it 32-char long too. That gives here only one chunk: 'hello---------------------------'. ('-' represents one 0x00)

Now each chunk is used as an X. Let's call the correponding point M (Two M's are possible but it doesn't matter as I never use Y)
Then I take a random N and calculate:

• G*N
• pubkey*N + M

Those points are the encrypted data to be sent to the recipient. As pubkey=privkey*G, M is easily calculated.



Note: Not all X values leads to a point on the EC. In such cases I just use offsets.

To be honest with you, I'm a bit busy and I haven't got time to study all of this. I'm really not knowledgeable enough to be properly commenting on this stuff anyway so I hope it does work and I'm going to retire and let you find some real experts.

[jackjack]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

[oleganza]

How about using ECC point multiplication and AES:

[...]

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

What do you mean? Sender must know the message it is about to send.

[jackjack]

How about using ECC point multiplication and AES:

[...]

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's indeed much more efficient
Just out of curiosity, is it possible to tweak this a bit to make the sender unable to read the crypted message?

What do you mean? Sender must know the message it is about to send.

I was thinking about the private key s. The computer I'm using everyday should be safe but I wouldn't trust it for something risky.
If I use your method, the computer may keep s somewhere (HDD, RAM, bash history, etc) and if it's compromised the attacker might be able to retrieve it and decrypt the message.

Now that I'm writing it I realize that the same goes for the message and the random N...

[Shevek]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's OK but:

1) There is no need of doubling SHA256 to obtain the symmetric key. SHA256^2 is a bitcoinish thing that does not improve the security of SHA256. In fact, there is no need of SHA256. Take "Kx" as symmetric key and it's ok.
2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

[jackjack]

How about using ECC point multiplication and AES:

1. Get recipient's public key R (R = r*G, r is private key)
2. For each message, generate unique keypair S,s: S = s*G.
3. Create a shared secret: K = R*s
4. Compute 256-bit encryption key out of that shared secret: key = SHA256(SHA256(K))
5. Encrypt the message with that key and send the message together with unique pubkey S.
6. Recipient gets the message and computes key using his private key r and S: key = SHA256(SHA256(r*S))
7. Recipient's key turns out to be the same because r*S = R*s = r*s*G.

I like this scheme more because it allows to efficiently encrypt messages of arbitrary sizes.

It's OK but:

1) There is no need of doubling SHA256 to obtain the symmetric key. SHA256^2 is a bitcoinish thing that does not improve the security of SHA256. In fact, there is no need of SHA256. Take "Kx" as symmetric key and it's ok.
2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

2. Indeed!
1. Wouldn't you lose one bit of entropy? (As only half of x values between 0 and n-1 leads to a pair of points)
Using Kx+(Ky&1) should make it a bit better right?

[Shevek]

1. Wouldn't you lose one bit of entropy? (As only half of x values between 0 and n-1 leads to a pair of points)
Using Kx+(Ky&1) should make it a bit better right?

Uhmm... if you don't want to leak even a single entropy bit, I think it's better SHA256(K)

[oleganza]

2) It is better to use "S" as the shared secret and send "K" to the recipient. She can get the secret "S" as S = r^(-1) * K. This way, you can send the same encrypted message to many recipients: just create the K1, K2, K3, etc, pubkeys for de recipient's keys R1, R2, R3, etc

This is smart. Thanks for suggestion.

[oleganza]

I was thinking about the private key s. The computer I'm using everyday should be safe but I wouldn't trust it for something risky.
If I use your method, the computer may keep s somewhere (HDD, RAM, bash history, etc) and if it's compromised the attacker might be able to retrieve it and decrypt the message.

Now that I'm writing it I realize that the same goes for the message and the random N...

If you are trusting your computer with your message, you can trust it to hold a secret for a fraction of a second. Once you send out a message, simply clear the secret from memory, so it's not swapped on disk or otherwise extracted due to some corruption later on (it's a standard security practice, btw: put some secret in memory, use it, then zero it out ASAP).