GnuPG Celebrates 10 Years

[Posted December 27, 2007 by cook]

From:		Werner Koch <wk-AT-gnupg.org>
To:		gnupg-announce-AT-gnupg.org
Subject:		GnuPG's 10th birthday
Date:		Thu, 20 Dec 2007 10:55:16 +0100
Message-ID:		<87tzmdbshn.fsf@wheatstone.g10code.de>
Cc:		info-gnu-AT-gnu.org, lwn-AT-lwn.net

               A Short History of the GNU Privacy Guard
               ========================================

It's been a decade now that the very first version of the GNU Privacy
Guard [0] has been released.  This very first version was not yet
known under the name of GnuPG but dubbed "g10" as a reference on the
German constitution article on freedom of telecommunication
(Grundgesetz Artikel 10) and as a pun on the G-10 law which allows the
secret services to bypass these constitutional guaranteed freedoms.

Version 0.0.0 released on December 20th 1997 [1], was a barely working
replacement of PGP avoiding all patented algorithm by using Elgamal
and Blowfish instead of RSA and IDEA.  It was prominently marked as a
test version but nevertheless included most of the features of the
current GnuPG.  The data format however was not compatible with
OpenPGP but oriented towards the PGP 2 format with a few extensions
(e.g. to allow streaming of data).  The OpenPGP working group was
founded back in fall 1997 and I learned a bit to late about it to
build "g10" according to the then existing draft.  For copyright
reasons it was practically not possible to reverse engineer the format
used by PGP-5, so the establishment of the OpenPGP WG was the right
thing at the right time.

Before talking about GnuPG we need to go some more years back in
history: To help political activists Phil Zimmermann published a
software called Pretty Good Privacy (PGP) in 1991.  PGP was designed
as an easy to use encryption tool with no backdoors and disclosed
source code.  PGP was indeed intended to be cryptographically strong
and not just pretty good; however it had a couple of inital bugs, most
of all a home designed cipher algorithm.  With the availability of the
source code a community of hackers (Branko Lankester, Colin Plumb,
Derek Atkins, Hal Finney, Peter Gutmann and others) helped him to fix
these flaws and a get a solid version 2 out.

Soon after that the trouble started.  As in many counties the use or
export of cryptographic devices and software was also strongly
restricted in the USA.  Only weak cryptography was generally allowed.
PGP was much stronger and due to the Usenet and the availability of
FTP servers and BBSs, PGP accidently leaked out of the country and
soon Phil was sued for unlicensed munitions export.  Those export
control laws were not quite up to the age of software with the funny
effect that exporting the software in printed form seemed not to be
restricted.  MIT Press thus published a book with the PGP source code
which was then scanned outside the USA to form the base of PGP-2i ("i"
for international).  Since then that version was used widely.

The criminal investigations against Phil ended in 1996 and he founded
PGP Inc to write PGP-5.  The first public release was done in spring
1997.  The same year at the 39th IETF meeting at Munich in August Phil
Zimmermann and Jon Callas asked the IETF to setup a working group to
publish a standard for the protocol used by PGP-5 under the name
OpenPGP.  The main drive behind this was to allow widespread use of
strong encryption even if at some point the new company would decide
to stop selling and supporting PGP.  As it turned out PGP Inc was
acquired by Network Associates just a few months later and in 2002
this company actually ceased support and development of PGP (though
the PGP product was later continued by the new PGP Corporation).

Also often claimed to be Free Software, PGP has never fulfilled the
requirements for it: PGP-5 is straight proprietary software; the
availability of the source code alonedoes not make it free.  PGP-2 has
certain restrictions on commercial use [2] and thus puts restrictions
on the software which makes it also non-free.  Another problem with
PGP-2 is that it requires the use of the patented RSA and IDEA
algorithms.  The patent on RSA was only valid in the USA but the
patent on IDEA was and is still valid [3] in most countries.

Although the GNU project listed a requirement for a PGP replacement
for some years on its task list, it was not possible to start
implementing it as long as patents on all public key algorithms were
valid.  That changed when in April 1997 the basic patent on public key
algorithms expired (the Diffie-Hellman US patent 4200770) and finally
in August when the broader Hellman-Merkle patent (4218582) expired.

