- cypherpunks - lists.cpunks.org

[Bitcoin-development] we can all relax now
by kjj 06 Nov '13

06 Nov '13

One of the things that really gets me going is when someone devises a model, tests it against itself, and then pretends that they've learned something about the real world. Naturally, the Selfish Mining paper is exactly this sort of nonsense. Their model is one with no latency, and one where the attacker has total visibility across the network. An iterated FSM is not a suitable simulation of the bitcoin system. The bitcoin network does not have states, and to the extent that you can pretend that we do, you can't simulate transitions between them with static probabilities. The authors understand this deep down inside, even though they didn't work out the implications. They handwave the issue by assuming a total sybil attack, and in true academic spirit, they don't realize that the condition necessary for the attack is far, far worse than the attack itself. Greg said he'd like to run some simulations, and I'm thinking about it too. Unfortunately, he is busy all week, and I'm lazy (and also busy for most of tomorrow). If neither of us get to it first, I'm willing to pitch in 1 BTC as a bounty for building a general bitcoin network simulator framework. The simulator should be able to account for latency between nodes, and ideally within a node. It needs to be able to simulate an attacker that owns varying fractions of the network, and make decisions based only on what the attacker actually knows. It needs to be able to simulate this "attack" and should be generic enough to be easily modified for other crazy schemes. (Bounty offer is serious, but expires in one year [based on the earliest timestamp that my mail server puts on this email], and /may/ be subject to change if the price on any reputable exchange breaks 1000 USD per BTC in that period.) Basically, the lack of a decent network simulator is what allowed this paper to get press. If the author had been able to see the importance of the stuff he was ignoring, we wouldn't be wasting so much time correcting him (and sadly the reporters that have no way to check his claims). https://bitcointalk.org/index.php?topic=324413.msg3495663#msg3495663 ------------------------------------------------------------------------------ November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231&iu=/4140/ostg.clktrk _______________________________________________ Bitcoin-development mailing list Bitcoin-development(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development

1 0

Re: [Cryptography] randomness +- entropy
by Jerry Leichter 05 Nov '13

05 Nov '13

