Commons license.

Your support will help MIT OpenCourseWare

continue to offer high-quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

TADGE DRYJA: Today, I'm going to talk

about signatures and all sorts of different signature

kind of things.

In the problem set, you're working with signatures,

but you're working with hash-based signatures, which

are not actually used in bitcoin at all.

But we'll talk about those.

OK.

So if you've gotten through the homework,

there's lamport signatures, right?

These are hash-based signatures.

And they use hash functions.

So it's fairly straightforward.

You can understand them.

There's nothing super crazy going on.

The code is fairly compact.

So that's cool.

What are some disadvantages of these lamport signatures?

Does anyone-- yeah?

AUDIENCE: You can only use it once.

TADGE DRYJA: Yeah.

OK.

So plus.

This is hashes.

That's cool.

One-time use.

Other possible disadvantages of them relative to other systems,

if you're aware.

Another is they're kind of huge, kind of big, right?

You can deal with it.

But if you were looking in the forge,

or that file with the signatures,

it's like, what, 8K for a signature--

8 kilobytes-- kind of big.

Keys are 16 kilobytes--

kind of annoying.

Private keys are also 16 kilobytes.

So yes, sig 8K, 16K priv/pub key.

So that's some disadvantages.

So since I don't have slides, I'm

gonna make this more fun and interactive.

What are some solutions for these problems?

So we can actually mitigate/solve

both of these things to a pretty good extent.

So how about the first one, one-time use?

What would be a fairly obvious way

to mitigate the one-time use problem?

And don't think the answer is too stupid.

It may be a fairly stupid answer, and it might work.

So yeah?

AUDIENCE: Not actually revealing pieces of your private key?

Instead, reveal something else.

TADGE DRYJA: There's probably some clever way.

But that might be too clever.

Something really simple for, OK, I can only use a key once.

How can I use a "key," quote unquote, more than once?

Yeah?

AUDIENCE: Make another one.

TADGE DRYJA: Yeah.

You can make another key.

So you could say, well, I've got this 16 kilobyte public key.

Well, I'm going to make a 32 kilobyte public key.

And it's just two public keys stuck together.

And now, when I make a signature,

I just put an extra bit in the front.

And I say, well, this signature is using key 0

or this signature is using key 1,

and it's got the whole signature after.

And then you look through this 32 kilobyte public key,

and you say, OK, well, it starts with a zero,

so that means it's using the first key, the first subkey

in this 32 byte public key block.

And in this case, it's using one,

so that means it's using the latter subkey.

So that would work.

That would let you use your public key twice,

at the cost of doubling your public key size, which

is not really great, right?

And it's not very efficient.

But it does sort of work.

OK.

Any clever ways to do it more efficiently?

Or wait.

So OK, also, I'll give you sort of a hint.

In this case, let's say this is pub sub 0 and pub sub 1, right?

And then, your 32 byte pubkey is just them

concatenated together, right--

pub0, pub1.

What would happen to the private keys in this case, right?

How would private keys work here?

Same expansion of size, I guess.

Can anyone think of a way to mitigate the expansion of size

of private keys in this case?

So the private keys are the preimages here, right?

They lead into these public key blocks.

So you could just say, OK, well, I

have twice the size private key leading into twice the size

public key.

Could you do that more efficiently?

Yeah?

AUDIENCE: Could you just hash the private key

so that you have two hashes instead of one?

TADGE DRYJA: Yes.

So let's say you have this 16k block,

and you want this to turn into two public key.

So that's the basic good way to do it.

And it sort of turns in like that.

How exactly-- what's the way you do that?

AUDIENCE: You can keep the same private key as before

and just add something like zero or one to indicate--

TADGE DRYJA: Yeah.

So this is a hash function, right?

And so before, we just said, OK, hash of this is block 0,

this is block 1, this is block 2.

So the idea of pub--

let's see.

Is this visible?

This might be too small, right?

AUDIENCE: Yes.

TADGE DRYJA: Yes, OK.

Let me make this bigger.

Sorry.

OK.

So in these diagrams, you've got your private key right now.

And it's in these big blocks.

And there's 256 of them, but let's keep it small.

And the idea is these are 32 byte blocks with random numbers