A month later, at the Individual-Network Betriebstagung at Aachen [4],
Richard Stallman continued his talk with a BoF session where he asked
the European hackers to start implementing public key software.  The
arms trafficker laws of the USA prohibited the GNU project to write
such software in their country or even by US citizens working abroad.
Thus he told the European hackers that they are in the unique position
to help the GNU with crypto software.

Being tired of writing SMGL conversion software and without a current
fun project, I soon found my self hacking on PGP-2 parsing code based
on the description in RFC-1991 and the pgformat.txt file.  As this
turned out to be easy I continued and finally came up with code to
decrypt and create PGP-2 data.  After I told the GNU towers that I
will take up the PGP replacement implementation I spent the rest of
the year replacing IDEA by Blowfish, RSA by Elgamal, implementing
streaming encryption, adding some key management and getting the code
into a reasonable shape.

There used to be a plan for a free version of Secure Shell called PSST
(later known as LSH) with a somewhat populated mailing lists
maintained by Martin Hamilton.  Martin was the so kind to setup a
mailing list for g10 too and announced it on that list.  This way we
got the first subscribers.  Eventually I made the first tarball, put
it up to ftp.guug.de, the FTP server of the German Unix User Group,
and wrote an announcement [5].

Right the next day Peter Gutmann offered to allow the use of his
random number code for systems without a /dev/random.  This eventually
helped a lot to make GnuPG portable to many platforms.  The next two
months were filled with code updates and a lengthly discussion on the
name; we finally settled for Anand Kumria's suggestion of GnuPG and
made the first release under this name (gnupg-0.2.8) on Feb 24 [6].
Just a few days later an experimental version with support for Windows
was released.  (That release also fixed an alignment problem on Alpha
boxes which was detected due to kernel log files filling up the hard
disk and an admin asking whether they really need to be backed up. ;-)

In July 1998 the first more or less OpenPGP draft compliant version
was released.  Matthew Skala had contributed Twofish code done cleanly
From scratch (Twofish was at that time a promising AES candidate and
suggested by Schneier as a Blowfish replacement; however we had some
copyright concerns with the reference code).  Michael Roth contributed
a Triple-DES implementation later the year and thus completed the
required set of OpenPGP algorithms.  Over the next year the usual
problems were solved, features discussed, complaints noticed and
support for gpg in various other software was introduced by their
respective authors.

Finally, on September 7, 1999 the current code was released as version
1.0.0 with the major update of including Mike Ashley's GNU Privacy
Handbook [7].  A year later the RSA patent was to expire on September
20; the patent holder placed the patent into the public domain 3 weeks
earlier and thus we could release 1.0.3 with RSA support already on
September 18.  One of the major obstacles on widespread use public
cryptography had gone (far too late of course).

Also in 1999 the German government decided that strong encryption will
not be regulated in any way and that its use is recommended for
everyone.  To publicly support this statement the Ministry of
Economics funded the porting of GnuPG and related software to
Microsoft Windows [8].  The US government was not keen to see that and
tried to urge the German government to revise the decision to allow
unregulated distribution of crypto software [9].  That did not work
out and to the end the USA had no other way than to weaken their own
export rules.

Although we still develop GnuPG using servers located in Europe the
new US export controls eventually allowed US hackers to contribute to
GnuPG development.  In 2001 David Shaw joined the project and since
then he is one of the most active GnuPG hackers and the co-maintainer.

It's now a long time since GnuPG could be managed as a fun project and
thus I now spend most of my professional life maintaining and extending
GnuPG.  In 2001 I founded g10 Code, a Free Software company for the
development and support of GnuPG and related software.  The most known
project is probably GnuPG-2 which started under the name NewPG as part
of the broader Aegypten project.  The main goal of Aegypten was to
provide support for S/MIME under GNU/Linux and integrate that cleanly
with other mail clients, most notably KMail.  Although having been
actively used since 2004, we released 2.0.0 only one years ago.

