Re: [Botan-devel] choosing the right algorithm

[Jack L. <ll...@ac...>]

On Tue, 24 Jun 2003, Roddi wrote:

> Hi,
>
> I have some difficulties for choosing the right algorithm for the
> following problem:

[...]

> The solution would be to let the user to key in the signature by hand
> (if he/she chooses to).
>
> Now the question:
> Is there a public-key algorithm that can sign with a signature length
> of 128bit (or preferably even shorter) and that would still be secure?

Not that I know of. Even DSA (which has quite small signatures) would
produce sigs quite a bit larger than that (lets say, large enough that it's
extremely unlikely that the average person would be able to correctly
transcribe the whole thing without making an error). You could get (secure)
authentication that small by using, e.g, a message authentication code. The
problem then being that someone could find the key hidden in the binary,
and produce a keygen. I imagine you would like to prevent this by using PK
signatures.

Hmmmm... actually, I can think of a way of doing this. DSA produces a
signature of size 2*n, when the parameter q is n bits. Typically q is 160
bits (which is consistent with current security needs), because DSA can be
broken with (roughly) 2^(n/2) effort, and 2^80 is considered the minimum
amount of work required to be safe. Now, if you used a q that was only 64
bits long, this would produce a 128 bit signature, **BUT** it would not be
very secure. It would not be trivial for someone to break, but it would
certainly be possible, especially if they were well versed in crypto.

That said, I think you may be better off forcing the user to have internet
access, at least enough that they can download a license file. Another
alternative would be, for people who absolutely couldn't get on the net
(which I suspect is quite rare these days), would be to give them a phone
number to call, where they can read off whatever serial number and machine
ID info is needed (probably generated and shown on the screen for them).
Then (after doing verification, etc) you mail them a floppy disk or CD-R
with the license file included on it. I know music software tends to be
expensive, so it may be cheaper to use stronger crypto (which is free), and
hire someone to man a phone line (which is cheap), than to risk widespread
pirating and losing sales (which could be very expensive).

-Jack