[whoops mispelled cpunks on cc line 1st time, sorry for 2 copies] Perry Metzger <perry@piermont.com> wrote:

Gary Jeffers <gjeffers@socketis.net> writes:

...

Well, I just used MIT's PGP 2.6.2 with 3 different users' public keys to encrypt 3 different files. In all 3 files, the first 3 characters were the same (an umlauted A, then an i with an up arrow over it, and then a heart). This beginning 3 character string is apparently the infamous PGP RSA signature. The signature that says to spooks' programmed encryption sniffers - "HEY! I'M PGP - GIVE ME A LOOK!."

As if they couldn't figure it out anyway. It isn't an "RSA signature" by the way. Read format.doc sometime.

Yeah, that's what stealth does, removes the boiler plate stuff saying, various things, such as pgp version number, rsa encrypted message, conventional idea block, and as Perry says, it's all in pgformat.doc in the PGP docs directory.

...

When are the PGP designers and coders going to get serious and de- velope STEALTH PGP inside PGP itself!?

Never, I hope. It would dramatically lower the utility of the system. Can you imagine how disgusting it would be to try decrypting something if you have a dozen keys outstanding? Not to mention how hard it would be to deal with figuring out that you should even try to decrypt things in the first place.

I reckon it would be a very nice utility, built into pgp as an *option*, some countries it isn't legal to use PGP, and it hasn't been ruled out that the US may not be the next to join the list, all this GAK stuff, son of Clipper, it is a distinct possibility that the law enforcement lot might outlaw other crypto wiht mandatory GAK. Then stealth features for PGP become important for incorporating into stego, of course you can argue that well stealth should be part of the stego app then. It shouldn't be a problem unless it was enforced, as an option I see no problem with it, and lots of possible future advantages even. I'm trying to work on stealth2.1, modifing Henry Hastur's stealth util to added Hal Finney's algorithm for improving the stealthiness (it's not enough to just strip the headers as stealth1.x does, the fact that the RSA encrypted header is always < N, the rsa modulus gives the game away with a few messages to analyse for statistical purposes, ie if you see a lot messages < N, where N is by definition not an even power of 2, and possibly even N is known, or suspected from keyservers). I've been delaying releasing it because I was worrying about ran no generators being good enough, but I think I might have convinced myself that it is not even necessary to use ran no generators, I'd appreciate it if some folks with a bit of crypto expertise could cast their eye over the description below.

...

So what, -that "only a few companies" will be discovered to be using PGP through the RSA signature!? Those few companies are the seeds for the vast numbers of companies that would follow them in using PGP over the Internet. The RSA signature is the flag that allows the spooks to easily net the bold first companies. The RSA signature is greatly impeding the spread of PGP use over the Internet. PGP MUST BE STEALTHED!!

It isn't an RSA signature. Its a bunch of magic numbers.

Look, get real already. If someone sees a bunch of random numbers in mail sent by me, its going to be pretty obvious what the hell is inside anyway.

Yeah, but you wouldn't do it that way. I reckon this is what you'd do: % pgp -es duress % pgp -es msg % stealth < msg.pgp > msg.stl % cat msg.stl >> duress.pgp % pgp +makerandom=1234 noise % cat noise >> duress.pgp % pgp -a duress.pgp % mail someone < duress.asc The pgp +makerandom=<size> <file> is an undocumented feature of pgp > 2.6 (not sure exactly when it got added, Colin Plumb pointed it out when I asked him about ran nos for stealth). So what this means is that you are using PGP it's self to hide a stegoed message. This would be good for the guy from FACTnet (forgotten his name) who just got hit by the CoS, he could hold out for a while, then give up his key, the duress message would appear, and the real message would be explained by having a script to do this on his HD, and having long since burned the disk with a script to do the above on it: % pgp -es msg % pgp +makerandom=4567 noise % cat noise >> msg.pgp % pgp -a msg.pgp % mail someone < msg.asc ie the idea is that you pad your message to a fixed size for the express purpose of hampering traffic analysis (of the type of my, Alice did have a lot to say to Bob that day). It would be even better cover if the thing had gotten sent through a remailer, as this kind of thing is expected of type I remailer traffic (before mixmaster which does the packetizing for you). So the duress message really looks like this: +---------+---------------------------+--------------------+--------+ | pgp hdr | IDEA encrypted duress msg | stealthed real msg | noise | +---------+---------------------------+--------------------+--------+ the IDEA block has a length field, but you can increase the length without damage to include the following stealthed stuff as the underlying stuff which is IDEA encrypted will know it's length on decryption, and the following junk will just be discarded. So, Alice and her secret key ring (encrypted) gets nabbed by the Charlie (CoS?), and coerced into divuling her passphrase. And if and when it is noticed that the message was longer than it ought to be (CoS that smart? substitute the NSA and they'd notice for sure), Alice explains away the junk on the end by pointing them to the fact that all of her messages where exactly (say) 16k long, and that she was using a the noise only script, and that the message really is this: +---------+---------------------------+-----------------------------+ | pgp hdr | IDEA encrypted duress msg | noise | +---------+---------------------------+-----------------------------+ Now we come to arguments about why you might want this built-in to PGP. Well it provides plausible deniablity as you have no extra software which might look incriminating unless you managed to dispose of it first, if it comes as stock. Also the 2nd reason for built-in at least for stealth is if it needs good random number source, but as I said, I'm not sure it needs a random no generator. So comments please, this has been around a few times already, but here's the algorithm for manipulating x which is the RSA encrypted component of the header of an RSA+IDEA encrytped PGP message: (this is a description of my implementation of Hal's algorithm as described on his www page: http://www.portal.com/~hfinney/): consider random no x, RSA modulus N 1 < x < N (that used to say 0 <= x < N, but 0, and 1 being RSA fixed points, 0, 1, and N won't be generated by PGP presumably? I think this shouldn't matter as the keyspace of N is so large that the probability of a 0 or a 1 specifically is nothing to worry about I think.) Hal's algorithm was to convert x to being in the range: 0 <= x' < lim where lim which is the next power of 2 above N * 2^surety, and surety is 64, 64 seems big enough? The recover operation is: x = x' mod N and the create operation is: 1) scale = int( (lim-1) / N ) + 1 2) scale2 = 2^int( log2( scale ) + 1) ie scale2 = next power of two over scale 3) r = MD5( 0, x ) ie MD5 digest of x, as x is an RSA encrypted random session key misc other info, and more random padding to bring up to be close to N in size. It strikes me that we already have a random number, and that provided MD5 can not be inverted (which it is not possible, as it is compressing, and looses info, and the brute force to find which of all the possible y's (0 < y < N) MD5 digests come out to be x. I would have thought it likely that this would be evenly distributed, and that the cost would be enormous? 4) r = MD5( r, rand() ) it will fail some of the time, so in this case repeat with another random number, Istirred it in first but perhaps you would only do it if it failed. Or perhaps it is enough to MD5( r, r ) ie stir r into itself to generate another ran no? So long as there are no rare cycles? Presumably either impossible or infinitessimally small probability. 5) r = r mod scale2 6) if (r > scale) goto 4) 4),5) & 6) are designed to generate an evenly distributed random number in the range: 0 <= r <= scale 7) x' = N * r + x 8) if (x' > lim) goto 4) an example, with small numbers, and surety set to 8, x = 7, and manufactoring the ran nos manually: lim = 2^( int( log2(N) + 1 ) + surety ) = 2^( 4 + 8 ) = 4096 1) scale = int( 4096 / 13 ) + 1 = 316 2) scale2 = 2^( int( log2( scale ) ) +1 ) = 2^(8 + 1) = 512 3) say MD5( x ) = 0x00000000000000000000000000001234 4) say MD5( x, rand ) = 0x00000000000000000000000000001235 = 4661 (base 10) 5) r = 4661 mod scale2 = 4661 % 512 = 53 6) if ( 53 > 315 ) - it's not 7) x' = N * r + x = 13 * 53 + 7 = 696 8) if (696 > 4096) - it's not) so x' = 696 reversing: x = x' mod N = 696 mod 13 = 7 when 6) is true, ie r > scale which will happen half the time on avg with the first ran no, and so on like a coin flip, the chances of many coins flipping the wrong way diminishes rapidly with number of flips. when 8) is true, ie x' > lim, x' can only be > than lim when x = N - 1, and given that x = N - 1, the probability is less of x being in N * scale <= x < lim but this will only occur with probability: 1 1 -------- < ----- 2^surety scale I think. So you'd have to collect one mess of messages to even catch one sample, let alone enough messages to have a statistical proof of steganography being present. Pls check the maths a bit, the above describes the software implementation of Hal's algorithm which he has on-line, on his page: http://www.portal.com/~hfinney/ But the main question I'd like to get verification on is if it is safe to use the MD5 of the RSA encrypted message to perform the operation. I'm essentially doing: x' = N * f(MD5(x)) + x where f(y) is a function which converts from range 0 <= y < 2^128 to a range 0 <= f(y) < scale. Is that safe? x is random, and will be different even for a repeat encryption of the same file, as PGP is using a random IDEA session key. So are there any brute force attacks on that which would be cheaper than attacking 128 bit IDEA? PGP's random number generator also makes extensive use of MD5, so I'm taking the use of MD5 as secure as a given. If it is thought to be dangerous for some reason (it is after all some kind of signature on it's self, presume that you know N, and x' but not x, the question is can the equation be brute force reversed in a less than 128 bit brute force attack. I'm neglecting to consider the rand() calls, which I'm not expecting to add security, but are just a mechanism to stir the value with to get more random nos, as occasionally the alogrithm needs more than one, if the first fails, etc. If people reckon it's insecure, then it would be ideal to include the stealth functionality into PGP, so that integral use of PGPs ran no routines can be made. I was previously using an MD5 digest of PGPs randseed.bin for this, but you can't stir it (well you could but that would considered a security risk diddling with PGPs files), and not stirring means you have no improvement over the above, in the event that that your system is captured with the known plaintext. If you stirred it there would be no proof of that being the message in the file. Even unstirred, if the N * f(MD5(x)) + x is no good, the inclusion of a digest of the randseed.bin would be a big improvement. It seems rather messy to have all of the keyboard sampling stuff, for PGP keys duplicated for this. Hope the x' = N * f(MD5(x)) + x construct is secure as this will avoid the issue. Adam