On Nov 4, 2013, at 2:21 PM, John Denker wrote: > Some people have been throwing around the word "entropy" > rather carelessly. > > Entropy means something very special. Well, yes, and in its technical definitions - either in thermodynamics where it arose or information theory where it was imported because of a similarity in formalisms - it plays virtually no role in cryptographic discussion. In cryptography, especially when discussing random number generators, the word has a loosy-goosy meaning that's somehow tied to lack of predictability - but in an unspecified way. When people make it a regular habit to "guess" the entropy of various processes and then go on to build systems based on guesses, you know the word has lost any formal meaning it ever had. While the distinctions you draw are valid and important, I'm afraid "entropy" no longer has the capability to distinguish them. > For a great many cryptological purposes, a high-quality > PSEUDO-random distribution is good enough, even though its > entropy density is very low. Note the contrast: > > TRNG entropy density = 1 - epsilon > PRNG entropy density = epsilon I don't know what this means. > As another way of emphasizing the distinction: a PRNG places > orders-of-magnitude harsher demands on the strength of the > cryptological primitives it uses. I don't know what *this* means either. I drew a distinction in an earlier post - a distinction you can find in many papers on cryptographic primitives - between random values (unpredictable to the attackers being considered) and nonces (never repeated in a given cryptographic context, but there are no assumptions about unpredictability). Where a random n-bit value is specified, I can think of no paper that does not assume what we call "n bits of entropy" - though a better way to say it is "a value chosen uniformly at random from the set of n-bit strings". Sometimes the value is supposed to be chosen uniformly at random from some other set - e.g., from Z/p, i.e., between 0 and p-1. Trying to state this in terms of entropy is a losing game - and in fact it isn't actually trivial, given a random *bit* source, to produce such a distribution. People have gotten it wrong in the past. (The obvious technique of choosing a k with 2^k > p, choosing a "random" k-bit value, and the n reducing it mod p, if described in terms of "entropy", looks fine - I have k bits of entropy, which is more than enough to cover the choice I need to make. But the output is biased.) > This can be quantified > in terms of classical cryptologic ideas such as unicity > distance, but for present purposes I prefer the "entropy > density" language. "Unicity distance" is a nice but different concept - and one with little bearing on cryptography today. (If I draw a cipher E at random from some a collection of functions - e.g., by choosing a key - then the unicity distance is the unicity distance is just the number of pairs (x, E(x)) that specify E uniquely within the set. I suppose you can stretch this to talk about how many samples from the "random" generator are needed to specify *it* uniquely - i.e., be able to determine all past and future states - but I've seen the term used that way.) A broader - hence more useful - classical term (which may have been introduced by Shannon) is "equivocation". I don't recall the formal definition, but it attempts to capture the uncertainty an attacker has about the next plaintext, given all the information he already has. If I know a message was encrypted using a one-time pad, my uncertainty about the first character is not absolute - it's much more likely to be "t" than "z". T o provide information-theoretic security, a one-time-pad must contain "enough randomness" to keep my a priori and a postiori equivocation equal. This *is* something that can be given in terms of the entropies of the message and one-time-pad sources, but the deracinated notion of "entropy" one sees in most discussions is way too weak to say anything useful here.) > The rubber meets the road here: Consider the contrast: > > PRNG: I am quite sure that on startup the machine needs to > have on board a crypographically strong, well-seeded PRNG. > This needs to be up and running very, very early in the > boot-up process. Some things that need the PRNG cannot > wait. > > TRNG: At the moment I have no firm opinions as to how much > actual entropy the machine needs on start-up. I look > forward to having a discussion on this topic, with use-case > scenarios et cetera. A BBS generator is "indistinguishable" from a true random number generator. What's missing from that statement - and from the distinction you're drawing above - is a specification of the attack model. The BBS generator has inherent limitations that are given in its proof of correctness: The attacker has polynomially bounded resources (in fact, "attacker" literally means a polynomially-bounded probabilistic TM), which in turn implies that it only has access to a polynomially-bounded number of outputs. These are generally fine. The proof doesn't bother to state (though it's implicit) the obvious: That the attacker doesn't have access to the internal state of the generator. This isn't an "entropy" assumption - the internal state must, to the attacker, appear to have been chosen uniformly at random from all possible internal states, and is not available to the attacker. If you want to use "entropy-talk", all the entropy in a BBS generator is there, at the start, in the choice of the initial state. And yet there's a profound difference between the output of a BBS generator and the output of, say, a linear congruential PRNG starting with exactly the same state. One is pr edictable given a few successive samples; the other is secure given any polynomially-bounded number of them. "Entropy" simply cannot capture this distinction. And it's in fact exactly the distinction - in the transition from Shannon's classic notions of information-based security to modern computability-based ones - that make it possible to say anything useful at all about encryption algorithms other than one-time-pads. While we have no proofs like those for BBS for PRNG's built on practical cryptographic primitives, we generally assume that they have similar properties. (More correctly, we can prove some properties given assumptions about others. But those are the same assumptions we make about the actual encryption and hashing and signature algorithms we use. If they fail, the whole system falls down regardless of the source of "random" values.) To summarize: The distinction between cryptographic PRNG's and "true" RNG's has to do with the attack model. The attacker considered in the former is polynomially bounded (OK) and doesn't receive as input some special piece that we label "internal state" (this one can be violated). The attacker against a "true" RNG is ... what? Formalizing that is equivalent to formalizing randomness - which no one has managed to do. (In fact, modern developments of probability theory don't even try - random distributions are simply among the axioms. Even more, if you believe John Conway, the "Free Will" Theorem he and he and Simon Kochen proved show that "quantum unpredictability" is *stronger* than randomness!) In practical cryptography, this translates into "whatever I can imagine". In my other thread on plausible attacks, I tried to focus on limiting the attacker to, well, plausible operations in a particular real-world setting. If you *don't* do that, you can make no progress at all. A hardware generator - even Turbid - is vulnerable if I include as plausible an attacker who's infiltrated every supplier of electronic components in the world and has slipped a small transmitter into everything built, including every diode, resistor - hell, maybe every piece of wire! I have no problem with designing strong, practical random number generators. I'd love to see them deployed more widely. But clever designs of low-level primitives, as important as they are, are not a substitute for *system* designs; in fact, they can blind us to the necessary system properties. If a cryptographic primitive needs some unpredictable input, we need to go further and ask (a) how much? (b) unpredictable under what attack model? Only then can we begin to answer the *system* design question of "what's a suitable generator for such inputs?" If we can, for a reasonable cost (measured in any appropriate way), get our hands on a generator whose attack model assumes way more attacker resources than attacks on multiple uses of those values - great, let's make use of it. Too much discussion of "random number generators" is the equivalent of "I'm not sure AES is strong enough, so I'll do a ROT-13 encoding first - it can't hurt". And it can't - until you run into Tony Hoare's comment to the effect that "You can make a system so simple that you can see at a glance that it's correct, or so complex that you can't see at a glance that it's *not* correct." -- Jerry _______________________________________________ The cryptography mailing list cryptography(a)metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography

2 1

key challenge results
by coderman 05 Nov '13

05 Nov '13

