[Cryptography] Why human-readable IDs (was Re: Email and IM are ideal candidates for mix networks)

[Christian Huitema]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is exactly the problem that Kim Cameron and I tried to solve by developing what we called "call signs." The idea is to compress the hash of the public by solving a puzzle: find the arbitrary "salt" so that the hash of the salt and the public key ends with a large enough number of zeroes. (Or 1, or any arbitrary patterns.) Publish then the "call sign" as a  fraction of the hash, say the leading bits, that is short enough to be memorized, or at least written on a napkin. Of course, you have to verify that N bits of call signs + M zeroes is long enough to provide a strong hash.

The birthday paradox tells us that collisions will happen after 2^(N/2) users in the same space. We assumed that the practical length was at most 10 characters, 50 bits, which means collisions would happen after a few million users. We mitigated that by adding a human identifier in the mix, making the call sign something like "Perry.A32-H45Z-ZE0." Now the collisions only happen in the space of "all people named Perry", which is much smaller than "everybody."

Of course, this was a Microsoft project, which Microsoft did not choose to develop. And it was patented...

- -----Original Message-----
From: cryptography-bounces+huitema=huitema.net at metzdowd.com [mailto:cryptography-bounces+huitema=huitema.net at metzdowd.com] On Behalf Of Perry E. Metzger
Sent: Wednesday, August 28, 2013 5:53 AM
To: Jerry Leichter
Cc: Wendy M. Grossman; cryptography at metzdowd.com
Subject: [Cryptography] Why human-readable IDs (was Re: Email and IM are ideal candidates for mix networks)

On Tue, 27 Aug 2013 23:52:23 -0400 Jerry Leichter <leichter at lrw.com>
wrote:
> But none of that matters much any more.  "Publication" is usually
> on-line, so contact addresses can be arbitrary links.  When we meet
> in person, we can exchange large numbers of bits between our
> smartphones.  Hell, even a business card can easily have a QR code
> on the back.

Just as an FYI, this describes exactly zero of the times that I've
gotten people's email or jabber addresses in recent years. Very
typically people have written them down for me, told them to me over
the phone, or the equivalent. I've had to read mine over the phone a
fair bit, too.

I wouldn't know how to trust publication online in the first
place.

"Perry Metzger's email is <big string>"
"How do I know that's true?"
"Because it is encrypted in <big string>"
"What if that's a lie? I've never heard Perry utter <big string>"
"What, you don't trust me? No dishonest person has a web server!"

If someone tells me they're foo at example.com, and I have a trustworthy
way of mapping foo at example.com into a long lived key (see my first
message in this sequence of three that triggered this discussion),
life is a lot better. I think this alone is a lot of why X.500 died
so fast compared to SMTP -- the addresses were simply untenable, and
they were at least in theory human readable.

Anyway, I've already started implementing my proposed solution to
that part of the problem. There is still a need for a distributed
database to handle the lookup load, though, and one that is not the
DNS.

Perry
- -- 
Perry E. Metzger		perry at piermont.com
_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.20 (MingW32)
Comment: Using gpg4o v3.1.107.3564 - http://www.gpg4o.de/
Charset: utf-8

iQEcBAEBAgAGBQJSHgr0AAoJELba05IUOHVQdwgH/2bhJZYagObK1yzl27r9w+BP
ests/CMmUOVxnAnICY0MeoH5/GLbyNX2u5ZKGh32DikoTCFEHpMItgxpT8hQpEtD
81j5NV4X2qRaYc183C0HGxpJe2Cq2vQNAVGTJbJAV08dDZuu2W/IxuPsBjF0U3p+
yxham0qSnbngYSNBi31WXg4X08EV/Z3H5NoTsWkiHfSs+LLcyT9uNXwi7IxP4tmU
filmYGKBIdw16A9wGuqAy/V7edFG4tqgNtVdKH+yAYDGwY7NW+NYzOQCn8HOMQ4w
sxXMDuUEg+KQ1PvtfIgk3tfTSEb45Rsiu9VH2Vir9PKOzzCzQIneJvG2V8nCDdI=
=AtVw
-----END PGP SIGNATURE-----