Subject: Re: OT: Rails is shitty
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 26 Jan 2008 03:12:29 -0600
Newsgroups: comp.lang.lisp
Message-ID: <JPSdncJwJKrgZAfanZ2dnUVZ_vamnZ2d@speakeasy.net>
<nagler+blackhole@bivio.biz> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) wrote:
| > Anyway, I'm just trying to point out that the only part of a closure
| > you need to send/retrieve from the client is the closure's lexical
| > environment (hopefully externalizable data), *not* the code for the
| > function itself.
| 
| I was thinking you need both for version consistency.
+---------------

It doesn't really help, so why waste the bandwidth? Yes, as you
pointed out, you really need versioning on the stuff that comes
back from the user [thanks for this observation!], but it really
doesn't matter whether the function code for the closure is
physically sent to/from the user or not -- you still have the
version consistency problem in either case.

That is, if the function code for the closure isn't sent [as I
recommended], then as you noted you can have version skew between
the externalized lexical environment and the function code. But
even if the closure function code *is* sent, you can still have
version skew between the code that was sent and what the *current*
execution environment in which that function code is going to run
expects. That is, what's *around* the continuation execution has
to match the continuation in either case. So given that, there's no
advantage [and plenty of disadvantages] in sending the actual code.

[Let us now drift even further off-topic, into cryptography... ;-} ]

+---------------
| Also, I believe the HMAC validation opens you up to Black Swans.
| If the HMAC was cracked, you'd have a very nasty injection attack
| on your hands.
+---------------

Note that I *didn't* say "use some random hash as a MAC" (Message
Authentication Code); I said "use HMAC", by which I meant specifically
the algorithm defined in RFC 2104 "HMAC: Keyed-Hashing for Message
Authentication" <http://www.ietf.org/rfc/rfc2104.txt>. The salient
point here is the *key*, which in this scenarios would be a secret
key stored only on the server. Specifically, the client *never knows*
the key! It is never transmitted. Only the HMAC result is transmitted
and then received/verified. The client (or an attacker) can't even
duplicate the HMAC they received, even with the cleartext data in hand.

If HMAC-SHA-256 or even just HMAC-SHA-1 [see RFC 2104] were to be
"cracked", a whole lot more financial towers would be falling than
your or my web sites! HMAC-SHA-n (for n = 1, 256, 384, 512) are used
*everywhere*, including in IPsec. [There might even be a Nobel Prize
in that achievement.]

But the HMAC construction is *significantly* stronger than just
the hash that is used. Even HMAC-MD5 is still thought to be quite
safe, even though weaknesses have been demonstrated in MD5 itself in
certain specific contexts [which don't include the usage in HMAC-MD5].

Finally, an HMAC neatly handles the versioning problem: simply
change the HMAC key when the version changes, and previous closure
states will no longer validate!

+---------------
| I also think that you would open yourself up by transferring
| interesting (and well-structured) state which would then be
| subject to offline (read: parallel) attacks.
+---------------

HMAC is much, *much* less vulnerable to an offline attack than
"just a hash". For the latter, yes, a massive offline collision
attack might allow you to twiddle some bits of the state, e.g.,
the now-well-known collision attack against MD5 can change a small
number [three? six?] of specific bits in a 1024-bit message. [Not
any six bits, mind, but six specific bits in fixed places within
the 1024-bit message. Only those few bits, and either all are
flipped or none are.] MD5 has *still* not been shown to be vulnerable
to the more useful "second preimage attack" with anything less
than brute force, with cost 2^128/n hashes, where n is the number
of hashes you're trying to break simultaneously.[1]

As I said above, for HMAC neither an attacker nor even the client
*itself* can duplicate the hash output given only the input data
(state). The secret key is required, since the algorithm is:

    H(K XOR opad, H(K XOR ipad, text))     [see RFC 2104, sect. 2 p. 3]

Without knowing the key, an offline attack is not feasible.
[An online attack is, but the attacker would have to submit
an average of 2^127 forged requests to your server to get
just one through. Fat chance. He'd look like a DoS attack and
you'd firewall him off long before he got anywhere close.]

And if you're using HMAC-SHA-1 or HMAC-SHA-256 instead of HMAC-MD5,
then replace all of the "2^128" above with "2^160" or "2^256".

+---------------
| This is probably my biggest concern of generalized client-side
| continuations. You are divulging significant application state...
+---------------

O.k., then encrypt just the application state with something strong,
like AES-CTR with a nonce as part of the key. BUT STILL USE AN HMAC
ANYWAY! [And be sure to do do crypt-before-auth, *NOT* auth-before-crypt.
The latter is provably weaker.]

+---------------
| ...AND a way to inject arbitrary code (via the lexical environment
| which might include an eval along the way).
+---------------

Not with an HMAC with any of the strong hashes. But again, see [1]
for the dangers of plain hashes as MACs in the presence of EVAL...


-Rob

[1] See the following for how in the presence of some sort of
    interpreter process (e.g., Postscript files, say, or Lisp EVAL)
    even the limited Wang/Feng/Lai/Yu-style MD5 collisions can
    be used to perform attacks that look on the surface *as if*
    they're full "chosen second preimage" attacks:

	http://www.docbug.com/blog/archives/000372.html
	http://www.cits.rub.de/MD5Collisions/

    An even faster approach is here:

	http://eprint.iacr.org/2006/105
	Vlastimil Klima, "Tunnels in Hash Functions:
	MD5 Collisions Within a Minute"

    So your concerns about an unrestricted EVAL of the closure
    state is well-warranted... *if* using simple hashes for MACs.

    But again, unless the attacker knows the key, HMAC is immune
    to these types of attacks [for less than brute-force cost].

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607