It was not that much fun writing X.509/CMS (commonly named S/MIME)
software compared to the elegant and very interoperable OpenPGP
protocol.  Having mastered that we meanwhile achieved to provide a
software which is really useful and works nicely with almost any other
S/MIME implementation.  It also turned out that we could port GnuPG-2
to Windows - despite my original claim that a modern POSIX platform
will be needed for GnuPG-2.  This development also showed that it is
viable to develop Free Software as a business.

With the new tools and from a user's perspective S/MIME and OpenPGP
will soon not make much of a difference anymore.  However I had to
smile when I today read a report on the last RSA Europe conference
where a quick poll during a talk showed that OpenPGP is the mostly
used encryption protocol.

Recall that GnuPG is just one tool; there are numerous other tools out
to solve related privacy problems.  Kudos to all who worked on writing
and deploying privacy tools over all these years!


Happy Hacking,

  Werner


[0] http://www/gnupg.org
[1] ftp://ftp.gnupg.org/gcrypt/historic/g10-0.0.0.tar.gz
[2] from pgpdoc2.txt: "Finally, if you want to turn PGP into a
    commercial product and make money selling it, then we must agree
    on a way for me to also make money on it. [...] Under no
    circumstances may PGP be distributed without the PGP
    documentation, including this PGP User's Guide."
[3] "valid" is meant in the sense the patent holders use it and does
    not imply that I regard patents on software a valid concept.  See
    http://www.fsfeurope.org/projects/swpat/background.en.html .
[4] http://www.dascon.de/IN-BT97/programm.html
[5] http://lists.gnupg.org/pipermail/gnupg-devel/1997-Decembe...
    There are just a few mails in December mainly discussing patent things.
[6] http://lists.gnupg.org/pipermail/gnupg-devel/1998-Februar...
[7] http://lists.gnupg.org/pipermail/gnupg-announce/1999q3/00...
[8] http://partners.nytimes.com/library/tech/99/11/cyber/arti...
[9] http://www.heise.de/tp/r4/artikel/5/5124/1.html


