October 02, 2005

Extra Financial Cryptographic Engineering

Patrick announces his Loom system, which basically (AFAICS) allows slicing and dicing amounts into URLs that are distinguished by a SHA1 hash. Each piece of value can be placed into a new location with a new SHA1 hash, and as long as the SHA1 hash is kept secret, so is the dosh. (Also discussed on Venkat's blog.)

This bears comparison to epointsystem.org's ePoints which employ a similer slicing and dicing method. This system is heavily crypto-oriented but by repute employs a simple server that only offers two primitives: split, and combine.

Also, the use of SHA1 numbers as essentially big random numbers is what I use in my BRN extension to Ricardo, which is designed to do all the infrastructure behind blinded token money, without the blinding. (Serious students of FC will know that the blinding is about 2000 lines of code, and the rest is about two orders of magnitude larger, depending... so BRN creates an independent break between the precise blinding formula and the code that deals the tokens.)

What then is perhaps more interesting to the financial cryptographer is not the mechanism but the metaphor. By describing the BRN as a "location" in cyberspace, and the transfer as a placing of gold in a secret place, Patrick seems to have inspired his nearby supporters more than any description of crypto blah blah ever could.

There appears to be a new generation of hackers coming forth with money systems. I suspect this is because of the rise of p2p systems, which bring with them horrific problems in economic coordination. To my knowledge, only MojoNet (now MNET) addressed these challenges seriously with techniques known here but that story remains undocumented in FC annals (*hint*, *hint* !!!).

Meanwhile, in the Community currency field, there are now several systems offering basic accounting mechanisms (Cyclos, CCLite, MRS). These have a much lower security threshold, befitting their community heritage. Although some would argue this is mistake as community currencies often collapse at the point of success (as measured by being valuable enough to steal), I don't see it so dogmatically; like all communities, the CC world has to experiment, win a few and lose a few, in order to find out which of their assumptions were right and which wrong.

So my question is whether we now have sufficient FC activity to run another EFCE? Have the doldrums of FC passed, and is it time to make the pilgrimage to the hallowed halls of the Signet Library, or do we need another E-First City in Europe?

Posted by iang at October 2, 2005 10:55 AM | TrackBack
Comments

At present there is no merchant that exchanges loom gold - ezez.com is down for the count - so as yetloom is considerably less functional than the web site suggests. Still early days though, seems like a good idea.

Posted by: James A. Donald at October 3, 2005 12:41 AM

EzEz.com is definitely still in business but they are not accepting new customers at the moment. However, there is another merchant who exchanges loom gold:

https://rayservers.com/new/gold

There are more exchangers to come: some solid people have expressed interest.

I am also working on a new separate issue based on e-gold which will support automatic bailing and redemption. Then comes the Loom SCI, then an automated exchange, then even more issues as you can imagine. Then a bit of code refactoring to unify the code base even more strongly among distinct issues. Then tools to build new issues easily, followed pretty quickly by an open source release. Not to mention meeting my other commitments in life.

The rayservers blog has an excellent explanation of Loom, along with some promising applications in the realm of tor, mixmaster, and Phil Zimmerman's upcoming zFone project.

https://rayservers.com/new/blog/loom_zFone

Also, last night I installed a new, more serene interface for moving gold:

https://loom.cc/gold

One of my challenges on the e-gold issue is to make the bail and redeem interfaces equally beautiful and serene.

Posted by: Patrick Chkoreff at October 3, 2005 11:59 AM

As Patrick has mentioned, my blog entry goes into the implications of the Loom Gold currency.

I had done much thinking along these lines concerning digital cash, secure spam free untraceable anonymous email, self extending networks... a summary of which is on my blog.

There is a Loom Gold Treasure Hunt for Phil that will raise some gold for zFone, and draw attention to the possibilties that a simple system such as loom.cc has.

My blog entry is still being refined, so check back there for news: https://rayservers.com/new/blog/loom_zFone

When its reasonably complete and Patrick has both the loom and the EG issue sorted out, there will be a wider announcement of this.

Here's to Patrick!

Posted by: Venkat Manakkal at October 3, 2005 04:48 PM

Somehow the post ate the rayservers.com portion of the URL... it was good on the preview screen. Trying again.

Posted by: Venkat Manakkal at October 3, 2005 04:52 PM

I think, Ian got the crypto behind Loom wrong. The Loom locations (which I wouldn't call URLs) have nothing to do with SHA1 or any other hash function, except the fact that the locations are very probably stored by their hash values internally to prevelt wholesale robbery by cracking into the loom server (you just see hashes, not the actual locations). But even that is far from certain.

From a user's point of view, loom locations are just 128-bit random numbers, and s/he never needs to worry about the hash value. This is both an advantage and a disadvantage when compared to ePoints: Loom users don't need the capability to calculate hashes, ePoint users are better protected from insider fraud. Loom doesn't seem to be very concerned with issuer fraud; we are very mindful about it. Finally, with ePoints, locations can be used until the first withdrawal (which must be therefore an emptying of the location), since after that the location is exposed in the public records (public records are another safeguard against issuer fraud, which Loom doesn't have).

I'm wondering how Loom is governed, but I'll address that question to Patrick.

Posted by: Daniel A. Nagy at October 3, 2005 05:50 PM

It is not apparent to me if or how the loom system supports payments made to a machine. Seems to me a bit difficult to set up a website to accept loom payments without human intervention, and also difficult for someone who has made such a payment to demonstrate he has done so.

But yes, the interface is way cool - but being way cool is not all that is necessary to be useful.

Posted by: James A. Donald at October 3, 2005 06:08 PM

Right Daniel, no hashes are involved. They are actually 256-bit random numbers. I ordered some beautiful 16-sided dice from chessex.com so I can potentially use a full 256 bits of entropy for high-value locations. (Venkat mentioned I could use a spread-spectrum gold dust storage technique but I'd still need to seed that scheme.)

Originally when I prototyped the system a couple weeks ago I just stored the locations and associated values right in the database with no obfuscation whatsoever.

About a week ago I switched to encrypting the locations with an AES-256 key, to prevent leakage in a situation like a hidden camera viewing an adminstrative ssh session. This obviously has no bearing on the problem of insider fraud of course.

If we ignore the potential for collisions, it might be possible for me to use an irreversible hash scheme instead. But given the recent rumblings about SHA1 I decided to table that idea for a while and just use a guaranteed collision-proof scheme.

Besides, even if I did use a hash scheme it would still not address insider fraud. An insider would merely connect straight to the database and move value from one arbitrary hash to his own known hash. Also, he would go ahead and easily create a fake entry in the transaction log.

(Note here that transaction logs are purely for data integrity purposes, allowing the reconstruction of a bad database. With an infinitely reliable database I would not even bother to keep them. In fact, I intend to shred older chunks of logs after a suitable period of time.)

You are correct to observe that I cannot possibly disclose Loom transaction records to the public, simply because that would disclose confidential information about valuable or potentially valuable locations. I can see how a one-shot approach might address this, though I still need to think through the implications in detail.

I will definitely need to think more about the problem of insider fraud. As it stands right now, if you have my level of access to the server, you can simply scribble on the database however you like.

Makes me wonder how e-gold and 1mdc address the problem.

Also, in light of the potential anonymity of Loom locations, I will have to keep in mind Ian Grigg's dire warning about anonymous digital cash, namely the "bank robbery" problem. Basically the gunmen storm in on an administrator, force a login, create a bunch of fresh digital tokens (or merge some existing ones), and then notify their cohorts (which may include software robots) to begin a massive campaign of purchases or outexchanges.

OK, now I'm getting butterflies in my stomach so I'll stop right there.

Posted by: Patrick Chkoreff at October 3, 2005 06:54 PM

"It is not apparent to me if or how the loom system supports payments made to a machine. Seems to me a bit difficult to set up a website to accept loom payments without human intervention, ..."

Let's say Bob wants to buy coffee from Capulin.com.

First, Bob pre-loads some spending cash into a location. That's like his wallet. Then he goes shopping.

He connects to the Capulin.com web site via SSL and places his order using the shopping cart. He presses the Check Out button.

The Capulin site says he owes 6 grams of gold. Bob pastes his "wallet" location into the field there and presses Pay.

The Capulin site deducts 6 grams from the location and says thank you, your order will be shipped within 3 days.


"... and also difficult for someone who has made such a payment to demonstrate he has done so."


Bob drives up to a fast food window and hands the clerk a $20. Clerk gives him change for a $10. Bob says hey I gave you a $20. Clerk says no you didn't.

Or, Bob drives up and hands the clerk a $10. Clerk gives him change for a $10. Bob says hey I gave you a $20. Clerk says no you didn't.

(If either party anticipates fraud, there are ways to use printed serial numbers to kill a dispute. Not as easy if they're using uniformly constructed coins though.)

In the Capulin example, the merchant could take the money and then claim the customer didn't put anything there. Or the merchant could take the money and not ship the coffee.

Or, Bob could neglect to put any money there but claim Capulin took some.

In any case, I don't suppose Bob would continue to shop at Capulin coffee after that.

For larger purchase, the two parties might opt to establish an escrow.

There is another trick two people can use, which I haven't thought about very deeply yet, where the payer can move over a small amount of money at a time, and the payee picks it up in stages like that, each time confirming receipt of the previous chunk. Venkat mentioned this one to me once (and I believe it had crossed my mind before).

Posted by: Patrick Chkoreff at October 3, 2005 07:38 PM

Venkat, I've fixed your comments manually... possibly the perl script swallows the https improperly. Just another case where SSL webservers are a poorer class of net citizen :-/

Posted by: Iang at October 4, 2005 04:51 AM

Patrick,

On the bank robbery problem ... it is one of a class of "insider" problems where an outsider uses a gun to become an insider. I wouldn't worry about it for the short term, as systems do not face outside attack until they have succeeded.

No system is worth attacking until it is money and no system is money until it has been attacked. No matter the circularity, the time this happens in the gold community at least is when we have a liquid and sustained exchange market.

Posted by: Iang at October 4, 2005 04:58 AM

(forwarded email from Patrick, was delayed in mail sludge for some reason)

CLARIFICATION:

No hash function, SHA1 or otherwise, is used in the Loom system code.

Each location is 256 bits, period, and is entirely the choice of the user.

Thus you can have as much as 256 bits of entropy in it, for example if you used 16-sided dice from .

Or you could use weaker techniques such as hashing "joe's gold" along with some salt if you like.

But all such choices are beyond the purview or knowledge of the Loom system.

In fact, a user can stuff gold into location 00000000000000000000000000000000 if desired, though it's rather silly thing to do.


I'll follow up with the rest of your post soon but just wanted to get that correction out there fast.

Thanks,
Patrick

Posted by: Patrick at October 6, 2005 05:32 AM

"Thus you can have as much as 256 bits of entropy in it, for example if you used 16-sided dice from ."


In my emails I like to enclose URLs in angle brackets, but that understandably makes them disappear from the blog.

I got my 16-sided dice from:

http://chessex.com

Also, the loom.cc/gold issue, which was the very first one floated for peer review, uses only a 128-bit key (32 hex chars). There is no security concern there because there is only two troy ounces of gold in reserve for that issue.

All FUTURE issues will use a full 256 bit key (64 hex chars). Keys this large should not pose any extra difficulty for the user, since it's just copy and paste.

Ultimately we'd like to see other interfaces to the Loom protocol besides just the web browser. Modifying an instant messaging client such as GAIM might be a good first step here.

At that point Loom will be a simple server protocol, similar to the one used in qmail. Then all the user interfaces, including web/CGI, instant messaging plugins, email plugins, etc. will just connect to a Loom server port and transact in ASCII commands.

Thanks for posting my comments up there, Ian!

Posted by: Patrick Chkoreff at October 7, 2005 05:41 AM

Pete Chown on the e-gold list suggests that 128 bits is sufficient for any purpose.

The "tar pit" effect of the round-trip time lag would slow down any methodical search by many eons for sure.

If we have 2^128 locations, which is 10^38, and we assume 0.01 second for each trial by internet round-trip, then it would still take 10^36 seconds to search the whole space. That's about 3.2 * 10^29 years. (The DOS attack from hell!)

We COULD also factor in Moore's Law, which might cut the round-trip speed in half every couple years or so. Of course, I could always just FORCE a delay in the software in this case. However, as I shall soon illustrate, even that might not matter very much.

Using 256 bits certainly does sound amazing, particularly in light of observations like this from Venkat:

"Even with a million 10 GHz computers seaching that space with every clock cycle (that 10^6x10x10^9 = 10^16 locations per second, it would take 10^61 seconds to search the space or 3.1x10^53 years)."

But is 256 bits overkill?

Let's say that Moore's Law did bring us to the point where a bevy of remote computers could search my database over the internet 10^16 times per second. Would we be in trouble with 128 bits?

At 10^16 trials per second, they could manage about 3.2 * 10^24 tries per year. They would finish the space of 10^38 locations in about 3.2 * 10^14 years.

That's a LONG time. Again, by some estimates the universe itself is only about 1.5 * 10^10 years old.

Also consider that loom.cc/gold would NOT be the only issue on earth. I would expect millions or even billions of Loom-type issues by then, so anyone trolling for value would not likely spend 3.2 * 10^14 years looking at ONE issue.


So Pete, what you say is starting to sound right -- 128 bits may be enough!!


Posted by: Patrick Chkoreff at October 7, 2005 09:50 AM

Patrick,

128 bits is fine. The concerns with 128 bits stem from the Shandong work on hashes, which have put cracks in all older message digests and made SHA1 look old and venerable. But the cracks are to do with birthday attacks - which means a collision between two random numbers and this reduces the space to half or 64 bits.

So the first thing is to look at whether your design falls to a birthday attack? Not really, as the most interest is in whether I can figure out the 128 bit number you have _already_ chosen. It doesn't help me to find a number that hasn't got some value behind it.

Also, bear in mind that the attacks is against message digests which are not strictly random. As you are using random numbers, then there is no "reduction" achieved by these attacks that effects you.

Posted by: Iang at October 7, 2005 02:28 PM

128 bits is definintely enough. At ePointSystem, instead of a block cipher, we use hashing (also strongly recommended for your case as it constitutes a pareto-improvement), and let the user chose the length of their codes.
The default length used to be 192 bits, but by popular demand it was demoted to 96 bits, which is perfectly adequate for day-to day security.
Keep in mind that all you need to make sure is that searching the location space is substantially more expensive than the benefits from doing so. That is if you issue a total of 20 tons of gold and an exhaustive search through the keyspace costs 2000 tons, you're safe.

Posted by: Daniel A. Nagy at October 8, 2005 09:54 AM

Daniel wrote:

"128 bits is definintely enough. At ePointSystem, instead of a block cipher, we use hashing (also strongly recommended for your case as it constitutes a pareto-improvement), and let the user chose the length of their codes."


A couple of observations here.

My first inclination is to keep the precise 128 bit location I use now, and shove that through SHA1 for storage in the database and temporary transaction log.

(Collisions should not be a concern, especially considering that the input material (128 bits) is shorter than the resulting hash (160 bits). But even an actual collision would not be a major issue, since it would merely act like a "wormhole" in space that made two distinct locations equivalent in very rare instances.)

Given that I intended to use hashing, another colleague has suggested that as long as I'm hashing the thing anyway, I should just go ahead and allow the user to choose any old string of ASCII characters he likes.

OK sure, but early in the design I considered that idea and rejected it because some Fool would then choose "fool's gold" as a location.

OK, well just enforce a minimum length then, right? But then the Fool would just use "fool's gold + name of fool's cat + fool's birthday".

The next objection is: well, a Fool is going to lose his gold anyway even in your scheme. He could simply repeat his home telephone number several times to make up one of your "hex" locations.

But my point is, that is *harder* for the Fool to do. It is easier for the Fool to just press the "Random" button and be done with it. Not even a Fool wants to *type* one of these 32-digit suckers.

So my argument is, allowing arbitrary character strings (even with a minimum) makes it *easier* for people to be foolish. It's even tempting for ME. I was just looking at my tally screen the other day, and thought how nice it might be just to use locations like "Bob" and "Carol" instead of those funky hex strings.

I *guarantee* you that's what people will do if I allow arbitrary character strings. They might move gold to a location called "Bob" just as a one-off payment token. They don't intend to store a bunch of gold there long-term, they just want to pay Bob. But doing that is a trap.

I maintain that alternative *user interfaces* should address this. A chat client would let you pay people on your buddy list and would use 128-bit locations behind the scene.

I admit that if I DID allow arbitrary character strings, then people who ARE security-conscious could beef up their security somewhat, maybe even using diceware passphrases.

But this would just make it so damn *easy* for people to use weak locations, that I rejected the idea out of hand very early on.

Posted by: Patrick Chkoreff at October 8, 2005 06:53 PM

At ePointSystem, we allow arbitrary location lengths, yet it's still easiest for users to just press random than coming up with foolish locations so that's exactly what they do; the overwhelming majority of locations are default-length random strings generated by the wallet application. The phasing in of the newest version with 96 bit default location length instead of 192 bits can be clearly observed with the increase of shorter locations in the logs (with ePoints, the source is logged literally while the destination by hash for each transaction, so that the issuer cannot fake transfers).
Then again, our locations are single-use, which can make all the difference.
Your arguments definitely carry a lot more weight in your case, when locations are re-used.

On a different note, the similarities between our systems are so deep, that I'm willing to add a Loom Gold plug in to ePointWallet, so that people can store both ePoints and Loom Gold in the same wallet. Also, we might set up an automated exchange.

Posted by: Daniel A. Nagy at October 8, 2005 11:27 PM

OK, guys, I just fixed the comment thingie in MT so that https comment URLs are acceptable. I encapsulate this experience in my hypothesis #3.4:

Good Protocols Bootstrap Securely

On first time starting up, the protocol boots into secure mode. From there on, it only gets better.

[snip]

Posted by: Iang at October 9, 2005 10:01 AM
Post a comment









Remember personal info?






Hit preview to see your comment as it would be displayed.