Has anyone experimented with having the expected/automatic transaction fees adjust at regular intervals, based on the recent transaction history? It wouldn't be too difficult to include in the difficulty retargeting code an adjustment of the tx fees constants based on whether the number and/or average size of transactions have increased/decreased over the last 2016 blocks.

I'm considering doing something similar for my demurrage-based altchain, but was surprised to find no hits on google for retargeting transaction fees...

So to summarize, you're saying that the brute-force key-recovery attack against of 3AES is no different than against regular AES?

I don't get how you can call that "broken"--that's what I'm aiming for, security is not reduced, and it's what I assumed from the start. Obviously it won't have *more* security against a brute-force attack than vanilla AES, since all keys are derived from the original. The only thing I'm aiming for is slightly better protection against a mathematical attack on the AES cipher itself.

Under the theory that should a practical attack on AES be published, it's a reasonable bet that the attack will not extend to a strengthened AES right away, as-is (or at least not be practical). That gives extra time to find a suitable alternative and transition everyone to it (which will take time for something like the bitcoin network).

The approach I'm considering would be the following:

K1 = K
K2 = SHA-256(K).truncate() // for AES-128 or AES-192
K3 = K

3AES_Encrypt(K, x) = AES_Encrypt(K3, AES_Decrypt(K2, AES_Encrypt(K1, x)))
3AES_Decrypt(K, x) = AES_Decrypt(K1, AES_Encrypt(K2, AES_Decrypt(K3, x)))

I don't know about you, but my CPU has hardware AES...

Thanks; if you read the stackexchange question I mention TDEA. The first security software I wrote used Triple-DES and only later was patched to include what was then known as Rijndael.

What I am specifically looking for is a drop-in replacement for AES-128 or AES-256, either as a symmetric encryption primitive or as special modes of operation. The TDEA approach requires doubling (or tripling) the key length, meaning the application/protocol needs to be aware of what you're doing.

I just asked it on crypto.stackexchange:

http://crypto.stackexchange.com/questions/779/hashing-or-encrypting-twice-to-increase-security

Interesting, thanks.

Which is exactly what I said

The issue with symmetric ciphers is how do you feed-forward to the 2nd round? Do you simply re-encrypt with the same key? With some ciphers that is analogous to encrypting once with a different key, and so wouldn't accomplish anything (I'm not sure about AES). Perhaps you'd use the ciphertext, or some hash of it as the key for the 2nd round? That would chain it together in a similar mannor, but who knows if that adds properties which open up new lines of attack...

This is probably a question for sci.crypt.

@ShadowOfHarbringer: those 0.00000002 BTC were never generated. Transactions are allowed to have fewer TxOut than TxIn--the difference is the Tx fee. Does the Satoshi client allow for the same discrepancy in the generating transaction? That would be news to me but explain what's going on here. The miner is failing to claim as many BTC as they are entitled to, resulting in fewer BTC generated for that block than would be expected. So this isn't really a case of coins being destroyed as much as new coins not being minted--but if the miner set the generator Tx0ut to zero, those transaction fees would be destroyed.

Anyone know why this happened? Looks like a buggy miner subtracted the Tx fee instead of adding it--but why was the block accepted by the network?

@theymos: that's an awfully round number. Are there 4 blocks that didn't generate bitcoins at all?

Iterative hashing is a technique well known in the literature and in practice. It occurred to me as well (and was the popular opinion in the thread I linked to), but if that were Satoshi's intent he would have used something like bcrypt(). Hashing twice instead of once really doesn't make much of a difference against a brute-force attack, such protection is not a concern for many areas where double-hash is used in bitcoin, and whatever effect it has on computational difficulty is cancelled out by bitcoin's built-in difficulty adjustment. Hence my original question: why?

The strengthening-by-additional-rounds argument makes sense though. Does anyone know an answer to my question about strengthening symmetric key ciphers via the same method?

Ah, because most types of attacks become less feasible as you increase the number of rounds, and double-hash is cryptographically analogous to running SHA256 with twice the number of rounds. That make sense.

Do you know if it is possible to increase the strength of symmetric encryption algorithms in a similar way? I.e, "AES(AES(plaintext))" where the outer AES uses a key derived from the intermediate ciphertext?

Why "SHA256(SHA256(data))"?

I understand the point of "address = RIPEMD160(SHA256(key))"--it combines the security of RIPEMD160 and SHA256, so both hash functions would have to be broken to undo the hash. But what cryptographic reason would there be for "SHA256(SHA256(data))"?

The only thing I can think of is that Satoshi was concerned or paranoid that there might be an attack on SHA256 based on the padding mechanism. But that's not a very credible theory. Anyone know why this (unusual) setup for a cryptographic hash was chosen?

My apologies if this has been answered before.. my Google-fu only turned up this thread, where the question was never sufficiently answered.

No, that would neither stop cosmic rays (too much energy), nor atmospheric neutrons (no charge). No simple solution I'm afraid

“biceps”?

That made me smile  

EDIT: It is possible to lose money, if the bitflip happens in the receiving address hash of the TxOut in the time between which the script is composed and the hash of the entire transaction is computed. But *is* exceedingly unlikely to occur, and could be checked for in the client anyway before broadcasting the tx. If I were running an exchange, it'd be the least of my concerns.

@casascius: RAID with any kind of redundancy (i.e, not RAID-0 or JBOD) *does* compare reads and notify of an error and/or fill in the gaps if possible.

If this were a software error, you'd see errors a lot more often than 1-in-a-trillion+.

@iamzill: why would Philip K. Dick's estate sue you? that's exactly how high-reliability systems have worked since the invention of the computer.

How do you differentiate coins in lost wallets from coins that just haven't been spent yet by their anonymous owners?

Answer: you can't.

Here's paper on the frequency of random-bit errors:

http://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf

If you are doing anything involving transactions of real-world value and you are not using ECC and RAID, you're doing it wrong. If you're handling transactions of extremely high value and you are not using redundant computation (asking multiple machines to generate/process transactions, and comparing results), you're doing it wrong.

The database systems that handle transactions for stock exchanges, air travel, heath devices, etc. have redundant storage, redundant memory, and redundant processing. Google "HP NonStop" for a good commercial example.

BRFI : Bitcoin Requests for Implementation (a la Scheme)

If you're this thorough about everything in life, I'm surprised you haven't encountered such an error before. Random one-bit errors do happen--I work with big data on consumer hardware and encounter this sort of thing about once a year or so. (That's why ECC memory and RAID exists.) With networks the situation is even worse, because there are some combinations of hardware routers and firmware versions that cause checksum fields to be overwritten rather than verified--and the chances of a transmission error over a network is much larger.

That said, there's no reason for the client to re-verify the transaction until it is actually used. I would hope that it would then discover the error and request the correct version from another node.