Finding ecc private key from plaintext and public key

Question

I am working on a message authentication scheme using libsodium and ed25519. The messages range in size from 256bytes to 1k plus the 56byte signature. With a potential of 90,000 to 350,000 signatures+plaintext per day, many of them will have limited changes and may be very similar (status notifications with an incrementing timestamp ex. 2015083020000126 All's Well).

How susceptible is ECC(specifically ed25519) to a known plaintext attack? How often should I be changing a source's private key to prevent a potential attacker gathering enough messages and reverse engineering the private key?

Answer 1

A good first step would be to introduce something similar to a session key, and then using a block cipher to encrypt the actual payload.

Encryption would work like this:

1. Generate a random passphrase which should more or less be globally unique and should never be reused. If you need to edit the encrypted file and reencrypt, generate a new key.
2. Encrypt that generated passphrase using ED 25519, and store the output at the head of the file along with other metadata (ie: the IV for your block cipher, etc.).
3. Sign your encrypted passphrase using ED 25519, so you'll never decrypt something that wasn't generated by you. Store this next to the encrypted AES key in the previous step.
4. Using your random passphrase for your block cipher, encrypt the payload using something with authentication like AES in GCM mode, or AES in CBC mode with an HMAC.
5. At the end of the file, generate a signature of the encrypted ciphertext, proving that you, the holder of the private key, vouch for its integrity.

This gives you a lot of benefits. First, you're now using a standard block cipher for your payload, and AES (in the right modes of operation) isn't vulnerable to known plaintext attacks. Second, now that you're using a standard block cipher, encryption and decryption will be much faster operations in CPU time. Third, using a block cipher mode which has authentication gives you integrity, and by signing the ciphertext, you assert that not only has the message not been tampered with, it was you who created it.

Step 5 above may not be necessary, as your signature in step 3 should be good enough combined with an authenticated block cipher like AES in GCM mode or CBC with HMAC.

Decryption looks like this:

1. Decrypt your random passphrase using ED 25519 and check its signature. If everything looks good, proceed, otherwise fail.
2. Use your decrypted passphrase to decrypt the ciphertext using your block cipher. Your block cipher should be providing integrity support (GCM or CBC+HMAC) and should fail if anything was tweaked.
3. At the same time that your decrypting each block, pipe the original ciphertext through the ED 25519 signature verification method so you're not having to rescan the entire payload once you're done.
4. After you've finished decrypting the ciphertext, validate that the signature (generated in step 5 above) is valid.

This should provide a pretty robust encryption system.

---

Since I see now that you're mainly looking for message authentication, I've devised another solution which just does that.

Generating message authentication codes:

1. Generate a random key to use with your HMAC.
2. Encrypt and sign that key and stick it at the front of each message.
3. Run your HMAC over the entire plaintext.
4. Append output of the HMAC at the end.

Validating message authentication codes:

1. Decrypt and validate the HMAC key at the head of the message.
2. Generate an HMAC over the plaintext as above.
3. Compare your HMAC's output to the stored HMAC at the end of the message.

Provided that you use a good hash function for your HMAC (ie: SHA-256), this should be a pretty good solution. It effectively removes your concern of known-plaintext attacks for ED 25519 (not that they exist, necessarily), and will generally be a much faster solution in performance than doing signatures natively in ED 25519.