3

I have some unusual size constraints for my data which may be relevant to the prescribed solution.

The scenario is as follows. Secure server A generates 240 bytes of data that need to be consumed by an offline client B. Client B needs to ensure that the 240 byte message was not altered. I tend to stumble ingloriously over the semantics and terminology of the security world, but I believe what I am looking for is 'data integrity'.

If I follow this process does it guarantee 'data integrity'? (I realize guarantee might be a strong word)

  1. Generate a public/private key pair on the server A
  2. Perform an asymmetric encrypt on the 240 byte message using the private key (a signing operation if I understand properly)
  3. Client B is issued the public key and the encrypted (signed) messsage

If Client B is successful in decrypting the message does this guarantee, at least academically, that the data has not been altered with?

Note 1: The number of bytes available on the transfer medium to Client B are at a premium, an increase of up to 40% increase due to the encryption could be tolerated, for example an RSA signature using a 2048-bit key resulting in 256 bytes from my 240 byte message would be acceptable.

Note 2: There is no expectation of privacy. I do not care if the data can be read by anyone. Only that the scheme can detect if the message has been tampered with.

Ancillary Question: Is there a recommended algorithm? I have been toying with RSA using 2048-bit keys.

Thank you security wizards, I don't know how you guys do it.

Chris A.
  • 33
  • 1
  • 3
  • Do you need to use asymmetric keys? An HMAC would be fine if not. – AndrolGenhald Apr 09 '18 at 21:23
  • 1
    Your understanding of signing is incorrect. Signing is sometimes incorrectly described as encrypting a hash of the data with a private key, but "encrypting" the data itself provides no integrity. – AndrolGenhald Apr 09 '18 at 21:25
  • @AndrolGenhald Do you have a source which details this fact? This seems contrary to everything I have read. Even [MSDN](https://msdn.microsoft.com/en-us/library/windows/desktop/aa387460(v=vs.85).aspx) describes signing as encrypting. As far as using an asymmetric algorithm, I'm not explicitly bound to one but the key which is accessible to the client will be presumably accessible to the public. – Chris A. Apr 09 '18 at 22:59
  • [This](https://security.stackexchange.com/a/87373/151903) is a good (though lengthy) explanation. tl;dr RSA signing uses the same operation as RSA decryption, and verifying a signature uses the same operation as RSA encryption, but signatures and encryption use different padding. It'd be more accurate to say signing is actually "decrypting" the hash of the data, though at that point the explanation becomes less intuitive, and still doesn't account for padding. That MSDN article looks woefully incorrect in regards to signatures. – AndrolGenhald Apr 09 '18 at 23:34
  • Encrypting is a bad idea, it works for RSA and doesn't for others methods like EC. It has a length constrain, and needs to be properly padded. Use PKCS RSA signature of hash or do ECDSA or something. – VovCA Apr 09 '18 at 23:36
  • @AndrolGenhald Thanks for the reference, I think that was the most informative and authoritative bit of information I've seen yet. I think part of my confusion is the terminology and explanation that is used specifically for RSA. I do see the author's note "Crucially, the security requirements for the encryption padding are quite distinct from those for the signature padding." – Chris A. Apr 10 '18 at 00:19

2 Answers2

1

You're on the right track, what you want is to use a private/public key pair to create and verify signatures.

But first

Your understanding of signature algorithms is incorrect. You've been given the "standard" encrypt the hash of the data explanation and misinterpreted it.

First, the common explanation is that you encrypt a hash of the data, not the data itself. If you encrypt a hash of the data, then someone modifying the data won't know how to alter the encrypted hash so that it matches. If you encrypt the data itself there is nothing to provide integrity. An attacker can modify it however they want (however they won't be able to know the decrypted value they're changing it from or to).

Second, this all too common explanation is incorrect (see here for a better but lengthy explanation). This explanation only works for RSA, and it's not even really accurate for RSA. One of the operations performed to create an RSA signature is also used in RSA decryption, so it'd be more accurate to say that an RSA signature is the decryption of the hash of the data, but then you're decrypting something which was never encrypted to begin with, which is even more confusing, and that still doesn't account for the different padding required for signatures and encryption.

Now the answer

A signature is definitely what you're looking for, but RSA signatures are large (256 bytes for a 2048 bit key), so I'd recommend that you look into ECDSA, as the signatures are much smaller for a similar security level. According to that Wikipedia article, to have a 128 bit security level (very standard) your signature will be 512 bits, or 64 bytes, which seems acceptable. Just please, please find a library to do it for you, it's far too easy to screw these things up.

AndrolGenhald
  • 15,506
  • 5
  • 45
  • 50
  • 1
    Many thanks for pointing me in the correct direction. I'll look into the elliptic curve family of signatures as it most certainly seems to fit the tiny footprint of bytes I have at my disposal. I wouldn't dare implement one of these things myself. I know enough to know that is a no-no. – Chris A. Apr 10 '18 at 00:22
  • Looks great, just threw together a quick demo using standard crypto libraries. 240 byte message encrypted with 2048-bit RSA then signed with 256-bit ECDSA yields a message of 320 bytes. Not too shabby. – Chris A. Apr 10 '18 at 16:01
0

No, asymmetric encryption doesn't guarantee data integrity. One way to demonstrate this is to exhibit an asymmetric encryption scheme that guarantees confidentiality but nevertheless is malleable (and adversary can modify ciphertexts without the recipient being able to detect it).

The link in the previous paragraph explains that RSA, ElGamal and Paillier (asymmetric encryption algorithms) are malleable, so those are already three examples. Another form of example follows from noting that nearly practical asymmetric encryption systems are hybrid—they use asymmetric primitives to protect a symmetric session key, and then use a symmetric encryption algorithm to process the message text. And since many symmetric encryption algorithms are malleable as well, you can easily construct malleable hybrid systems.

That's the theoretical answer. The practical answer is don't roll your own—use well-vetted encryption implementations that have been designed not to fall into malleability pitfall. The typical solutions are to use either digital signatures (asymmetric) or authenticated encryption (either in a symmetric system, or in the symmetric part of a hybrid system).

Luis Casillas
  • 10,361
  • 2
  • 28
  • 42