-- 
Die Gedanken sind frei.  Auschnahme regelt ein Bundeschgesetz.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 0:24 UTC (Fri) by jd (guest, #26381) [Link] (9 responses)

GnuPG is a fine piece of software. My main criticism is not of GnuPG itself but rather the lack of software that makes use of it transparently or semi-transparently. (You won't see secure e-mail, for example, until it is practical to send and receive secure e-mail from the majority of e-mail clients.)

My second criticism only marginally impacts GnuPG and really applies to all cryptographic software. The number of algorithms supported is often a tiny fraction of the number of algorithms out there, and for secret-key encryption, the number of encryption modes supported is a miniscule fraction of the number that exist.

Yes, there are going to be people who point out that many of the algorithms and modes have not undergone anything like the level of peer review as those in common use. To that, I would point out that those have been reviewed precisely because they are in common use, not the other way around.

There are also those who would argue that the increased choice would be more confusing than helpful. Perhaps, but the criteria used to select the AES algorithm was a mix of speed and security. With e-mail, speed is hardly a critical factor and therefore the balance used by NIST might not be appropriate for such cases.

For encryption modes, again, the balance has been speed vs. security, but the needs of e-mail are not general-purpose needs. I can see more people being interested in Authenticated Encryption Modes than in something that is merely fast. For sending images, I imagine that highly specialized encryption modes, such as 2DEM, that are designed to mangle information still extractable even from an encrypted image would again be highly appealing.

Finally, a few rotton tomatos at the users, at corporations and at lawmakers. The value of a technology increases both with use and with standing. Digital signatures and authenticated modes, if suitably strong, should be required on electronic documents wherever a regular signature would be required or expected on a paper document. (To me, this would include all official electronic documents.) Notary services should be able to "stamp" electronic documents produced in their presence by means of a very strong digital signature, giving it equal status to any paper document that had been notarized. (Although arguably it would be far harder to tamper with the electronic document.)

Official corporate e-mails would be included in "official electronic documents", in this. How often have we seen e-mails dragged into court, only for there to be arguments over whether they're genuine, complete, or some other such nonsense? Backups of all e-mails only get you so far, if you can't be sure if what is presented is what was stored, or that what was stored was what was written. It would also make it impossible to land up in debates over whether an e-mail was in an official capacity or not. An official signature means an official e-mail. No official signature means it can't be enforced as corporate policy.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 9:21 UTC (Fri) by bvdm (guest, #42755) [Link] (7 responses)

The decision to select Rijndael as the AES was certainly not based on a "mix" of criteria
between speed and security. The only consideration was complete resistance to all known
methods of cryptanalysis for the full 128-bit claimed strength. It was only amongst the final
round of peer reviewed candidates that speed was considered an advantage for final selection.

Any break in AES would represent an unprecedented advance in cryptanalytical theory. Given
that one wouldn't know what other ciphers would be susceptible to the new analytical attack,
there is really no point in not using AES. Given that 128 bits represents an unimaginably big
number, any break will probably not result in a practical loss of security.

Designing secure ciphers is a solved problem for the time being. It is much easier to crack
your box or for someone to break your knees than to break AES.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 17:03 UTC (Fri) by flewellyn (subscriber, #5047) [Link] (6 responses)

I'm sorry, I can't agree that cryptography is a solved problem, except in the purely theoretical sense: sure, we have a mathematically-proven unbreakable cipher, the One-Time Pad, but it's so hard to deploy and use correctly that its applications are extremely limited in the real world.

So in all truth, it's likely that at some point in the future, AES will be cracked. Mind you, I have no idea how; if I knew that, I would be either the world's greatest cryptanalyst or the world's greatest psychic. But given the history of cryptography and cryptanalysis, I feel confident enough in saying that one day, somehow, AES will be broken.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 20:32 UTC (Fri) by jd (guest, #26381) [Link] (1 responses)

Block cyphers use various methods of data mangling that produces a result that crudely approximates a totally random signal. The better the block cypher, the better the approximation. However, it isn't perfect and can never be perfect - even in theory. The encryption mode helps to improve the pseudo-randomness, but that too can never be perfect.

When (not if) a weakness is found in AES, it is pretty much guaranteed to be a weakness in the nature of the approximation. The 2DEM crowd demonstrated nicely in their initial paper how you could recover some information from encrypted images where there is a poor choice of encryption mode. I have no idea how much is recoverable, how much you can scrape the message for exposed data. Any information, though, must effectively reduce your key search space, with the obvious implication that sufficient information must reduce it to something you can search on a realistic timeframe.

2DEM mode

Posted Dec 29, 2007 5:51 UTC (Sat) by zooko (guest, #2589) [Link]

I just went and had a look at the 2DEM docs that they submitted to NIST.

As far as I could tell from a quick reading of the first couple of sections of their paper, they pointed out that ECB is very weak at confidentiality, and that CBC isn't parallelizable, and then proposed 2DEM mode. These two facts (ECB doesn't offer good confidentiality and CBC isn't parallelizable) were already well understood by other cryptographers. All of modes of operation described in SP 800-38 A (except of course ECB, which shouldn't have been included) offer good confidentiality, and CTR mode offers excellent parallelism. Some of the newfangled modes like OCB and GCM are also parallelizable.

So as far as I can tell, 2DEM mode doesn't offer anything over CTR mode.

Regards,

Zooko

GnuPG Celebrates 10 Years

Posted Dec 29, 2007 16:35 UTC (Sat) by Nelson (subscriber, #21712) [Link] (3 responses)

DES has never been "cracked." AES is at least as strong as DES, it has withstood all of the known attacks against DES.

It's hard to imagine it having a weakness that reduces its strength to something practical to process but I guess it's possible. You have to also understand that the ciphers that have been developed by actual cryptographers in the last 10 or so years that have been "cracked" the crack is almost never actually possible to do, it's just calculatably more efficient than brute force. It usually takes an intractable amount of processing power or storage to perform these "cracks" and the actual crack. Being paranoid, once a cipher has shown one of these weaknesses, it's usually abandoned and considered untrusted. I can't think of a legitimate cipher that has been developed in a long time that could actually be cracked in any practical manner, maybe FEAL or REDOC but those are pretty old.

GnuPG Celebrates 10 Years

Posted Dec 30, 2007 9:12 UTC (Sun) by flewellyn (subscriber, #5047) [Link] (2 responses)

DES has never been "cracked."

As a matter of fact, yes, it has.

You have to also understand that the ciphers that have been developed by actual cryptographers in the last 10 or so years that have been "cracked" the crack is almost never actually possible to do, it's just calculatably more efficient than brute force. It usually takes an intractable amount of processing power or storage to perform these "cracks" and the actual crack.

GnuPG Celebrates 10 Years

Posted Dec 30, 2007 17:13 UTC (Sun) by dmaxwell (guest, #14010) [Link]

See the above link. 22 hours using a distributed network is not infeasible. And this was in 1999, almost 9 years ago! Computers are much more powerful now, and massive parallel clusters are much more widespread. It's conceivable today that DES could be broken in a matter of hours.

The OP is correct. DES has not been cracked in a cryptoanalytic sense. It has been brute forced because trying every key in a 56 bit keyspace is now practical. Any true crack to a cypher algorithm reduces the keyspace enough to make a brute force search practical. DES is simply weak in the keyspace dept. The math behind it is good.

GnuPG Celebrates 10 Years

Posted Dec 30, 2007 19:30 UTC (Sun) by Nelson (subscriber, #21712) [Link]

Brute force isn't a "crack."

Do the math on AES then, if that's the best way to "crack" it then AES potentially be secure for centuries. And then there is EDE "Triple-AES" if we actually need something better.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 18:41 UTC (Fri) by raven667 (subscriber, #5198) [Link]

Official corporate e-mails would be included in "official electronic documents", in this. How often have we seen e-mails dragged into court, only for there to be arguments over whether they're genuine, complete, or some other such nonsense? Backups of all e-mails only get you so far, if you can't be sure if what is presented is what was stored, or that what was stored was what was written. It would also make it impossible to land up in debates over whether an e-mail was in an official capacity or not. An official signature means an official e-mail. No official signature means it can't be enforced as corporate policy.

Here are some reasons why some companies don't necessarily agree with your assessment.

That would seem to open up the company to all sorts of potential liability with very little benefit. Retaining email for long periods of time can open up your organization to legal fishing expeditions where your IT and legal team spends its time answering subpoenas and going through old backup tapes rather than their actual work. This can be especially onerous for an organization like an ISP which is storing and processing data on behalf of third parties, you might end up in the middle of a lawsuit that doesn't even involve you.

One of the answers to this problem is aggressive data deletion policies, as soon as the data isn't needed purge it. It's easy to respond to discovery requests when you can show that you don't have the data in question any more. It is also more secure in that if your system is compromised the attackers can't make off with customer data you don't have anymore.

The other issue is that signing documents can have other implications, especially if you make any claims to non-repudiation. Any offhand comment by an employee to a customer can become legally binding in some locations. Non-repudiation claims are especially a problem because someone could install a trojan on a workstation or simply leave their computer unlocked and unattended allowing others to sign or encrypt messages as them. Poor private key management is also standard practice at most organizations. Problems such as this can be time consuming and expensive to clear up and are just liability for the company.

In the specific case of PGP style key management escrow is an issue. In the common use case every user generates their own private key which is not necessarily shared with the company officers. If an employee moves on to another job, the company may lose access to any emails and documents they've received or encrypted for themselves. Of course this risk exists in any event, any person can install GPG and digitally shred their system and the risk can be migrated if the GPG deployment is thought through and managed properly but there are additional risks in jumping into proper forethought of these and other issues.

I hope I'm not too much of a killjoy but I wanted to provide some counterbalancing information as to why this can be difficult or perceived to be difficult at some companies. These are concerns that I've heard when proposing a similar email encryption deployment.

GnuPG Celebrates 10 Years

Posted Dec 28, 2007 0:29 UTC (Fri) by Kluge (subscriber, #2881) [Link]

Thank you Werner!

Signature

Posted Dec 28, 2007 16:17 UTC (Fri) by mmutz (guest, #5642) [Link]

For those of you not well-versed in Schwäbisch, the translation of the signature reads:

Thoughts are free. Exceptions are governed by federal law.

It mimicks a formulation from the German Constitution: Das Nähere regelt ein Bundesgesetz (details are governed by federal law), which is often the last sentence in paragraphs that make up the Constitution.