vast majority of players (63*) were able to encrypt to my key even though the email address did not match. (no address would, nor could you query a key server for it) this is a much better result than i expected, as some "friendly" clients have trouble encrypting without an email match. the onion reference a ruse, misdirection. hidden services not required to encrypt ;) same for invalid creation date, however, i'd love to know if anyone had a client complain on create date. as for the rest, i did enjoy the quotation discussion tangent! best regards, --- *unofficial tally: 63 successful players 3 failed attempts 1 anon recipient (extra credit :) clients (unverified) including: GnuPG, BCPG, OpenPGP.js, Why do you need to know? on platforms spanning Linux, BSD, Windows, OSX.

1 0

[Cryptography] Embedded device key generation problems due to bad PRNGs
by Bill Frantz 05 Nov '13

05 Nov '13

<https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic…> describes net scans for bad RSA keys on the web performed by Zakir Durumeric, Eric Wustrow, Alex Halderman, and Nadia Heninger. Among their conclusions: We manually verified that 59,000 duplicate keys were repeated due to entropy problems, representing 1% of all certificates, or 2.6% of self-signed certificates. We also found that 585,000 certificates, or 4.6% of all devices used the default certificates pre-installed on embedded devices. More surprisingly, we discovered that entropy problems can allow a remote attacker with no special access to factor a significant fraction of the RSA keys in use on the Internet. We were able to factor 0.4% of the RSA keys in our SSL scan. We did this by computing the greatest common divisor (GCD) of all pairs of moduli from RSA public keys on the Internet. However, there’s no need to panic as this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown web servers. The list of vulnerable devices that we have already identified includes more than thirty different manufacturers, including almost all of the biggest names in the computer hardware industry. The kinds of products that we identified include firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones. This is a problem, but it’s not something that average users need to worry about just yet. However, embedded device manufacturers have a lot of work to do, and some system administrators should be concerned. This is a wake-up call to the security community, and a reminder to all of how security vulnerabilities can sometimes be hiding in plain sight. Cheers - Bill ------------------------------------------------------------------------- Bill Frantz | Airline peanut bag: "Produced | Periwinkle (408)356-8506 | in a facility that processes | 16345 Englewood Ave www.pwpconsult.com | peanuts and other nuts." - Duh | Los Gatos, CA 95032 _______________________________________________ The cryptography mailing list cryptography(a)metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography

1 0

Re: [Cryptography] randomness +- entropy
by Theodore Ts'o 05 Nov '13

05 Nov '13

On Mon, Nov 04, 2013 at 12:21:00PM -0700, John Denker wrote: > > FWIW note that current Linux distros make no attempt to > provide a reservoir of true-randomly distributed bits for > use at the next startup. There are some efforts toward > storing a seed for the kernel PRNG, but the stored seed is > itself pseudo-randomly generated, and the kernel correctly > attributes zero entropy to it. One of the reasons why we don't attempt to extract "true random bits" and save them across a reboot is that even we had such bits that were secure even if the underlying crypto primitives were compromised to a fare-thee-well, once you write them to the file on the hard drive and the OS gets shut down, there's no guarantee that an adversary might not be able to read the bits while the OS is shut down. Even if you don't do something truly stupid (such as leaving your laptop unattended in a hotel room while visiting China), the risk of having your "true random bits" stolen is probably higher than the cryptographic primitives getting compromised. That's probably one of the reasons why people tend to not necessarily worry about the difference between a CSRNG and a TRNG in practice. For example, these are the people who believe that we should just replace Linux's /dev/random with a Fortuna RNG which doesn't even pretend to try to track entropy estimates, and which fundamentally assumes that the underlying crypto algorithms are secure, or at least, not the weakest link to worry about. (Again, realistically, the chances that your OS kernel has some 0-day vulnerability that the NSA's Tailored Access Operations folks have purchased from some black hat is probably a bigger risk than there being a cryptographic weakness in AES or SHA that is exploitable given the how we are using the encryption or crypto hash in Yarrow, Fortuna or Linux's /dev/random.) I still think it's worth it to have a /dev/random where we attempt to make an estimate of the entropy that we've collected and then later dispensed. But I recognize that from a engineering perspective, the distinction is not going to be that important for many people who are interested in practical security issues. Regards, - Ted _______________________________________________ The cryptography mailing list cryptography(a)metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography

1 0

"Reforms" to NSA spying
by Jim Bell 04 Nov '13

04 Nov '13

