×
all 8 comments
sorted by:
best
topnewcontroversialoldq&a

[–]segv00 13 points14 points  (0 children)

the article is slightly inaccurate when it uses bitcoin mining to try and say that the speed of hardware available to normal people is orders of magnitude slower than the speed of hardware available to special people (people/organization with lots of money and smarts).

the difference is that bitcoin mining is a fundamentally parallel algorithm. Over simplifying: We're given a hash Y and we want to find the number X whose sha256 is Y; to do this we just try as many Xs as we can. But there's no dependency between these attempts, we can try one X at a time, or we could try 1000 (or 54 million) at a time. This is why GPUs are so good at this. This time it takes you to test the hashes is inversely proportional to the number of CPUs you have.

But with repeated squaring this doesn't work (as far as I know). You're given the starting value of a process and asked to find the result of applying some function X times to it, but there's nothing to parallelize here. You can't start with step 3 until you've finished step 2 (since you don't know the input to step 3 until you've computed the output of step 2). If you have one CPU or a billion, it's going to take the same amount of time (assuming the CPUs run at the same speed).

What would make it faster is if you had a cpu that ran a 10Ghz instead of 2 or 3, but even that's just a 5 times speed up, and since the cost of reversing repeated squarings is O(n2) (where n is the cost put into the problem), guarding against a CPU 5 times faster than what you have requires only 2.3 times more work.

Of course, maybe there's a hardware implementation that can run this particular problem at 100GHz instead of 2, let's say 1THz just to be generous. To guard against this (an adversary 1000 times faster than you) you'd only have to spend 10 times longer yourself.

Given the way CPU clock speeds are going, they're not getting much faster, just more parallel, repeated squaring actually seems like a pretty good problem to use.

[–][deleted] 3 points4 points  (0 children)

Those damned Time Lords...

[–]moor-GAYZ 0 points1 point  (2 children)

By the way! I accidentally went and read "A Guided Tour Puzzle for Denial of Service Prevention" linked from the article (here's a summary on Wikipedia) and I'm really confused now: am I missing something crucial, or is their scheme an unnecessary complication of a much simpler (and not nearly as good as it seems) idea at its core?

In particular: what if we run all guide processes on the same server? Because from the crypto perspective there's should be no difference whatsoever (you can even have multiple servers behind a load balancer physically). Then all that cruft with guided tour, guide indexes and so on falls off, and what remains is the idea of a repeated authorization: the server sends you a random nonce, a sequence number, and the hash of the above with salt (plus maybe some work to do if you want a hybrid authorization scheme), you send it back, it verifies it, increments the sequence number and either lets you in or repeats.

So it should take, say, 10 exchanges before it lets you in, and you can't skip any because you can't increment the sequence number yourself because you don't know the secret salt. So with a 100ms latency it takes at least one second to authorize.

Which is cool and everything, but quite obviously doesn't prevent a malicious agent from running a shit-ton of requests in parallel. It only increases latency for a single authorization attempt, but, unlike other proof-of-work protocols doesn't require the client to do any work which would ordinarily exclusively utilize the CPU. So the whole thing is basically worthless.

[–]dmwit 0 points1 point  (1 child)

I didn't read the paper, and am going directly from your description, so take my response with a grain of salt (haha).

But if you're making a scheme that depends critically on network latency, perhaps one way to defend a need for multiple servers is that the idea is that you spread the servers out around the world to ensure that at least half or so of them have high latency, no matter where you are. That is, one server isn't enough because you'd like to defend from an attacker that manages to get into your datacenter.

[–]moor-GAYZ 0 points1 point  (0 children)

The problem is that even if we have guaranteed latency, this scheme absolutely doesn't prevent anyone from ddosing us, brute forcing our passwords or anything.

If you require the client to spend 1 second of CPU time to get access to something we want protected, then adversaries need 1000 CPUs to get 1000 requests/s through.

If you require the client to spend 1 second of wall-clock time, then an adversary needs 1 CPU running 1000 concurrent connections to get 1000 requests/s through. The only thing you have succeeded at is delaying the flood of connections by 1 second.

In fact we can make the whole thing even more absurd: in their scheme the system doesn't have to store information for each connection attempt, it's stored in the wire. If we can afford keeping the connection open, then we don't even have to care about latency, the whole thing becomes equivalent to keeping each client on hold for 1 second before letting them in. Absolutely useless.

[–]moor-GAYZ 0 points1 point  (2 children)

Oh, also a minor correction regarding the Rivest's scheme:

This has the nice property that the puzzle constructor invests only O(n) computing power, but the solver has to spend O(n2) computing power. (This scheme works in the random oracle model, but Barak & Mahmoody-Ghidary 2009 proves that is the best you can do.)

I don't know if it's just a confusing language, but Rivest's scheme obviously (if you look at the code provided in the link) works in like O(log n) for the constructor, because he has access both to n (that is, p * q) and phi ((p - 1) * (q - 1)). It gives basically the exponential advantage to legitimate users vs brute-forcing attackers as RSA.

The much worse O(n) vs O(n2) ratio applies only to the random oracle model, where there's no structure to the problem that legitimate users exploit to gain massive speedups (i.e. they use an honest one-way function instead of one with a trapdoor).

[–]gwern 0 points1 point  (1 child)

It gives basically the exponential advantage to legitimate users vs brute-forcing attackers as RSA.

I see. So it's actually log(n) to construct and n2 to break?

[–]moor-GAYZ 1 point2 points  (0 children)

I think just O(n). Or, better, in his terms, to compute by brute force 22^(t) (mod N) takes O(t) (i.e. even when you use exponentiation by squaring), while if you know N's prime decomposition you can compute it as

    BigInteger n = p.multiply(q);
    System.out.println("n = "+n);

    BigInteger pm1 = p.subtract(ONE);
    BigInteger qm1 = q.subtract(ONE);
    BigInteger phi = pm1.multiply(qm1);
    System.out.println("phi = "+phi);

    // Now generate final puzzle value w
    BigInteger u = TWO.modPow(t,phi);
    BigInteger w = TWO.modPow(u,n);
    System.out.println("w (hex) = "+w.toString(16));

On the order of O(log t).