Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is an approximate length for a digital signature (SHA) given the following?

Using RFID tags, size ranging from 100 to 2000 bytes (8000 bits), our project is setting aside a portion for a digital signature against its fixed data, which includes an unique 8-byte serial number and with 32 to 64 bytes of factory data.

The signature, obviously longer leads to more security, will be for authentication (repudiation is not important). As the fixed data and signature can consume a sizable percentage of the tags, and 2013 technology being what it is (signature can't be too short), I looking to approximate the minimal size needed to securely authenticate data.

Example tag allocation
Fixed data 64 bytes
Unique Serial Number 8 bytes
Digital Signature ?? (32 - 64+ bytes, 256 - 512+ bits) I'm thinking 64 bytes, but that takes a good chunk of space - maybe overkill.

A prompt answer is not required.

To authenticate 64+8 bytes, what minimal digital signature length is recommended?

share|improve this question
1  
If it's fine for the verifier(s) to be able to create valid authenticators, then you can use a MAC instead. –  Ricky Demer Jul 23 '13 at 23:27
    
Please note that SHA is not a signature algorithm, it is a hash algorithm family. –  Paŭlo Ebermann Jul 31 '13 at 20:19
add comment

1 Answer 1

up vote 2 down vote accepted

BLS signatures are $\:2\hspace{-0.04 in}\cdot\hspace{-0.03 in}k\:$ bits long, where $k$ is the security parameter, and the probability of a forgery is $\hspace{.01 in}\epsilon$.


Pseudorandom MACs (such as HMAC) can be truncated to $L\hspace{.01 in}$ bits, and the probability
of forgery (by someone who is outside of the system) will be $\: \frac{\text{# of tries}}{2^{\hspace{.01 in}L}}+\epsilon \;\;$.

(As alluded to in my comment, the verifier(s) can trivially forge valid authenticators for the MAC approach.)

share|improve this answer
1  
@e-sushi Thank-you for your BLS suggestion. –  chux Jul 25 '13 at 16:45
    
@chux You're welcome… –  e-sushi Jul 25 '13 at 16:46
    
I see 2048 bits is the standard for today, with little regard to the size of the document. 1k may work, but its becoming dated. Thanks for the MAC idea. –  chux Jul 25 '13 at 16:47
    
@Ricky Demer Thanks for the added info. As 2 kbit will not fit into the smaller RFID tags, looks like a MAC will have to do. I'm thinking 256 or 512 bit MAC will suffice, but that sounds like another question. –  chux Jul 31 '13 at 20:50
    
@chux : $\;\;$ 2048 bits is the standard for RSA signatures, not BLS signatures. $\:$ $\:k >256\:$ or $\:L >160\:$ would be way overkill. $\:$ I would advise you to consider what security parameter you want (2048-bit RSA is estimated to give $k=112$), and decide whether or not it would help if the signature allowed you to recover part of the message (i.e., the signed message is shorter than the signature plus the message). $\;\;\;\;$ –  Ricky Demer Jul 31 '13 at 21:47
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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