I need to write an "Authoring" application which produces large files. These files must be signed so that the "Consuming" application knows that it was authored with a matching key. The consuming application must access the signed files read-only, with random access. This means it will not read the full file but still must check that the read bytes are signed.

I have thought cutting the data into 64k blocks and sign these blocks individually using a RSA private key with Crypto++.

  1. Is there a RSA scheme which produces fixed size signatures?
  2. The last block can be as small as 1 byte. Is there any cryptographical risk doing this?
  3. Is this globally a good idea?
  • $\begingroup$ Compute a Merkle Tree Hash and sign its root. Merkle trees support efficiently proving that certain blocks belong to a root by looking at uncle hashes. $\endgroup$ – CodesInChaos May 23 '16 at 8:53
  • 2
    $\begingroup$ Signing individual blocks allows an attacker to combine blogs from several files you signed or even reorder the blocks within a single file, resulting in a file that you never signed. $\endgroup$ – CodesInChaos May 23 '16 at 8:56
  • $\begingroup$ What about just adding an index and a file unique id to every block and sign it with the block data? You prevent both reordering and file mixing. $\endgroup$ – galinette May 23 '16 at 10:03
  • $\begingroup$ Thanks for the Merkle tree hint, I will read about it. It is maybe an overkill solution, though. $\endgroup$ – galinette May 23 '16 at 10:04
  • $\begingroup$ With that approach you also need to tag the last block or authenticate the length, otherwise you'll suffer from truncation attacks. (Personally I still prefer the hash-tree or at least hash-list approach). $\endgroup$ – CodesInChaos May 23 '16 at 15:33
  1. Is there a RSA scheme which produces fixed size signatures?

Normally RSA signatures are fixed size. Depending on encoding and the details included, the length may vary by at least a few bytes, though. There is usually a known maximum at least.

  1. The last block can be as small as 1 byte. Is there any cryptographical risk doing this?

No. As long as a good signature scheme (including a secure hash and proper padding in the case of RSA) is used the length of the data signed does not matter.

  1. Is this globally a good idea?

Firstly, signing each block individually does not allow verifying that their order is correct – an attacker could reorder the blocks and the corresponding signatures. You would need to add at least an index of the block to the signed data to verify that. (You likely also need to sign the file identity and length to prevent moving blocks between files or leaving data off the end.)

It also seems somewhat inefficient — RSA signatures are quite long and computing them is relatively time-consuming. But you know best whether the performance is sufficient or the space usage a problem in your use case.

Signing a hash list or hash tree of the data would allow storing a shorter signature and verifying blocks faster — you only need to verify a signature of the hashes once, then it suffices to check that each block hashes to the correct value. It would also take care of verifying the ordering. However, it would require reading and verifying a length-dependent list/tree of hashes before reading the actual data, which may be a problem.

  • $\begingroup$ I'm not sure if the reading of the hash data would become an issue quickly. Even with a 64 byte (512 bit) hash the minimal size of the list would 64 bytes per 64 KiB block. A quick calculation shows that you're already up to 64 MiB before the hashes take up more space then a single block. Personally I would go for a larger block size if really big files are concerned. Modern computers and even phones should have no issue with 1 MiB blocks minimum - leading to a 16 x 16 = 256 fold increase before the hash list overtakes the block size (16 GiB) - if that matters at all. $\endgroup$ – Maarten Bodewes May 23 '16 at 10:00
  • $\begingroup$ In order to prevent an attacker to mixing blocks between files, adding a file id to the index in every block is also required. Could you add this to the answer? $\endgroup$ – galinette May 23 '16 at 10:07
  • $\begingroup$ @MaartenBodewes, size-wise probably not, but I can imagine cases where you would need all authentication data to be stored right next to the block, so that true random access is possible - i.e. there is no access to data except to an authenticated block. $\endgroup$ – otus May 23 '16 at 10:07
  • $\begingroup$ @galinette, added, but even it would not be enough to prevent an attacker from dropping blocks off the end, so a hash list/tree is better. $\endgroup$ – otus May 23 '16 at 10:10
  • 1
    $\begingroup$ @galinette, simplest solutions are to store the hash list in a separate file or to append it (with a final length field to easily find where it starts). $\endgroup$ – otus May 23 '16 at 11:31

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.