The Side Channel

Zophikel

1:06 AM

Does anyone here have a bitcoin mining farm ?

Meta Crypto SE

2:52 AM

0

Q: Does anyone know about this supposed reddit AMA?

The link to a post on reddit r/math. I would very much like to hunt down a NSA crypto stack handle.

discussion

Tom

9:26 AM

@e-sushi yes, you're probably right about getting what you pay for -- most of the time! I've uploaded the PDF of the review paper to the first upload site I could find: docdro.id/WZcw7uq I'd be very happy if you or anyone else looks at it!

If anyone would like to review my hash-based signature scheme here's the link: docdro.id/WZcw7uq I'd be very interested to hear what you think.

CurveEnthusiast

10:04 AM

@SEJPM Well, yeah. What's a few months compared to the years you would want your scheme to be around before people start to consider using it?

Although that's probably not the use-case here, and my comment was mostly a joke!

MickLH

9:25 PM

@Zophikel Does an efficient algorithm for obtaining SHA256 preimages count?

@Tom I already had and analysed this idea to use bloom filters to compress Lamport keys. You can have security or efficiency from it but not both.

Tom

do you have a paper to explain your reasoning?

MickLH

A set of bloom filter coefficients smaller than the list of hashes has too many false positives to maintain the security parameter

(and that's not considering attacks exploiting the specific structure at all yet)

Tom

right (assuming that argument is correct), but this scheme uses 8 different hashes so the probability of false positive is 0.0001^8

it's not a derivative of lamport

MickLH

Well to be honest without clear algorithm or mathematical notation, I can't be 100% sure what you're exactly explaining.

But I did put a large amount of time into seeing if there was any way to force digital signatures out of hash functions and bloom filters / hyperloglogs

and I had a few strong negative results

Tom

well the algorithm is very clear in the paper

MickLH

9:39 PM

Maybe to you...

Can you explain why it's not a derivative of Lamport?

Because from the paper I got the idea that it was Lamport signatures compressed by Bloom filters

I know what I'm saying is tempting to dismiss, but I sure hope you don't write me off as "too dumb to get it."

Tom

absolutely not, I'm guessing that I need to work/help you understand it

the signature is a subset of the (many) 'private hashes' generated from the private key. the bloom filters are used in verification: we hash each private hash and check against bloomfilters

the diagram in the paper shows the general configuration

MickLH

Lets get nitty-gritty, how would a signature exactly be verified?

(ie. Is there a separate hash function used to assign the bloom filter taps? Does every filter tap depend on every hash bit? etc.)

Tom

it depends how it's implemented for how it's verified -- as is explained throughout the paper (which is because I refine the implementation through the paper to achieve the performance we want). but partitions of the public hashes (hashed private hashes) are added to the same bloom filter. when the signature is verified we check that the private hash hashes to something that gets a positive from the expected bloom filter

(the detail is in the paper)

MickLH

I read the paper. I much prefer algorithmic and mathematical notation as it's my natural thought space. Classical human languages are horribly tedious and ambiguous to me.

If you insist that I infer from the paper, then I've got:

Verify(x, m) = BloomTest(x) && TomTest(x, m)

I'm a horribly impatient person. This scheme can be described in less than one paragraph.

If I really must infer, then I'll take the most likely guess and respond to that: In that case one could reduce the problem of set membership estimation to your scheme.

In that context, your scheme implies a method to beat the optimal Bloom filter

Tom

9:59 PM

let me try to create a pseudo-code here

MickLH

thank you, hope it's not too much hassle. I just like to be really exact

Tom

private key = crypto_hash(private data)

MickLH

btw, if you use shift+enter, you can enable multi-line mode and then a "format code" button will appear to the right of send

Tom

ok thanks

MickLH

hey @EllaRose, sorry I didn't read your message on keybase yet, it keeps saying "Securing..." forever when I try to open it -_-

it really hates my computer lol

Ella Rose

10:03 PM

I had that bug too. I restarted and it went away. I think their app is in alpha or at least early deployment

MickLH

oh ok I'll restart that machine

I uninstalled and reinstalled... but didn't restart lmao

Tom

private hashes = set[i = 0->4194304] {hash(private key concatenated with i)}
public hashes = set[i = 0->4194304] {hash(private hash i from private hashes)}
sign(m) = let h=hash(m); then 8 times: let j = 4 bytes of h; add to signature nearest unused private hash to index j mod 4194304

whoops. forgot fixed font

private hashes = set[i = 0->4194304] {hash(private key concatenated with i)}
public hashes = set[i = 0->4194304] {hash(private hash i from private hashes)}
sign(m) = let h=hash(m); then 8 times: let j = 4 bytes of h; add to signature nearest unused private hash to index j mod 4194304

from public hashes partition into 1024 subsets; create bloom filter for each, and add the subset to the bloom filter as hash(public hash concatenated with its index)
verify(signature,message) = find the expected signature for m; for each private hash in signature, get public hash by hash(private hash), and check in corresponding bloom filter for positive; if all respond positive, return true, else return false

MickLH

@Tom what is to stop me from providing just any random data that fits the expectation and saying it's a private hash?

Tom

because the signature must conform to the message

MickLH

10:18 PM

Given a fixed message, how many possible signatures conform to it?

@EllaRose I got your message now and replied

Tom

1

MickLH

@Tom Then I could trivially forge the signature by providing the only "private hash" that matches the expectation

Tom

because the signature algorithm always picks the same set of private hashes in the same order

MickLH

I don't mean by your signing algorithm

I mean in theoretical possibility

Tom

you can forge a signature, but it wouldn't get hits in the bloom filters

MickLH

10:21 PM

So the verify can not distinguish between a random chunk of data, and a real private hash, other than the bloom filters correct?

Tom

well it will know it's not a real private hash when it hashes it and can't find it in the filter

MickLH

So in order to forge successfully, we must find a (possibly false) positive in the total combined bloom filter?

Tom

yes

MickLH

Ok to sketch what could be made rigorous, we can view the N bloom filters each with K taps, as a single composite filter with N*K taps and where the bloom tap hashes produce a biased output distribution

Because of this biased output distribution, we have strictly less than or equal information content to an unbiased bloom filter

Tom

(btw listening to your music -- pretty good!)

MickLH

10:33 PM

If we assume an optimal bloom filter configuration and a fixed number of items in the filter, we have a false positive rate proportional to the number of filter bits

"proportional" by some function lol, I should just say dependent, either way it's just a sketch

(sorry, trying to obtain a hard number)

Tom

listening to 'steroids' so all's well

MickLH

lol I'm glad you like them, it's just some fun and games nothing serious

Tom

it's fun, reminds me of geforce the game from N64

MickLH

ok so I'll assume the total number of bloom taps is given by $k=\frac{m}{n}\log(2)$ because it minimizes the false positive rate

and I derived it with a mild assumption but someone showed you don't even need that assumption iirc, the false positive rate should be $(1-(1-\frac{1}{m})^{kn})^k$

($m$ is the number of bloom filter bits, and $n$ is the number of private hashes inserted into the filter)

Tom

10:52 PM

I should definitely say that the hash that's checked in the filter is hash(hash(private hash) concatenated with expected index)

... I was thinking I should have put that, but I didn't expect you to get that far so quickly

MickLH

By setting the false positive rate equal to $2^{-s}$ and using a (standard) approximation, you can find that with an optimal choice of $k$ and arbitrary choices of $n$ and $s$, you have determined $m$ as approximately $m=\frac{n s}{\log(2)}$

Tom

the setup of the bloomfilters is whatever gives 0.0001 false positive probability

MickLH

and to be honest I'm afraid that might be too optimistic, I'm assuming that every bloom filter is optimal and combined optimally

so idealizing away the fact that the separate bloom filters can't make use of each other's data in making their guess

Tom

I'm not sure why there's so much analysis when there's 8 independent attempts to get a positive from a 0.0001 false positive filter

MickLH

That's sortof beside the point, I'm not arguing against or analyzing that piece of the puzzle.

I'm saying that you can't fit 8 of such filters in such a small space

At least, not with that many items in them

Tom

11:04 PM

they are fit in whatever space is needed

MickLH

When you reduce the storage space of a bloom filter, you increase the false positive probability

Tom

there's no constraints on space in this version

MickLH

What I showed above is that the storage space is asymptotically equal to Lamport signatures

Tom

what I've outlined is before optimisations to allow you to check the security

MickLH

Regardless of any specifics, just based on the concept of using a bloom filter to compress a test against a list of hashes

Tom

11:07 PM

the point of the bloom filter is to get the trade off to false positive probability. we set that probability to 0.0001 then choose the parameters for the filter to achieve that probabiliity

*trade off space to the false positive probability

MickLH

Yes. I am well aware of how a bloom filter works. Sorry for making you uncomfortable.

Tom

I'm very comfortable listening to your music. I'm just curious about the route you're taking

MickLH

To be concrete, I am saying that for a 0.0001 probability, and 256 bits of information, you can afford ~13.354... hashes to be encoded into the filter

Let alone splitting the 256 bits among 8 filters

Tom

afford in what context?

MickLH

If you insert 14 hashes into said bloom filter, the false positive rate rises above 0.0001

(so "afford" in the context of your security parameter vs key size)

Tom

11:16 PM

so you're saying that if you SHA3-256 hash something with an index several times, you can deduce that somehow the distribution of whatever pseudo-random bits those turn out, in a bloom filter this causes higher false-positive probability?

MickLH

No, I'm assuming that every aspect of the bloom filter is optimal

In the absolutely best case (unrealistic) scenario, that's the best it can ever do

Tom

but there is the extra index bits of data

MickLH

and the optimal Bloom filter is already close to the optimal solution permitted by information theory

(in a random oracle type of argument, anyways)

Tom

so over all the public hashes put into the filter you have not only the extra information from the index bytes concatenated with the private hash, but also the index bytes as the public hashes are added to the filter

MickLH

"extra information" is meaningless honestly, this is starting to feel like you simply don't want to accept a negative result and that's fine but if so then tell me so that I may continue my work

Tom

11:20 PM

so you actually have 4194304*256bits * 2 or something like that

MickLH

Ok then you should update your paper

Because your (public) key size claim is off by about a factor of 4194304*2

which invalidates your claims about it being competitive with existing schemes

Tom

not at all. the paper explains how the public key eventually (after more steps of refinement of the scheme) yields such small keys

MickLH

And I'm saying it doesn't (and can't) rigorously justify such compression without sacrificing security or introducing structured assumptions

But lets move on, this isn't the only killer problem

Lets assume you have invented magical bloom filters that beat information theory for now

Prove that finding a false positive in the bloom filter is as hard as brute force...

Tom

no the fact is the hashes that go into the bloom filter don't soley rely on the 256-bit private key, and so that argument -- as far as I can see -- is invalid

MickLH

It's not, but lets move on to the next critical issue since we're not making progress on the first one.

Tom

11:26 PM

you have to provide a message that will hash to require the signature

and since it's a cryptographic hash you won't be able to do that without iterating through message variations

MickLH

"cryptographic hash" isn't a well defined requirement from the hash function

does it depend on collision resistance or preimage resistance?

Tom

you can just assume it's SHA3-256

MickLH

I get that you mean to imply I should assume it's a perfect random oracle

But it does not comfort me to hear it in such loose terms without any justification, fyi

and I'm still being far more lenient than those who will attack the scheme at a typical crypto conference :P

Tom

well it can be assumed to have the preimage resistance etc of a leading cryptographic hash function

I kind of assume that people will read the paper carefully

MickLH

This really is not the place to fudge anything man, I'm not trying to challenge you

I'm asking the questions the paper left unanswered

Tom

11:30 PM

the paper said assume sha3-256

and it's all fine

MickLH

That's effectively meaningless and scary, you should say "Random Oracle" at the very least

Tom

ask the most probing questions

MickLH

Then your arguments have at least a chance of being rigorous

Tom

it's hardly meaningless and scary if it's a practical well-studied algorithm that has known properties

MickLH

That wasn't something I intended to debate

It was an observation, not my own opinion

I am obviously not given fear over a choice of hash function

I am explaining that it's a "hand waving argument" and doesn't really satisfy people looking for hard proof

(Which is basically anyone who would be in charge of choosing a signature scheme in any sane setting)

> no the fact is the hashes that go into the bloom filter don't soley rely on the 256-bit private key, and so that argument -- as far as I can see -- is invalid

Tom

11:34 PM

that's ok, but this stage is pre-complete-formalization, and I don't know why it matters if it's a 'random oracle' or 'sha3-256' for any argument you'll suggest

MickLH

If you don't know why it matters, then you absolutely need to study a lot more before trying to convince anyone your scheme is secure

It would be highly irresponsible to suggest that the proposal is safe for sensitive data in its current form

Tom

I'm relying on the security properties of that specific function, and so you'll have to tell me why that's unacceptable

MickLH

You're relying on magic.

Relying on the security properties of a specific function requires a rigorous mathematical formulation

SHA3-256 is not a security property

It's a feelsy-truthy assumption

Tom

no, but some amount of pre-image resistance is

MickLH

a "hand waving argument"

Sure, some amount of pre-image resistance is a security property

Now show how your scheme relies on that security property

Hint: Show how if your scheme is broken, then that security property MUST be violated.

Don't use feelings, don't use "You know what I mean" at all

Use only math

Tom

11:41 PM

I'm not sure why there's a need to state a way to break the scheme only if that property is violated, instead of focusing on the key questions that make this scheme different from other schemes -- the new security arguments

MickLH

Other way around

And because there are no "new security arguments"

I'm informing you of what a security argument actually consists of, so you could write one

If you want to say scheme X relies on problem Y, then you must show that anyone capable of breaking scheme X can be used to solve problem Y

Otherwise for all we know, you can just break X even if Y is impossible to solve

So here X = your scheme, and Y = SHA3

Tom

no the reliance is the other way round: if someone can break SHA3-256 then they can get past any security my scheme adds itself

MickLH

Please stop insisting, you are dead wrong here.

I will reiterate...

In order to be sure that breaking scheme X is for sure as hard as solving problem Y, then I need a separate algorithm (called a "reduction") that can produce an a fake key for scheme X, and then cracking that key gives you an answer to problem Y.

I understand that it might feel "backwards" but actually it's the intuition that people cling to which is backwards.

It's obviously trivial to break your scheme if SHA3 is broken. Proving that would be useless.

But what if your scheme is "SHA3 a random number, throw it away and check if the password is test"

Tom

they aren't the equivalent problem, so that inference is impossible

MickLH

it's obviously broken right?

But for all we know that scheme could be as strong as yours

Because being able to break either scheme, does not directly yield a way to reverse SHA3

If you disagree then please go away, you are absolutely frustrating face-cringingly wrong and overconfident in your wrong assertion.

Dunning–Kruger effect

The Dunning–Kruger effect is a cognitive bias in which low-ability individuals suffer from illusory superiority, mistakenly assessing their ability as much higher than it really is. Psychologists David Dunning and Justin Kruger attributed this bias to a metacognitive incapacity, on the part of those with low ability, to recognize their ineptitude and evaluate their competence accurately. Their research also suggests corollaries: high-ability individuals may underestimate their relative competence and may erroneously assume that tasks which are easy for them are also easy for others. Dunning and...

Tom

11:50 PM

here's what I think is happening: you aren't wanting to debate on the arguments we've been arguing (actually relating to the scheme), and so you've shifted towards formalities that are kind of strawman arguments that have nothing to do with the scheme

MickLH

No, you simply are vastly uneducated and do not understand what a security proof actually is.

See, a security proof is a mathematical proof of the security.

Your hand waving arguments only show why your intuition tells you that you're right. But your intuition is simply not correct about such arguments being rigorous.

You simply lack the required tools. Please study a bit more and try again.

Tom

right, and as I've said, that's not necessary when we can debate the parts of the scheme that don't require that formalization

MickLH

@SEJPM I'm gonna have to go. Would you mind confirming to this guy that a hand waving argument based on feelings does not count as a rigorous security reduction, so that he's not confused and bothered by his ego trying to explain away what has happened today?

(or anyone? peace.)

Tom

the fact is you can infer the formal arguments from the constraints in the paper

your ego is what's been bruised because your bloom filter argument was wrong

hate for this to devolve into a flame war

MickLH

lol I'm glad I checked again, that's hilarious.

Tom

11:55 PM

it's not really it's lame

MickLH

Ok lets try this again

Prove to me why it's secure.

Tom

and I'm saying, tell me the part of the paper that you don't understand

and that a reasonable person couldn't infer the formal argument for

MickLH

I read and understood the entire theory, though you didn't give an implementation.

Wait

Have you ever been to college for cryptography?

Jesus. You are taking too long... lets assume it's perfectly secure ok?

Tom

you see, you're doing it again

MickLH

I was being serious but hurry up, I don't have time for every ... average guy who thinks his ideas are better than they are, I'm just trying to help because you asked specifically and everyone else ignored your paper because it's obviously ridiculous, sorry.

So lets assume your scheme is perfectly secure, ok?

Can we start from such a mild assumption?

Tom

11:57 PM

no, I think you're just trying to patronize me

MickLH

Jesus christ.

This is your last chance, I am the only person who's both going to try to put up with your overconfidence and also actually has the skill required to analyse what you're proposing.

Tom

when the only formal thing you've tried to produce is the bloom filter argument that I think you actually agree is wrong

MickLH

Can we assume your scheme is perfectly secure for the sake of the fucking argument?

Tom

not really

MickLH

So you know it's not secure? lol

Tom

11:59 PM

you can continue speaking and stop asking rhetorical questions

MickLH