Scott Robinson (quadhome) wrote,
Scott Robinson

Human Key Exchange

I walked over to EME this evening with the ostensible purpose to work on the Byte Brothers contract. But, I forgot to pack the tester in my backpack. D'oh!

Instead, I updated my todo list and started working on some pending homework assignments. After working on that for a while, my mind wandered off to more interesting subjects. I was reading about the brokenness of current secure hashes when a fellow student Devin walked up and asked what I was up to? We started talking, and later on instant messaging I presented him with a problem: (I realize there are inaccuracies in what I said.)

quadhome: At the moment, anonymous key exchange is impossible.
quadhome: Therefore, before any two people can securely exchange messages, there must be a shared piece of information.
quadhome: Right now, there are three main methods for sharing that piece of information on the Internet.
quadhome: 1. Ad-hoc.
quadhome: That is, the information is shared as a part of an initial key-exchange and remembered by each side.
quadhome: Any future conversations can be thus known to be with the same person.
quadhome: However, if there is a Mallory in that initial conversation, then all future ones are breached.
quadhome: SSH works like this.
quadhome: 2. Trusted Authorities.
quadhome: That is, there is a Trent somewhere who both Alice and Bob know and trust.
quadhome: Therefore, if Alice asks Trent if Bob is who he says he is, and Bob does the same.
quadhome: And Trent answers yes in each situation, then Alice and Bob "know" they're talking to each other.
quadhome: Mallory cannot interfere.
quadhome: (Solve this question while I describe the next method: what is the meta-flaw in that scheme?)
quadhome: 3. Web-of-trust.
quadhome: BTW, SSL, TLS, and SMIME use #2.
quadhome: In WOT, Alice and Bob know each other already.
quadhome: They've met IRL and verified each others identity and association to keys.
quadhome: Also, Bob knows Charlie, he has authenticated him as well.
quadhome: So, when Alice wants to send a message to Charlie, she can see that Bob already knows Charlie and therefore she can trust that Charlie is who he says he is.
quadhome: But, since she hasn't met Charlie yet, that means she doesn't "trust" him as much.
quadhome: And therefore, if she meets someone else who Charlie also knows, she's less certain that person is who they say they are.
quadhome: But, let's say Bob knows Charlie, Devin, and Fred.
quadhome: And Alice has met each of them too.
quadhome: (and trusts them only marginally)
quadhome: If all three of those guys knows someone new, say Gina, then she can trust that Gina is who she says she is.
quadhome: Because three of the people she marginally trust all trust Gina.
quadhome: PGP and, to a point, FOAF work this way.
quadhome: (When FOAF has an encryption layer.)
quadhome: Ok, did you figure out the meta-problem for #2?
Devin: could it be that I am asking for the wrong bob?
quadhome: Ha, good one!
quadhome: That is one of the meta-problems, but not the one I was going to point out in the current scope.
quadhome: Damn good thought though. ;-)
quadhome: The one I was keying (no pun intended) into is that, you have to trust Trent right?
quadhome: So, if you can't work out a way to trust Bob, how are you working out a way to trust Trent?
quadhome: Or, put another way, if you have a way to trust Trent, why not apply that way to Bob?
quadhome: Realistically, there are situations that asymmetric issue is real. For example, I want to talk to someone in a country I can't go to.
quadhome: I can, however, meet someone here in the States that can go to that country.
quadhome: I trust them, they go there and confirm with whoever I want to talk to.
quadhome: That person who can go is Trent.
quadhome: So, it's not necessarily a bad idea, but all things being equal (and we so love equality in math), the Trent problem is just a recursion of the initial pre-shared information/trust problem.
quadhome: So, in summary, we have three ways to trust:
quadhome: 1. Ad-hoc: assume they're who they say they are, and verify from then on.
2. Trusted authority: ask someone who has met everyone.
3. Web-of-trust: trust our friends.
quadhome: Ok, here is the social jump:
quadhome: So, I stated those so I cold easily relate to reality. We perform those exact same actions in how we trust people IRL.
quadhome: That is, the fundamental problem isn't one of secret sharing, it's of trusting that information.
quadhome: In reality, if someone tells me something, I tend to trust it until disproved. (1) Unless, however, that person "looks" shady.
Devin: knowing that the information is actually true
quadhome: So, I'm applying heuristics there.
quadhome: Well, what is "truth"?
quadhome: So, in general, you talk of trust.
Devin: well what if I tell you that my sister is 3 years younger than I am
quadhome: (And then we get to, how do you rate trust?)
quadhome: I would believe you. However, I wouldn't believe it as much as I believe my younger sister is two years younger.
Devin: how can we verify this information without involving my sister
quadhome: I would rate is with less confidence.
quadhome: Ha, actually, how can we verify this without involving your parents?
quadhome: Since, realistically, three years of separation you parents could have been lying for a while.
Devin: without involving anyone else
quadhome: Who knows why?
quadhome: So, without this devolving into a trust metric discussion (also a great topic), let me present the problem:
Devin: alright
quadhome: (Ask me about trust metrics sometime, also a great problem. Or, just read about them.)
quadhome: So, we also trust the government too as a trusted authority.
Devin: sometimes
quadhome: You trust in your mail being delivered, maps and roads are being produced, and that your taxes aren't being pissed away, etc. etc..
quadhome: Sometimes, yes.
quadhome: That's trust metrics again.
quadhome: I'm not saying how much we trust these entities, just that we do.
quadhome: And finally, I meet random people and I trust them.
quadhome: And when I meet someone through a good friend of mine, I trust them too.
quadhome: Though, usually, not as much.
Devin: random trust metric
Devin: I like that
quadhome: So, those are applications of #1, #2, and #3, yes?
Devin: sure sure
quadhome: Those trust relationships "work" in reality because you can visualize the reliability.
quadhome: That is, there is no anonymous key exchange in reality.
quadhome: If I see a person on the street, I know it's them.
quadhome: (generally)
quadhome: When I interact with the government, there are giant buildings and fun stuff.
quadhome: So I know I'm dealing with the government, or at least someone powerful enough to might as well be a government for me.
Devin: because you've seen them before
quadhome: And when my friend introduces me, it's because we're all sitting around at a bar.
quadhome: Or what have you.
Devin: non-anonymous key exchange
quadhome: The point is, that identity exchange is visualized.
Devin: sure
quadhome: I can recognize faces.
quadhome: However, it doesn't quite work the same way with keys.
quadhome: For example, consider when we signed each others keys.
quadhome: How much of my fingerprint did you look at?
Devin: first and last
quadhome: Right. So, that secure hash of X bits was suddenly truncated.
quadhome: To, I believe, 32 bits.
quadhome: If there had been a serious attack on us, do you realistically think it would have been in the middle?
quadhome: or rather, would have been in the ends?
Devin: maybe a combination
quadhome: So, the fact is, even when two responsible guys try to identify each other, they don't.
quadhome: Because it's too hard!
quadhome: That's a social problem.
quadhome: In fact, a rather interesting social problem in that proper key exchange is hard.
quadhome: If I want a known Trent, making sure I'm actually talking to him is hard too.
quadhome: So, to come to the point, here is the problem:
quadhome: How can you visualize a reasonable key-space (say, 256-bits) in such a way that each possibility is recognizably different?
Devin: sound
quadhome: Oh?
Devin: assign a tone to the different bit values
Devin: and play them concurrently
Devin: if there is a weird noise
Devin: something is different
Devin: it would make a little song
Devin: together
quadhome: If I played a hundred sets of 256 notes, would you be able to tell each apart?
quadhome: Then played them again, randomly, would you be able to remember which was which?
Devin: in a string of noise
Devin: this is for fingerprint identification right?
quadhome: The problem isn't comparing any two set of 256 bits. It's comparing them all.
Devin: to another set of 256 bits
quadhome: It's for all of them, here is why:
quadhome: Assuming a Mallory with infinite selection, I have a fingerprint "ABC123XYZ"
quadhome: And I want to show it to you
quadhome: Mallory can select for one part, the least noticeable, and will produce a fingerprint of:
quadhome: "ABCl23XYZ"
quadhome: (Assume the ABC and XYZ are the ends of the key, and 123 vs. l23 are somewhere in the middle.)
quadhome: So, for any point in the key-space, they must all be unique and recognizably so.
quadhome: And yet, succinct enough that a human can differentiate them without losing patience.
Devin: So what am I comparing your key to?
Devin: you show it to me, and I assume its from you
Devin: and this mallory can intercept it and change it to make it appear similar
quadhome: Yup.
Devin: tricking me
Devin: into accepting his key
Devin: instead of your key
Devin: right?
quadhome: Yup.
quadhome: For example, consider this slightly more realistic case:
quadhome: Instead of public and private keys, we're exchanging one-time keys.
quadhome: On the order of multi-gigabytes.
quadhome: But we're dissidents and being carefully monitored.
quadhome: (That's why we're using one-time keys)
quadhome: (pads, actually)
Devin: excellent
quadhome: So, I can transfer you all these gigs of data over the Internet.
quadhome: It's all cleverly hidden in the porn you have been downloading.
Devin: haha
Devin: I knew it
quadhome: But, I can't just walk up to you in reality and hand you a hard drive.
Devin: thats why it was so grainy
quadhome: The gestapo would know.
quadhome: Arrest us both right there, and we'd be fucked.
Devin: what If I just guessed the pad?
quadhome: Ha.
Devin: you think I could?
quadhome: Kinda computationally infeasible.
quadhome: (Side note: if you can do that, the gestapo would definitely lock you up and take all your notes. They would instantly be able to break every algorithm in the world.)
quadhome: So, let's say I can, however, give you a slip of paper.
quadhome: Or can publish something in a newspaper
quadhome: Or have a radio signal transmit something.
quadhome: (Feeling is hard, maybe make a statue?)
Devin: but no pre-agreeing
quadhome: (Or plastic surgerize some woman's breasts, that you later "confirm" against.)
quadhome: (hahahahaha.)
quadhome: (I'm definitely digressing here.)
Devin: I like that one
Devin: hide it in the silicone
Devin: they'd never find it there
quadhome: Anyway, I can share a small piece of information to you that you immediately recognize was the _exact_ same as the fingerprint of all that data you were sent.
quadhome: So you know that it was I who sent you the data, and not anyone else.
quadhome: And therefore, it was trustworthy.
quadhome: Here's another scenario:
quadhome: Two people are using MyCryptoSpace.
quadhome: They want to friend each other, but in order to do that must meet in reality. (That's why it's so popular)
Devin: I can imagine
quadhome: They each print off a sheet of paper with the fingerprint expressed in some way that a human can recognize.
quadhome: Swap papers, and make-out a little.
quadhome: They go home, and confirm the contents against what's on their computer screen.
quadhome: So now they know each other is who they say they are on MyCryptoSpace.
quadhome: And now they can "marginally" trust each others friends, and have a bunch more people they can make out with.
Devin: well here
quadhome: Math "guarantees" HIV free!
Devin: we publish our keys to the key-server right?
quadhome: Yup.
quadhome: Where they may or may not be modified.
quadhome: And then the other person downloads that key.
quadhome: Which may or may not be a modified version.
Devin: well well
quadhome: Then we compare fingerprints.
quadhome: And are only checking the ends.
Devin: That's where the sound comes in
Devin: during the checking
quadhome: So that means, instead of having to generate 2^256 different keys to crack us...
quadhome: Instead, the gestapo has to generate 2^32 keys.
quadhome: Ok.
Devin: so when we compare keys, we just listen to the music
Devin: and if its wrong
quadhome: Describe to me, in a little more detail, how you are generating this music.
Devin: then the keys are wrong
Devin: generate tones for characters
quadhome: What kind of tones?
quadhome: How many characters.
quadhome: Please be a little more specific.
Devin: Unicode characters
quadhome: I'm not trying to be an asshole, just asking. ;-)
Devin: sure sure
quadhome: Ok, so each character in the fingerprint, that is a combination of 16 characters, is mapped to a tone.
quadhome: So, for each character, there are 16 notes.
quadhome: Sound ok?
Devin: perhaps a form of combination tone based on the key
Devin: then play it against the supposed key
quadhome: What do you mean?
Devin: if the tones were different, then there would be a thingy
quadhome: I thought you were saying, 16 notes per character. The fingerprint has...
quadhome: Let me think.
Devin: what happens when you get two tones right next to each other
quadhome: 16 sets.
Devin: a phantom tone
quadhome: So, 16 sets of 16 tone notes, right?
Devin: that vibrates at the difference between the frequencies
quadhome: Right.
Devin: so we could hear that
quadhome: Ok.
Devin: the difference
quadhome: So you can compress even further.
Devin: and know that the keys were not the same
Devin: perhaps
quadhome: It would be 8 sets of 16 tones.
quadhome: Shorter tune.
quadhome: (Personally, I'd rather leave those phantom notes. More redundancy.)
Devin: we can hear from 100 Hz to 22 kHz I think
quadhome: Yup.
Devin: so there exist lots of frequencies
quadhome: Well, most people. But let's assume old people aren't allowed on MyCryptoSpace.
quadhome: No one wants to make out with old people.
Devin: that's true
quadhome: The reason I picked notes is that they're well known.
quadhome: but yeah, any frequency would do.
Devin: well hearing that phantom tone would be more direct if there were some difference between each frequency used
quadhome: So you play those, and you think people would be able to determine a difference?
Devin: like 5 Hz
Devin: which would work out to five beats per second
Devin: I think
Devin: I think they might
quadhome: Ok, this is a nice hypothesis.
quadhome: Shall we test it?
Devin: It would be easier
Devin: and people can't stop using their ears voluntarily
Devin: we should test it

So, we tested it. We also worked on several other theories, including encoding the information visually.

I think the best result from it was realizing that since the problem is a human one, there is more than the single solution of encoding 256 bits of information into something easily differentiable. There is process solution in breaking up the data. Instead of simply splatting 256 bits, instead you could break it up into four segments of 64 bits and compare each of those in series.

Another neat process solution is representing segments of a key as disharmonious tones, and playing two fingerprints represented this way simultaneously. If our ear heard any disharmony, then we would know the keys mismatched.

Solving this problem would open up a lot of interesting social technologies on the Internet. Anyone want to take a shot?

Tags: pretentious
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.