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?

  • Perhaps a good first step would be to have a method of generating a nonce-key and then running things through a difference cipher (AES 256 in GCM for example). Generate a random AES key and encrypt the key with ed25519. Store that in the head of the file. Encrypt the rest of the file with the decrypted original AES key. This might best be asked on crypto.se. Aug 26 '15 at 17:31
  • Possibly, I didn't notice crypto.se since it is in beta. If I were to add encryption I would just go with Curve25519 and be done with it. But an attacker watching the network would still be able to suck up the traffic and connect it with plaintext content since this is running a public facing alert system. Aug 26 '15 at 17:42
  • Looks like this was answered crypto.stackexchange.com/questions/14486 could someone mark it as such? I don't seem to have the reputation to do so. Aug 26 '15 at 18:43

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.

  • The issue is the payload. Plaintext will be publicly available, we are using this to authenticate the source. Also we are going with ECC over AES for resource reasons as this needs to be available to low power embedded systems without impacting performance. It is also why we are going with very short messages. Aug 26 '15 at 17:46
  • AES is usually hardware accelerated and should perform better than ECC. Public/private key operations are almost always more expensive than standard block ciphers like AES. My CPU here has AES instructions which allow it to do something like 2.6GB/s of AES encrypt/decrypt by using native extensions. If you use AES like I've recommended, you need not fear known ciphertext problems, provided that your RNG/passphrase/IV are good. Aug 26 '15 at 17:50
  • Ah, and I'm seeing now that you mainly care about message authentication and not encryption. You could do something similar as I've recommended above by running an HMAC over the entire payload with a ED25519-encrypted key. Aug 26 '15 at 17:53
  • ...and I've updated my answer to reflect that. Aug 26 '15 at 18:00
  • for this useful effort you deserve +1 (nice blog you have too :) )
    – user45139
    Aug 26 '15 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.