Monty Cantsin writes:
You can't see it up here, but this is a signed message using a protocol which is modestly titled "Cantsin Protocol No. 1". Suggestions for improvement are most welcome.
A very interesting idea! Please consider the following suggestions if you like, or feel free to ignore them. One problem with signatures which have no indication at the top is that two passes over the data are necessary: the first to scan and find the start-of-signature indicator, and another to go back and calculate the hash. Signatures such as S/MIME and PGP have enough information at the top of the signed message to allow one pass processing.
The first line is "16A5942B6EED349ECF4594C784DFD177 [Cantsin Protocol No. 1]". The hexadecimal number was chosen randomly and is the indicator that this is a Cantsin Protocol No. 1 signature. The number was chosen randomly and it is somewhat unlikely that anybody else will accidently choose it.
You might want to think about what happens if the document itself contains (maliciously, or perhaps because it is talking about your signatures) the string in question (as yours does and this one does as well). This could throw off an automated signature checker.
The second line in the signature is an SHA1 hash of the public key. The hash is computed on the concatenation of the hexadecimal ASCII forms of p, g, and y respectively. There should be no leading zeros. (Remember to leave off the newline!)
Presumably you could use the key hash to look up the key to use for verifying the message. This has a mild denial of service attack. Someone else could create a key with different boundaries between p, g, and y but which would create the same string as this concatenation, and therefore the same hash. If you left the "p: ", "g: ", and "y: " in place it would prevent this. PGP's key fingerprints have had the same problem.
The fourth line contains an offset and a length to specify the area of the text which is signed. The offset is relative to the signature itself. That is, the first character of the Cantsin Protocol No. 1 code is at position 0. As signatures are usually appended, the offset will usually be the additive inverse of the length.
It is intriguing that this can be used to sign a subset of the text. Presumably there could be multiple signature blocks each of which signed different subsets, possibly with different keys. One problem is that it is not obvious to the human reader what part of the text is signed. A nice effect with PGP and S/MIME signatures is that even readers who don't have the tools can have some slight confidence in signatures, because other readers will often report it when signatures don't verify. With a signature that only covers a portion of the text, people might assume that if there are no reports of failure, more of the text is signed than is the case. This is not a technical problem but is a social phenomenon which may not interact well with this signature format. You need to specify a canonical line ending format. Based on the count values in your document, it appears that you are counting line terminators as being one character long. Your count value of 1CB9 corresponds to decimal 7353, there are exactly 7353 characters from the first character of your message body to the beginning of your signature magic number, if line ends are one character. The specific characters for line endings need to be specified as well for the hash to be calculated consistently. Your hash appears to be calculated with LF as the line ending (although the hash program is broken, see below). Probably CR/LF would be preferable for the line endings as that is a widely used internet standard as well as being common on windows.
You also need to be able to compute SHA1 hashes. I've been using something called "sha1file" which, I believe, originated at Adam Back's web site.
That program has a bug. The routine SHA1_update in the file sha1.c is missing a line: while ( ctx->mlen == 64 ) { convert_to_bigendian( (word32*)ctx->M, 64 ); SHA1_transform( ctx ); use = min( 64, data_len ); memcpy( ctx->M, data, use ); ctx->mlen = use; data_len -= use; *** data += use; *** MISSING *** } Correcting this will make your hashes be correct.
El Gamal is simple enough that the signature on this message can be checked using standard Unix tools such as dc version 1.1. Let's say M is the SHA1 hash of the message. It is checked by verifying the truth of this equation: (y^a * a^b) mod p = g^M mod p.
El Gamal is a rather lengthy signature, although the verification equation is relatively simple. DSS has a shorter signature. If you report not r,s, but rather r,w where w is the inverse of s mod q, then the verification is: r = g^(M*w) * y^(r*w) mod p mod q. It's not really much more complicated. There are some subtleties to choosing El Gamal keys, but with the 2048 bit values you have chosen you are pretty safe. You want to make sure that the generator g doesn't generate a small subgroup; to do this you need to look at the factors of p-1. Your p-1 has several small prime factors: 0x2^3, 0x3, 0x6b, 0x16f, 0x1f79b, 0x3533a1eb3. Beyond that is a 1978 bit composite which I can't factor. Chances are very high that a random g will generate a group of size which is a multiple of a large prime factor of this large composite value, so it is strong, although not quite 2048 bits strong. Also, you can't really justify using 2048 bit keys when your hash is only 160 bits. The hash becomes the weak link for keys beyond about 1024 bits, and unless you use a stronger hash your key strength is misleading. This is why DSS is only specified up to 1024 bits. -- A hasher to be named later --