in it.

And then you hash it to get your public key.

So we say, OK, pub2--

and this is public, this is private, and, let's say,

secret--

pub2 is just the hash of secret2, right?

But yeah.

What we could do is we could sort of have two different hash

functions.

And then a real simple way to make

a whole bunch of different hash functions

is we define, OK, well hash0 is defined

as the hash function of whatever your input x is concatenated

with the number 0.

And then hash1, we define as just x comma 1 and so on.

And this is actually secure.

You could do this.

Any questions or possible objections?

AUDIENCE: I was thinking that if someone knew the hash function

you're using, wouldn't they only define

x because they know that it won't help with [INAUDIBLE] x.

[INAUDIBLE]

TADGE DRYJA: Yes.

Yes.

So there's no real entropy or secrets in this 0 and 1.

But it's purely riding on x, right?

But the idea is, well, if I do this,

and I say, OK, well pub2 is the hash

of secret2 concatenated with 0, yeah, if you know secret2,

you can go back.

Because 0 is obvious.

But the idea is if you don't know secret2, the fact that you

know the last byte of the hash input doesn't really help you.

Because there's all this data that you don't know.

And so you're not going to be able to find a preimage.

You're like, OK, I know the preimage

to public2 ends with a 0 byte.

What are the other 32 bytes that come before that?

You still can't go back to make a preimage.

AUDIENCE: But it feels like there's some sort of--

what's the word-- you'd make a similar statement saying, oh,

if the last byte is not important,

then the second-to-last byte is not important, either, right?

TADGE DRYJA: So the attack is I've got pub2,

which is a 32 byte hash output.

I want to find what this thing is.

Now, I do know what the last byte is, right?

It's going to be, let's say, 33 bytes,

and the last byte is a 0.

And this is going to be some random numbers

all the way back.

So I have some insight into what the preimage is.

I know the last byte is a 0.

But that doesn't help because I don't

know all the bytes before that.

So I can't really do--

I can't sign because I need to be able to reveal

all these things.

And the way the hash functions, if it's a good hash

function, the fact that you know some part of the preimage

shouldn't give you insight into the other parts

of the preimage.

Because it looks really random.

And adding stuff to the end here shouldn't reveal anything.

There are hash functions where this can be dangerous,

and you can consider those like broken hash functions, where

if I concatenate a lot of known data at the end,

it might give me properties of the public key that I can find.

[INAUDIBLE],, as far as we know, it works fine.

Most of the hash functions work fine this way.

So yeah, you can do this.

And then you can say, OK, well, I'm

going to use hash function 0 to make pubkey 0, right?

This is pubkey 0.

And if I use hash function 1, I make pubkey 1.

Now I have a 16 kilobyte-- let me erase this--

so now what I can do is I can say, OK, well,

I have a 16 kilobyte secret key, private key,

but I have a 32 kilobyte public key

that I can use twice that has two subkeys

so I don't have to store as much of my private key data.

So that's cool.

That makes it quite a bit more efficient.

Does anyone have an idea of how to get it even more efficient

for private key storage?

You can actually get it very efficient

using this kind of idea.

Any ideas?

Yeah.

Well, you--

So some hints.

This is pretty useful, right?

The idea is, well, even if you know

what the sort of suffix of all these things

are, if you don't know x, you're not

going to be able to find the preimage, right?

So maybe add some more stuff here.

Any idea?

Oh, yeah?

AUDIENCE: Could you hash the index?

TADGE DRYJA: Right.

Right.

So instead of just saying 0 and 1,

we can say here, well, why not just have one chunk?

And there's one chunk, and it's got random number x.

Well, this is hash x comma 0.

This is hash x comma 1.

This is hash x comma 2.

OK.

So yeah.

So what you can do is you can--

this was before, right, where I said, OK, yeah,

but this is basically how to do a 32 byte private key where

your private key is actually quite small,

and you just derive all of the public keys

by adding numbers at the end, concatenating them

into your hash.

And now you're like, OK, cool.

I have a 32 byte private key, and I

can make enormous public keys from them,

and it's still secure, right?

Because I can add whatever number I want here.

And I can do this a million times,

and no one will be able to find the preimage, even though I'm