A few days ago I read of 'reforms' being proposed to NSA spying on phone and internet metadata, along the lines of requiring the government to obtain some sort of warrant to get data from the phone companies, etc. Progress? I doubt it. Looks to me like the government knows it's going to lose control of the data, and probably there are no requirements that such phone co's keep 'all' the data. I predict that any proposed new bill will contain requirements that the phone co's record 'all' of the data the government might want, and keep it for an extended period of time. The government knows that if no such requirement is put into law, phone co's will compete for customers by offering ever-more-complete privacy. Soon enough, no phone company will store metadata, or they will store it in such a way that it will be useless for government purposes. Jim Bell http://news.yahoo.com/big-us-tech-firms-calls-reform-snooping-161145013.htm

3 2

NSA - What for.
by Juan Garofalo 04 Nov '13

04 Nov '13

What's the purpose of all the US spying? It obviously is not directed against 'terrists' since the only real terrorist out there are the american military sacks of shit and their accomplices. There are no 'foreign' terrorists who want to attack the US. If 'terrists' really existed, we'd be seeing real terrorist attacks in US cities every week. But there are none. So, are they spying on ordinary american subjects? What for? I mean, what actual benefit are they getting from that? They are the ones who caught DPR. But are they going to use their 'secret' information to put in jail every 'criminal' in the US? Or are they spying on behalf of american business, stealing industrial secrets and information from the competitors of american industries? Or are they mostly a useless bureaucracy that only steals and stores data, not doing anything else, at least for the time being? Preparing to transform the US from a covert totalitarian shithole into an overt totalitarian shithole? Or? J.

6 5

Re: [liberationtech] Obfuscation / Network Steganography Research
by Griffin Boyce 04 Nov '13

04 Nov '13

Lucas Dixon wrote: > Hi, > > I'm trying to put together a good reading and person list for what is > currently known on network steganography (in particular, network > traffic obfuscation) I'd recommend checking out these selected papers in anonymity: http://freehaven.net/anonbib/ Two papers in particular: Traffic Analysis Attacks on a Continuously-Observable Steganographic File System (Troncoso, et al 2007) http://freehaven.net/anonbib/cache/troncoso-ih2007.pdf StegoTorus: A Camouflage Proxy for the Tor Anonymity System (Weinberg, et al 2012) http://freehaven.net/anonbib/cache/ccs2012-stegotorus.pdf There are several that briefly talk about stego, but right now there haven't been that many devoted to the topic. best, Griffin -- Be kind, for everyone you meet is fighting a hard battle. PGP: 0xD9D4CADEE3B67E7AB2C05717E331FD29AE792C97 OTR: saint(a)jabber.ccc.de -- Liberationtech is public & archives are searchable on Google. Violations of list guidelines will get you moderated: https://mailman.stanford.edu/mailman/listinfo/liberationtech. Unsubscribe, change to digest, or change password by emailing moderator at companys(a)stanford.edu.

1 0

[Bitcoin-development] Electrum version 1.9
by Thomas Voegtlin 04 Nov '13

04 Nov '13

Electrum version 1.9 is now released. This version connects to multiple servers, and it also checks the SSL certificates of servers it knows. Please note that the BIP32 features are postponed (to version 2.0), due to the discussions about mnemonic seed format. Here is the changelog: # Release 1.9 * The client connects to multiple servers in order to retrieve block headers and find the longest chain * SSL certificate validation (to prevent MITM) * Deterministic signatures (RFC 6979) * Menu to create/restore/open wallets * Create transactions with multiple outputs from CSV (comma separated values) * New user interface for text mode, named "stdio" (does not use curses) * Plugins are no longer tied to the qt GUI, they can reach all GUIs * Proxy bugs have been fixed ------------------------------------------------------------------------------ Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk _______________________________________________ Bitcoin-development mailing list Bitcoin-development(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development

1 0

private fiber security, large IPsec deployments [was: PRISM too much trouble? Get MUSCULAR]
by coderman 04 Nov '13

04 Nov '13

On Wed, Oct 30, 2013 at 11:35 AM, Gregory Foster <gfoster(a)entersection.org> wrote: > ... According to a top secret accounting dated Jan. 9, 2013, > NSA’s acquisitions directorate sends millions of records > every day from Yahoo and Google internal networks ... > The NSA’s principal tool to exploit the data links is a > project called MUSCULAR, operated jointly with the > agency’s British counterpart, GCHQ. From undisclosed > interception points, the NSA and GCHQ are copying > entire data flows across fiber-optic cables that carry > information between the data centers... encryption between sites would eliminate the risk above on private fiber. you can easily accomplish this today via various means. (some businesses already VPN over private dedicated fiber) if you wanted to protect every host in every data center end-to-end would you go with IPsec or OpenVPN or other? what is the largest IPsec deployment on record? (transport, not tunnel mode) how would you handle key management / key exchange for such a system?

2 1