Silk Road forums

Discussion => Security => Topic started by: cdy0101010x on September 15, 2013, 04:09 am

Title: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: cdy0101010x on September 15, 2013, 04:09 am
Most people don't know about the existence of quantum computers. Almost no one understands how they work, but theories include bizarre-sounding explanations like, "they reach into alternate universes to derive the correct answers to highly complex computational problems."

Quantum computers are not made of simple transistors and logic gates like the CPU on your PC. They don't even function in ways that seem rational to a typical computing engineer. Almost magically, quantum computers take logarithmic problems and transform them into "flat" computations whose answers seem to appear from an alternate dimension.

For example, a mathematical problem that might have 2 to the power of 'n' possible solutions -- where 'n' is a large number like 1024 -- might take a traditional computer longer than the age of the universe to solve. A quantum computer, on the other hand, might solve the same problem in mere minutes because it quite literally operates across multiple dimensions simultaneously.

If you know anything about encryption, you probably also realize that quantum computers are the secret KEY to unlocking all encrypted files. As I wrote about last year here on Natural News, once quantum computers go into widespread use by the NSA, the CIA, Google, etc., there will be no more secrets kept from the government. All your files -- even encrypted files -- will be easily opened and read.

***Clearnet link***
http://www.naturalnews.com/040859_skynet_quantum_computing_d-wave_systems.html
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: abrakadabra on September 15, 2013, 04:33 am
 Na, google would NEVER sell out their users and they always protect and keep private the mass of data they collect from everyone. It's just collected so they can provide a personalized experience to their users and never shared, sold or otherwise misappropriated.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: CrazyBart on September 15, 2013, 04:53 am
Na, google would NEVER sell out their users and they always protect and keep private the mass of data they collect from everyone. It's just collected so they can provide a personalized experience to their users and never shared, sold or otherwise misappropriated.

good one!
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: abrakadabra on September 15, 2013, 05:18 am
When it was revealed the US gov had everyone's cellular phones tapped, an interesting (and funny) idea was proposed called
                     "operation everyone talk like a terrorist, all the time"
 If we all talk about terror plots openly in each of our telephone conversations then eavesdropping on those conversations becomes pointless.   

    maybe we could do similar concept with internet communications.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: abrakadabra on September 15, 2013, 05:35 am
Na, google would NEVER sell out their users and they always protect and keep private the mass of data they collect from everyone. It's just collected so they can provide a personalized experience to their users and never shared, sold or otherwise misappropriated.

good one!
Thanks, I thought so too!
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 15, 2013, 11:30 am
Quantum computers have the **theoretical** ability to break common public-key algorithms (RSA/PGP), and Elliptic Curve cryptography regardless of key length and to effectively halve the key length of any symmetric algorithm (AES, Blowfish)

It's doubtful any of the prototypes around have the ability to do this yet, plus it's more likely they would build SKYNET or something with it than spend all day meddling with encryption. Who knows what the NSA has though.

If you want to trade super secret stolen government secrets encrypt it with SHA-2(512)/AES-256 or SHA-3(1024)/Threefish-512. https://www.schneier.com/skein.html

I would recommend the actual NIST SHA-3 winner which was Keccak but since nobody can trust NIST anymore would seem logical not to use anything they are promoting http://keccak.noekeon.org/
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: SuckDick4Weed on September 15, 2013, 11:34 am
OHMAGOD

They just found a way to deliver ads even faster and charge business even more for advertising.

Pay per click just went from $10 to $100
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 15, 2013, 03:35 pm
Quantum computers have the **theoretical** ability to break common public-key algorithms (RSA/PGP), and Elliptic Curve cryptography regardless of key length and to effectively halve the key length of any symmetric algorithm (AES, Blowfish)

It's doubtful any of the prototypes around have the ability to do this yet, plus it's more likely they would build SKYNET or something with it than spend all day meddling with encryption. Who knows what the NSA has though.

If you want to trade super secret stolen government secrets encrypt it with SHA-2(512)/AES-256 or SHA-3(1024)/Threefish-512. https://www.schneier.com/skein.html

I would recommend the actual NIST SHA-3 winner which was Keccak but since nobody can trust NIST anymore would seem logical not to use anything they are promoting http://keccak.noekeon.org/

AES-256 can only take a 256 bit key, you would only be able to use half the output of SHA-512. Threefish-512 can only use a 512 bit key, you would only be able to use half of the output of SHA-1024.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: PaperStreetSoapCompany on September 15, 2013, 04:18 pm
This thread makes my brain hurt.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 15, 2013, 04:36 pm
Quantum computers have the **theoretical** ability to break common public-key algorithms (RSA/PGP), and Elliptic Curve cryptography regardless of key length and to effectively halve the key length of any symmetric algorithm (AES, Blowfish)

It's doubtful any of the prototypes around have the ability to do this yet, plus it's more likely they would build SKYNET or something with it than spend all day meddling with encryption. Who knows what the NSA has though.

If you want to trade super secret stolen government secrets encrypt it with SHA-2(512)/AES-256 or SHA-3(1024)/Threefish-512. https://www.schneier.com/skein.html

I would recommend the actual NIST SHA-3 winner which was Keccak but since nobody can trust NIST anymore would seem logical not to use anything they are promoting http://keccak.noekeon.org/

AES-256 can only take a 256 bit key, you would only be able to use half the output of SHA-512. Threefish-512 can only use a 512 bit key, you would only be able to use half of the output of SHA-1024.

The security strength of SHA-2: SHA-224 is 112-bits, SHA-256 is 128-bits, SHA-384 is 192-bits and SHA-512 is 256-bits and if I remember correctly that's the default value in Truecrypt (SHA-512).

Threefish is a built-in block cipher for Skein, which is the same size as the block so you're right that Skein-1024 would be Threefish-1024 by default, Skein-512/Threefish-512 ect.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 15, 2013, 05:16 pm
Quantum computers have the **theoretical** ability to break common public-key algorithms (RSA/PGP), and Elliptic Curve cryptography regardless of key length and to effectively halve the key length of any symmetric algorithm (AES, Blowfish)

It's doubtful any of the prototypes around have the ability to do this yet, plus it's more likely they would build SKYNET or something with it than spend all day meddling with encryption. Who knows what the NSA has though.

If you want to trade super secret stolen government secrets encrypt it with SHA-2(512)/AES-256 or SHA-3(1024)/Threefish-512. https://www.schneier.com/skein.html

I would recommend the actual NIST SHA-3 winner which was Keccak but since nobody can trust NIST anymore would seem logical not to use anything they are promoting http://keccak.noekeon.org/

AES-256 can only take a 256 bit key, you would only be able to use half the output of SHA-512. Threefish-512 can only use a 512 bit key, you would only be able to use half of the output of SHA-1024.

The security strength of SHA-2: SHA-224 is 112-bits, SHA-256 is 128-bits, SHA-384 is 192-bits and SHA-512 is 256-bits and if I remember correctly that's the default value in Truecrypt (SHA-512).

Threefish is a built-in block cipher for Skein, which is the same size as the block so you're right that Skein-1024 would be Threefish-1024 by default, Skein-512/Threefish-512 ect.

Truecrypt uses SHA-512 for its PRNG, you cannot possibly key AES-256 with a full SHA-512 output because AES-256 takes only 256 bit keys. The bit strength of SHA-X is X, in certain circumstances the security strength could be less due to various attacks, but if collisons are found with less than 2^X probability then the hashing function lowers the security of the overall cryptosystem. No collisions have been found for any of the SHA algorithms other than SHA-1, which apparently had its security lowered to 2^60, meaning with a given file and hash value, you could find another file with the same hash value after producing 2^60 outputs. So it would be bad to use this hash algorithm produce a key for a symmetric cipher, because even if the password is 128 bits a collison producing the same output hash value could be found after 2^60 attempts.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 15, 2013, 05:25 pm
But you can key AES-256 with partial output from SHA-512. You would just split the output in half. But might as well just use SHA-256. I believe it is also debatable if it would be safer to use SHA-512 or SHA-256. I have read some things indicating that SHA-256 would be safer, but one cryptographer I talked with said he would make the case that it is equally safe to use half a SHA-512 output as it is to use an entire SHA-256 output.

The thing is, cryptographic hash functions distill and evenly distribute randomness. At least, this is according to one thing I read a long time ago when I was first learning about cryptographic hashes, and I think it is true. So if you feed SHA-256 1 bit of entropy, the output 256 bits will have 1 bit of entropy evenly distributed through out them. This is the distributive property of cryptographic hash functions, the distillation property is that if you feed it 1000 bits of data which contain 1 bit of entropy, the output hash will have 1 bit of entropy in 256 bits of data. So if this is a correct understanding of cryptographic hash functions, it would seem that it would be safer to use SHA-256 to key AES-256, because let's say your password contains 256 bits of entropy. You feed the password to the hash function and the output hash has 256 bits of entropy. If you use SHA-512 and feed it a password with 256 bits of entropy, the output also has 256 bits of entropy, but now it is spread over 512 bits. When you take half of those bits to key AES-256, it would seem like you are only actually getting 128 bits of security, as each bit from the hash function has half a bit entropy due to the distributive property of cryptographic hash functions.

I am not sure if this happens in practice. From what I have read about cryptographic hashing functions, it seems like it should happen this way, and that it would be safer to use SHA-256 for the hash function to generate a key for AES-256. But like I said, one crytpographer said he would argue that both methods are equally secure.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: jackofspades on September 15, 2013, 05:44 pm
This thread makes my brain hurt.

Im with you PSSC

ill leave it to the computer nerds to figure this out and hopefully someone will paraphrase whatever i need to know for me lol
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: EastCoastCollective on September 15, 2013, 05:59 pm
According to an article  published on 9/5/13 in USAtoday.com  NSA spent  many billions building a supercomputer that can crack any and all encryption software  >:( After reading the article I wondered if its useless to encrypt??
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 15, 2013, 06:06 pm
is it useless to wear bullet proof vests because the US military has rockets?
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: RS7FI8ZRkm on September 15, 2013, 06:22 pm
is it useless to wear bullet proof vests because the US military has rockets?
yes an no? :P
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 15, 2013, 06:34 pm
A better answer from me would have been that the NSA probably actually cannot break all encryption, even with their multi billion dollar super computer. But even assuming they can, it doesn't mean encryption is worthless. If it takes them two days to decrypt a single message, why do you think they gonna spend two of those days decrypting your order for an ounce of bud.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 15, 2013, 07:08 pm
But you can key AES-256 with partial output from SHA-512. You would just split the output in half. But might as well just use SHA-256. I believe it is also debatable if it would be safer to use SHA-512 or SHA-256. I have read some things indicating that SHA-256 would be safer, but one cryptographer I talked with said he would make the case that it is equally safe to use half a SHA-512 output as it is to use an entire SHA-256 output.

The thing is, cryptographic hash functions distill and evenly distribute randomness. At least, this is according to one thing I read a long time ago when I was first learning about cryptographic hashes, and I think it is true. So if you feed SHA-256 1 bit of entropy, the output 256 bits will have 1 bit of entropy evenly distributed through out them. This is the distributive property of cryptographic hash functions, the distillation property is that if you feed it 1000 bits of data which contain 1 bit of entropy, the output hash will have 1 bit of entropy in 256 bits of data. So if this is a correct understanding of cryptographic hash functions, it would seem that it would be safer to use SHA-256 to key AES-256, because let's say your password contains 256 bits of entropy. You feed the password to the hash function and the output hash has 256 bits of entropy. If you use SHA-512 and feed it a password with 256 bits of entropy, the output also has 256 bits of entropy, but now it is spread over 512 bits. When you take half of those bits to key AES-256, it would seem like you are only actually getting 128 bits of security, as each bit from the hash function has half a bit entropy due to the distributive property of cryptographic hash functions.

I am not sure if this happens in practice. From what I have read about cryptographic hashing functions, it seems like it should happen this way, and that it would be safer to use SHA-256 for the hash function to generate a key for AES-256. But like I said, one crytpographer said he would argue that both methods are equally secure.

SHA-512 is largely identical to SHA-256 isn't it? but operates on 64-bit, thus there are some computation artifacts of SHA-512 that make cracking programs like hashcat harder to use with GPUs, giving you a slight advantage to not being at the mercy of GPU cloud hashing. No idea about ASIC or FPGA's though, I would assume they don't have this problem. All the encryption I've seen to make containers and the like, are using SHA-512 (Schneier also advocates SHA-512, but says there's nothing wrong with any SHA-2) while all the software implementations to use bcrypt/encrypt databases, are using sha256, probably to avoid that password spreading problem you talked about when feeding in passwords to avoid the 72 byte limit (though Password1 is now using 512)

Example:  $h=crypt(hash('sha256', $p),'$2y$......................');  bcrypt and scrypt make it really hard for GPUs to crack anyways. There's also this, which is a bcrypt 256 implementation to separate keys from server and encrypt the hashes as well http://sebsauvage.net/paste/?a99d7b619aa2a028#Ey6MdAyxEywI7JAox7afg7wBBSf0bh/qS6wnQ2MD1OU=

Meanwhile TC is using SHA-512, Whirlpool (512), and RIPEMD-160 hashes for AES256 keys.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: deathowl1990 on September 15, 2013, 07:38 pm
They must have switched this thing on today. All my Google searches now return pictures of cats that are both dead and alive.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: bitfool on September 15, 2013, 10:50 pm
Do your research!


http://www.scottaaronson.com/blog/?p=1400
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: SuckDick4Weed on September 16, 2013, 12:03 am
So that explains why Microsoft just deployed new SHA-1 / SHA-2 hash tables for internet explorer.

No-one should use windows. Pretty suss when you have also "uninstalled" internet explorer yet they still deploy update files for it. What's even more suss is trying to look up changelog information that just sends you around an internet loopy loop.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: StaticTension on September 16, 2013, 02:09 am
OHMAGOD

They just found a way to deliver ads even faster and charge business even more for advertising.

Pay per click just went from $10 to $100

Ha...that's what I was thinking!
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: NW Nugz on September 16, 2013, 03:18 am
A better answer from me would have been that the NSA probably actually cannot break all encryption, even with their multi billion dollar super computer. But even assuming they can, it doesn't mean encryption is worthless. If it takes them two days to decrypt a single message, why do you think they gonna spend two of those days decrypting your order for an ounce of bud.
Because my bud's that good ?  :-)
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: SelfSovereignty on September 16, 2013, 03:27 am
As I wrote about last year here on Natural News, once quantum computers go into widespread use by the NSA, the CIA, Google, etc., there will be no more secrets kept from the government. All your files -- even encrypted files -- will be easily opened and read.

***Clearnet link***
http://www.naturalnews.com/040859_skynet_quantum_computing_d-wave_systems.html

I would be deeply ashamed to admit it if I had written this.  It would be comical if not for the consequences.  Absolute pseudoscientific dribble of the most offensive and misleading kind.  You are not fit to report on news, sir: either you do not understand the subject matter, or you do not care that you are misrepresenting it.  There are very few things in this world that truly sicken me beyond all reason.  The work you produce and my assumptions of your character based on such are among them: you aid in disseminating lies and misinformation that keep the public ill informed and unable to make rational decisions because their view of the facts are warped and invalid.

Instead of helping people who cannot or will not take the time to understand a subject, you are filling people's heads with lies and biased delusions.  You are part of the reason innocent people have their lives broken and discarded by the state and popular opinion.  I do not know what reasons you have for your actions, but I have difficulty imagining any that would justify trying to convince anyone that will listen that artificial intelligence and the advancement of science and knowledge are synonymous with the death or enslavement of humanity.

Understanding ourselves and the world around us is our best -- and only -- hope.  Without understanding we are doomed to extinction like so many before us.  You deliberately make it harder for people to understand their world.  If anyone here is truly a criminal, it is you.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: cdy0101010x on September 16, 2013, 04:00 am
1) Sorry for any confusion, I'm not the guy who wrote that article, the original post contained parts of what was written on the clearnet page

2) You haven't pointed out what's so terribly wrong about the piece, and you seem to attack the writer more than the content. Specifically, what is the problem?
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kittenfluff on September 16, 2013, 01:40 pm
According to an article  published on 9/5/13 in USAtoday.com  NSA spent  many billions building a supercomputer that can crack any and all encryption software  >:( After reading the article I wondered if its useless to encrypt??

OH EM GEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE!!!!

Ok, the NSA have no such supercomputer because no kind of supercomputer can get round the P vs NP problem (and there may be no way around it, but no one knows right now). This would be a mathematical breakthrough MUCH larger than finding the Higgs Boson. What NSA have apparently done is weaken commercial encryption algorithms (usually by making the entropy generators less than random) so that they CAN break the encryption, but strong encryption is still strong. For instance, on a desktop pc it would take 6.4 quadrillion years to brute-force 2048bit RSA encryption. Working using conventional algorithms the D-Wave2 can compute problems 3600x faster (according to the wiki page - the only place I could find that had actual facts, no just glossy brochure crap), which still places it at taking 1.8 trillion years to brute force.

Now, where quantum computers excel is in that they can execute Shor's algorithm - this can use unique properties of qubits to break encryption. Don't ask me how it works, I'm working on learning about this kind of thing, but am not that advanced yet. However, this is not just some kind of magic spell any old quantum processor can manage, there are requirements. For starters, the noise needs to be low enough, but let's assume that is for now. The main point is that you need enough qubits. 512 qubits is very respectible, but as far as I can tell you need more qubits than the number of bits in the encryption key. Most sources say twice as many, did find this which suggest RSA768 can be broken with 1154quibits - about 1.5x the bit of the encryption key:

CLEARNET
http://www.nature.com/nature/journal/v499/n7457/fig_tab/nature12290_T1.html

So, to crack a 2048bit RSA they would need around 3000+ qubits. 512qubits is respectible, but not enough.

The final point is this - even if they did have a black box that could do this, it still takes some time and resources each time. They can't just decrypt everything in real time, and even if they could they do not have the HuMint resoruces to interpret it in real-time. The more encryption used, and the better the encryption, the harder and more costly it is for them and the more they have to use discretion over who they target.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: anonypunk on September 16, 2013, 04:37 pm
As I wrote about last year here on Natural News, once quantum computers go into widespread use by the NSA, the CIA, Google, etc., there will be no more secrets kept from the government. All your files -- even encrypted files -- will be easily opened and read.

***Clearnet link***
http://www.naturalnews.com/040859_skynet_quantum_computing_d-wave_systems.html

I would be deeply ashamed to admit it if I had written this.  It would be comical if not for the consequences.  Absolute pseudoscientific dribble of the most offensive and misleading kind.  You are not fit to report on news, sir: either you do not understand the subject matter, or you do not care that you are misrepresenting it.  There are very few things in this world that truly sicken me beyond all reason.  The work you produce and my assumptions of your character based on such are among them: you aid in disseminating lies and misinformation that keep the public ill informed and unable to make rational decisions because their view of the facts are warped and invalid.

Instead of helping people who cannot or will not take the time to understand a subject, you are filling people's heads with lies and biased delusions.  You are part of the reason innocent people have their lives broken and discarded by the state and popular opinion.  I do not know what reasons you have for your actions, but I have difficulty imagining any that would justify trying to convince anyone that will listen that artificial intelligence and the advancement of science and knowledge are synonymous with the death or enslavement of humanity.

Understanding ourselves and the world around us is our best -- and only -- hope.  Without understanding we are doomed to extinction like so many before us.  You deliberately make it harder for people to understand their world.  If anyone here is truly a criminal, it is you.
Was thinking something very similar.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: Dickens018 on September 16, 2013, 05:26 pm
According to an article  published on 9/5/13 in USAtoday.com  NSA spent  many billions building a supercomputer that can crack any and all encryption software  >:( After reading the article I wondered if its useless to encrypt??

NO, not at all.   Keep using PGP(GPG).

 The fact that NSA is still clueless to the files on the Flash Drive they seized in London indicates with high probability that some strong crypto, likely TrueCrypt, can withstand a major NSA assault for at least months.

  The NSA's great breakthroughs seems mainly in grabbing all the keys, or crippling the Pseudo Random Number Generator so keys can be found faster.

  Quantum Computers of a few bits have been created,  but a quantum computer large enough to handle the  prime factor problems at the heart of crypto is decades away.

   Stay safe.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 17, 2013, 01:49 am
But you can key AES-256 with partial output from SHA-512. You would just split the output in half. But might as well just use SHA-256. I believe it is also debatable if it would be safer to use SHA-512 or SHA-256. I have read some things indicating that SHA-256 would be safer, but one cryptographer I talked with said he would make the case that it is equally safe to use half a SHA-512 output as it is to use an entire SHA-256 output.

The thing is, cryptographic hash functions distill and evenly distribute randomness. At least, this is according to one thing I read a long time ago when I was first learning about cryptographic hashes, and I think it is true. So if you feed SHA-256 1 bit of entropy, the output 256 bits will have 1 bit of entropy evenly distributed through out them. This is the distributive property of cryptographic hash functions, the distillation property is that if you feed it 1000 bits of data which contain 1 bit of entropy, the output hash will have 1 bit of entropy in 256 bits of data. So if this is a correct understanding of cryptographic hash functions, it would seem that it would be safer to use SHA-256 to key AES-256, because let's say your password contains 256 bits of entropy. You feed the password to the hash function and the output hash has 256 bits of entropy. If you use SHA-512 and feed it a password with 256 bits of entropy, the output also has 256 bits of entropy, but now it is spread over 512 bits. When you take half of those bits to key AES-256, it would seem like you are only actually getting 128 bits of security, as each bit from the hash function has half a bit entropy due to the distributive property of cryptographic hash functions.

I am not sure if this happens in practice. From what I have read about cryptographic hashing functions, it seems like it should happen this way, and that it would be safer to use SHA-256 for the hash function to generate a key for AES-256. But like I said, one crytpographer said he would argue that both methods are equally secure.
SHA-512 is largely identical to SHA-256 isn't it?  but operates on 64-bit, thus there are some computation artifacts of SHA-512 that make cracking programs like hashcat harder to use with GPUs, giving you a slight advantage to not being at the mercy of GPU cloud hashing.

I don't know the specification of SHA-256 or SHA-512, but their output hashes are totally different for the same input. To protect from GPU cloud hashing attacks on password hashes you would use a PBKDF with a lot of iterations. Some GPU's can produce SHA-256 hashes really fast, particularly AMD GPU's, as explained below

https://en.bitcoin.it/wiki/Why_a_GPU_mines_faster_than_a_CPU#Why_are_AMD_GPUs_faster_than_Nvidia_GPUs.3F

Quote
Firstly, AMD designs GPUs with many simple ALUs/shaders (VLIW design) that run at a relatively low frequency clock (typically 1120-3200 ALUs at 625-900 MHz), whereas Nvidia's microarchitecture consists of fewer more complex ALUs and tries to compensate with a higher shader clock (typically 448-1024 ALUs at 1150-1544 MHz). Because of this VLIW vs. non-VLIW difference, Nvidia uses up more square millimeters of die space per ALU, hence can pack fewer of them per chip, and they hit the frequency wall sooner than AMD which prevents them from increasing the clock high enough to match or surpass AMD's performance. This translates to a raw ALU performance advantage for AMD:

    AMD Radeon HD 6990: 3072 ALUs x 830 MHz = 2550 billion 32-bit instruction per second
    Nvidia GTX 590: 1024 ALUs x 1214 MHz = 1243 billion 32-bit instruction per second

This approximate 2x-3x performance difference exists across the entire range of AMD and Nvidia GPUs. It is very visible in all ALU-bound GPGPU workloads such as Bitcoin, password bruteforcers, etc.

Secondly, another difference favoring Bitcoin mining on AMD GPUs instead of Nvidia's is that the mining algorithm is based on SHA-256, which makes heavy use of the 32-bit integer right rotate operation. This operation can be implemented as a single hardware instruction on AMD GPUs (BIT_ALIGN_INT), but requires three separate hardware instructions to be emulated on Nvidia GPUs (2 shifts + 1 add). This alone gives AMD another 1.7x performance advantage (~1900 instructions instead of ~3250 to execute the SHA-256 compression function).

so yeah GPU's are currently more specialized for SHA-256 than SHA-512. However, by using a PBKDF you can strengthen your password by much more than you can by switching from SHA-256 to SHA-512. PBKDF will use SHA-256 (or whatever) and iterate perhaps a hundred thousand times. So if using SHA-512 takes twice as much time for the GPU to make a hash, using SHA-256 with PBKDF with 100,000 iterations will take 100,000 times as long. Of course you could switch to SHA-512 with so many iterations, but you can always just add more to SHA-256 as well. There is no problem to make key generation from a password take X amount of time with Y hardware, and it is just as effective to use a PBKDF with more iterations as it is to switch to a new hashing algorithm.

Quote
No idea about ASIC or FPGA's though, I would assume they don't have this problem.

I don't think even GPU's have this problem theoretically, they are just not as optimized for SHA-512 as they are for SHA-256. Although it is probable that SHA-512 takes longer than SHA-256 inherently anyway, but as I said before you can use a PBKDF to make key generation take as long as you want on any given hardware.

Quote
All the encryption I've seen to make containers and the like, are using SHA-512 (Schneier also advocates SHA-512, but says there's nothing wrong with any SHA-2) while all the software implementations to use bcrypt/encrypt databases, are using sha256, probably to avoid that password spreading problem you talked about when feeding in passwords to avoid the 72 byte limit (though Password1 is now using 512)

What are they using them for though, is the important question. Also, how are they using them. It is literally impossible to use a 512 bit output for an AES-256 key, AES-256 needs a key that is exactly 256 bits. The only way you could use a SHA-512 hash for AES-256 is if you only use half of the output bits. In which case I would probably just use SHA-256, since it matches up. If I was using a password based key and wanted to make an attacker spend more time to guess passwords, I would use SHA-256 with a PBKDF with as many iterations as the user could stand. I am not positive if the entropy distribution problem actually will come into play, but from what I have read on hash functions I would be afraid that it would. A cryptographer friend said he would argue that both methods are equally as secure. I noted that he didn't say they are equally secure. I would therefore lean toward caution by using SHA-256 to key a 256 bit encryption algorithm, rather than using half the output bits of SHA-512.

Quote
Example:  $h=crypt(hash('sha256', $p),'$2y$......................');  bcrypt and scrypt make it really hard for GPUs to crack anyways. There's also this, which is a bcrypt 256 implementation to separate keys from server and encrypt the hashes as well http://sebsauvage.net/paste/?a99d7b619aa2a028#Ey6MdAyxEywI7JAox7afg7wBBSf0bh/qS6wnQ2MD1OU=

Meanwhile TC is using SHA-512, Whirlpool (512), and RIPEMD-160 hashes for AES256 keys.

Truecrypt uses those hash functions as part of its custom PRNG, it doesn't directly use them to produce keys. Truecrypt produces keying material with its PRNG, the hash functions it uses as entropy distributors (entropy diffusers they call them).

http://www.truecrypt.org/docs/random-number-generator

I can't really comment on the way their PRNG works. I would have done it a little bit differently, and more straight  forward imo. After getting the raw input from mouse position etc, I would concatenate it together into a single buffer every few seconds, then take the SHA-256 sum. Then I would take this SHA-256 sum and use it as the basis for the next round, with new raw input being concatenated to the previous SHA-256 sum, and then after a few seconds the new value being hashed, etc, for however long the user desires. Another property of a cryptographic hashing algorithm is that the output hash should contain exactly as much entropy as the input fed to it. So if I feed SHA-256 1000 bits that contain 1 bit of entropy, the output SHA-256 hash should have 1 bit of entropy. If I use this hash for the basis of the next output, and concatenate 1000 bits with 1 bit of randomness to it, when I hash this the next SHA-256 output should have 2 bits of entropy. At this rate, it will take 256 cycles to have 256 random bits. Then I would key AES-256 directly with this hash value.

Of course the hash value used to key AES-256 is not based on a password. Truecrypt generates a random key for AES-256 and then it encrypts this key with another key generated by the users password.

I wouldn't use SHA-512 because I would be too worried that the user would only accumulate 256 bits of entropy, and that they would be distributed evenly thoughout the 512 bit output, leading to the AES key only having 128 bits of entropy. Though I suppose you could use SHA-512 and XOR every pair of bits together to get a 256 bit key. Or you could take the SHA-256 value of the SHA-512 value. Using half of the SHA-512 value seems risky though. And I don't see a reason to use SHA-512 and then SHA-256 versus just using SHA-256 to begin with.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 17, 2013, 02:46 am
Actually it looks like Truecrypt is using a similar system (I just read the entire thing, before I only glanced at it), but I don't know why they have made it so much more complicated.

Quote
Random Number Generator

The random number generator (RNG) is used to generate the master encryption key, the secondary key (XTS mode), salt, and keyfiles. It creates a pool of random values in RAM (memory). The pool, which is 320 bytes long, is filled with data from the following sources:

    Mouse movements

    Keystrokes

    Mac OS X and Linux: Values generated by the built-in RNG (both /dev/random and /dev/urandom)

    MS Windows: Windows CryptoAPI (collected regularly at 500-ms interval)

    MS Windows: Network interface statistics (NETAPI32)

    MS Windows: Various Win32 handles, time variables, and counters (collected regularly at 500-ms interval)

So essentially Truecrypt is describing the buffer from the scheme I mentioned, where raw input data is added (from mouse position, etc).

Quote
Before a value obtained from any of the above-mentioned sources is written to the pool, it is divided into individual bytes (e.g., a 32-bit number is divided into four bytes). These bytes are then individually written to the pool with the modulo 28 addition operation (not by replacing the old values in the pool) at the position of the pool cursor. After a byte is written, the pool cursor position is advanced by one byte. When the cursor reaches the end of the pool, its position is set to the beginning of the pool. After every 16th byte written to the pool, the pool mixing function is applied to the entire pool (see below).

Truecrypt diverges here, after they fill the buffer up they don't ever replace it but rather they modify it. When new input comes in after the buffer is filled, they change the value of the current position in the pool to be the current position in the pool modulo 28 the new raw input.

Quote
Pool Mixing Function

The purpose of this function is to perform diffusion [2]. Diffusion spreads the influence of individual "raw" input bits over as much of the pool state as possible, which also hides statistical relationships. After every 16th byte written to the pool, this function is automatically applied to the entire pool.

Description of the pool mixing function:

    Let R be the randomness pool.

    Let H be the hash function selected by the user (SHA-512, RIPEMD-160, or Whirlpool).

    l = byte size of the output of the hash function H (i.e., if H is RIPEMD-160, then l = 20; if H is SHA-512, l = 64)

    z = byte size of the randomness pool R   (320 bytes)

    q = z / l – 1    (e.g., if H is Whirlpool, then q = 4)

    R is divided into l-byte blocks B0...Bq.
    For 0 < i < q (i.e., for each block B) the following steps are performed:
        M = H (B0 || B1 || ... || Bq)    [i.e., the randomness pool is hashed using the hash function H, which produces a hash M]

        Bi = Bi ^ M
    R = B0 || B1 || ... || Bq

Now Truecrypt divides the buffer into sections that are the size of the output of the hash function selected by the user. Truecrypt goes through each section and generates a value that is equal to the hash value of every section in the buffer, and then uses modular exponentiation to transform the current section to the current section ^ value generated by the hash function. It does this for every section in the randomness pool.

Quote
For example, if q = 1, the randomness pool would be mixed as follows:

    (B0 || B1) = R

    B0 = B0 ^ H(B0 || B1)

    B1 = B1 ^ H(B0 || B1)

    R = B0 || B1


Quote
Generated Values

The content of the RNG pool is never directly exported (even when TrueCrypt instructs the RNG to generate and export a value). Thus, even if the attacker obtains a value generated by the RNG, it is infeasible for him to determine or predict (using the obtained value) any other values generated by the RNG during the session (it is infeasible to determine the content of the pool from a value generated by the RNG).

The RNG ensures this by performing the following steps whenever TrueCrypt instructs it to generate and export a value:

    Data obtained from some of the sources listed above is added to the pool as described above.

    The requested number of bytes is copied from the pool to the output buffer (the copying starts from the position of the pool cursor; when the end of the pool is reached, the copying continues from the beginning of the pool; if the requested number of bytes is greater than the size of the pool, no value is generated and an error is returned).

    The state of each bit in the pool is inverted (i.e., 0 is changed to 1, and 1 is changed to 0).

    Data obtained from some of the sources listed above is added to the pool as described above.

    The content of the pool is transformed using the pool mixing function. Note: The function uses a cryptographically secure one-way hash function selected by the user (for more information, see the section Pool Mixing Function above).

    The transformed content of the pool is XORed into the output buffer as follows:
        The output buffer write cursor is set to 0 (the first byte of the buffer).

        The byte at the position of the pool cursor is read from the pool and XORed into the byte in the output buffer at the position of the output buffer write cursor.

        The pool cursor position is advanced by one byte. If the end of the pool is reached, the cursor position is set to 0 (the first byte of the pool).

        The position of the output buffer write cursor is advanced by one byte.

        Steps b-d are repeated for each remaining byte of the output buffer (whose length is equal to the requested number of bytes).
    The content of the output buffer, which is the final value generated by the RNG, is exported.

Truecrypt then uses this randomness pool to generate keying material, first going through some steps to transform it a final time.


I think that this is kind of an over complicated method personally. I would do something more like this:

Have the buffer that raw input is added to, every period of time (or better yet every time the buffer is filled), I would take the SHA-256 value of the buffer. Then I would totally clear the buffer, and add the SHA-256 value to it. Then as more input comes, I would add it to the buffer past the SHA-256 value, and when the buffer is filled again I would take the SHA-256 value of it again. I would do this for some number of rounds, or as long as the user desires. At the end, I would take a final SHA-256 value of the buffer. If I was only generating an AES-256 key, I would use the final SHA-256 hash for the key. However, Truecrypt is using their PRNG to generate more than the key, so I would need more than 256 bits. In this case, I would do the following:

Using the final SHA-256 output as a seed, I would then hash it out once more. If S is the original value and O1 is the hash of the original value

Ox = H(S || Ox-1)

O1..Oz would be my pseudorandom material to use for keying and other operations, where Oz is the final Ox.

The original seed is generated securely because:

A. Cryptographic hash functions preserve entropy, meaning the output of H(X) contains as much entropy as X.

Therefore, with R = raw input

H(R1) = A
H(A || R2) = B
H(B || R3) = D

D must contain as much entropy as the total entropy of R1, R2, and R3 combined.

B. Cryptographic hash functions distill entropy

If H produces 256 bits of output, feeding H(1000 non-random-input-bits + 1 random-input-bit) = 256 bit output with 1 random bit (due to preservation of entropy there is 1 bit of entropy in the output, distilled from 1001 bits to 256 bits)

C. Cryptographic hash functions distribute entropy

If H produces 256 bits of output, H(1 bit of entropy) = 256 bits each with 1/256 bits of entropy

therefore if there are 256 bits of entropy total fed to H during the seed generation process, the final value will be 256 random bits.

The final output material is secure because:

A. The seed is used to generate every 32 bytes of output

Ox = H(S || Ox-1)

Without knowing the seed value an attacker cannot use Ox to determine Ox-1 or Ox+1, because a cryptographic hash algorithm is (ideally) a one way function.

H(S) = O1 (the attacker can not determine the seed from the first output because doing so would mean H is not a one way function)

H(S || O1) = O2 (Same as above, plus the attacker can not guess O2 with knowledge of O1 unless they also have knowledge of S, and S is 256 bits of randomness)

H(S || O2) = O3

etc.

It should be safe to use randomly sized sections of output as well, since the entropy is evenly distributed by the hash function. That means just because the hash outputs A9 and A is used for the publicly viewable salt and 9 is used for the secret key, the attacker should not be able to use knowledge of A to be able to determine that the key starts with 9, since the entropy of A is the same as the entropy of 9 and the two are probabilistically independent of each other.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 17, 2013, 03:34 am
According to an article  published on 9/5/13 in USAtoday.com  NSA spent  many billions building a supercomputer that can crack any and all encryption software  >:( After reading the article I wondered if its useless to encrypt??

OH EM GEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE!!!!

Ok, the NSA have no such supercomputer because no kind of supercomputer can get round the P vs NP problem (and there may be no way around it, but no one knows right now). This would be a mathematical breakthrough MUCH larger than finding the Higgs Boson.

I have heard some people say that quantum computers imply that P = NP, although the fact that this isn't breaking news seems to indicate that perhaps the people researching quantum computers are full of shit. None of them seem to directly make such a claim, but some people take the claims they make to imply it. In computer science quantum computers are actually kind of controversial it seems to me. Traditional computer scientists seem to dismiss them in many cases, but perhaps it is just because they don't know enough about them. Even cryptographers used to dismiss them, but they seem to be more and more accepting of the fact that they are real now. I think that quantum computers kind of go beyond traditional computer science and more into the realm of advanced physics applied to computation. Certainly that is the case with quantum cryptography, which is very different from traditional cryptography and has a very physics oriented slant to it. (IE: Traditional cryptography you may scramble a plaintext and transmit it on the line, such that if it is intercepted it cannot be deciphered between location A and B. With quantum cryptography, you may use quantum teleportation to transfer a plaintext from point A to point B such that it does not exist at any point between A and B to be intercepted in the first place.)

On the other hand, I don't think it has ever been proven that prime factorization is NP-complete, so perhaps quantum computers theoretic ability to trivially factor massive numbers into primes doesn't imply that P = NP, but rather implies that prime factorization was never NP-complete to begin with. So just because a quantum computer can factor huge numbers into primes doesn't mean that there has been an answer to P vs NP, but is more likely to imply that some problems thought to be, but never proven to be, NP-complete, were actually never NP-complete to begin with.

Quote
What NSA have apparently done is weaken commercial encryption algorithms (usually by making the entropy generators less than random) so that they CAN break the encryption, but strong encryption is still strong. For instance, on a desktop pc it would take 6.4 quadrillion years to brute-force 2048bit RSA encryption. Working using conventional algorithms the D-Wave2 can compute problems 3600x faster (according to the wiki page - the only place I could find that had actual facts, no just glossy brochure crap), which still places it at taking 1.8 trillion years to brute force.

A true quantum computer with enough stabilized qubits is allegedly able to trivially break RSA and ECC and DH and most public key encryption. It is also allegedly able to cut the bit strength of a symmetric algorithm in half. It is true that right now it looks primarily like the NSA has subverted cryptography via influence over the standards as well as releasing some backdoored things, such as the PRNG dual_ec_drbg. However, the NSA is also very likely at the cutting edge of quantum computing, and that is a risk to take into account as well. On the other hand, the NSA is also at the cutting edge of traditional computing, and it is possible that their super computers are merely trying to brute force passwords and crack smaller traditional encryption keys (like RSA or DH 1,024).

Quote
Now, where quantum computers excel is in that they can execute Shor's algorithm - this can use unique properties of qubits to break encryption. Don't ask me how it works, I'm working on learning about this kind of thing, but am not that advanced yet. However, this is not just some kind of magic spell any old quantum processor can manage, there are requirements. For starters, the noise needs to be low enough, but let's assume that is for now. The main point is that you need enough qubits. 512 qubits is very respectible, but as far as I can tell you need more qubits than the number of bits in the encryption key. Most sources say twice as many, did find this which suggest RSA768 can be broken with 1154quibits - about 1.5x the bit of the encryption key:

CLEARNET
http://www.nature.com/nature/journal/v499/n7457/fig_tab/nature12290_T1.html

So, to crack a 2048bit RSA they would need around 3000+ qubits. 512qubits is respectible, but not enough.

Sounds right, nice source I have never been able to find exact numbers for how many qubits are required to break an X bit RSA key. On the other hand we should be a bit worried, because over the past few years the number of qubits in quantum computers has grown by two orders of magnitude already. If they keep up at this rate, and they only need 1.5 times as many qubits as RSA key has bits, they may be able to break even 4,096 bit RSA keys in the next couple of years.

Quote
The final point is this - even if they did have a black box that could do this, it still takes some time and resources each time. They can't just decrypt everything in real time, and even if they could they do not have the HuMint resoruces to interpret it in real-time. The more encryption used, and the better the encryption, the harder and more costly it is for them and the more they have to use discretion over who they target.

Shors algorithm can decrypt things in nearly real time. If a quantum computer exists that can crack RSA-X, it can crack RSA-X almost instantly.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: GGGreenbud on September 17, 2013, 04:18 am
    I don't think they can crack problems with the precision necessary to decode a complex message, and I'll tell you why.   These computers are built to do probability and matrix problems, the q-bits aren't real qubits in the sense that they mimic what a real qubit does.   I talked to a computer science PhD about this and he told me that what they are doing is simulating a quantum computer using absolute-zero quantum gates, which is not the same as having actual phase-dependent quantum particles to fool with. 
    Supposing I'm wrong, I don't think 512 qubits, given the limitations on keeping the whole thing stable, is enough to do it.  The more bits they have, the more unstable the system becomes and the less usable data they get back from the machine.   If they wanted to break down a message into many parts, and spend time on it, possibly, but you have to realize that these kind of supercomputers require lots of downtime for techs to run routines on them, require physical reprogramming often, and time is expensive, much like getting time on the hubble space telescope. 
    There are probably 100 analysts working terrorism or espionage cases for every one that is trying to crack a drug ring.  Do you really think the NSA is going to call up the DEA agents and say "we decrypted some msgs from Silk Road and we've got the name of a senior Admin"?  Its possible, but they would have to go to extreme lengths, and I don't think recreational drug use or even international trafficking is even on their radar, people also underestimate the backlog of encrypted data that they have been collecting- there is probably 100 computer-years worth of data they have labeled "urgent" that they will work on before they even get to anything recent.  A cold drug case is not like a cold murder case, it doesn't matter after X amount of time.  Don't get paranoid just yet, if they come out with a 4k+ STABLE qubit machine, and run it for 5-10 years, then I'll worry.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 17, 2013, 05:32 am
This is of course assuming we have properly implemented crypto, without deterministic random numbers. It seems a lot of us don't, and there's definitely some tricks being used at the NSA to lower the entropy of public key cryptography according to Schneier, who's upped his key to 4096 since 2048 RSA/OpenSSL/PGP is no longer reliable.

We're all likely running backdoored machines. Intel HW RNG is almost certainly diddled (https://www.schneier.com/blog/archives/2013/09/surreptitiously.html), ethernet cards and chips are all proprietary source, most likely backdoored (https://blogs.oracle.com/ksplice/entry/hosting_backdoors_in_hardware), toolchains and compilers are suspect and require multi signed builds to compare just to ensure they haven't been backdoored (http://cm.bell-labs.com/who/ken/trust.html) Linux code is a fucking shambles these days and we all essentially lucked out Theodore T'so who maintains /dev/(u)random prevented Torvalds and RHEL developers from forcing exclusive Intel RdRand TRNG and ditching the CSPRNG pool or else all our crypto would be completely useless. https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J

I guess it's time to start building tiny Lisp machines with FPGAs (http://www.aviduratas.de/lisp/lispmfpga/) and using TRNG from a reverse-biased PN junction powered by two 9volt batteries in a shielded box just so we can send each other provably secure messages. Either that or OpenBSD Loongson/Lemote laptops.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: bitfool on September 17, 2013, 05:40 am
Looks like nobody bothered to read the aaronson blog post I linked? Not even checked dwave in wikipedia?

Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 17, 2013, 06:32 am
looks like Truecrypt uses the same hash functions for their PBKDF as well

Quote
Header key is used to encrypt and decrypt the encrypted area of the TrueCrypt volume header (for system encryption, of the keydata area), which contains the master key and other data (see the sections Encryption Scheme and TrueCrypt Volume Format Specification). In volumes created by TrueCrypt 5.0 or later (and for system encryption), the area is encrypted in XTS mode (see the section Modes of Operation). The method that TrueCrypt uses to generate the header key and the secondary header key (XTS mode) is PBKDF2, specified in PKCS #5 v2.0; see [7].

512-bit salt is used, which means there are 2512 keys for each password. This significantly decreases vulnerability to 'off-line' dictionary/'rainbow table' attacks (pre-computing all the keys for a dictionary of passwords is very difficult when a salt is used) [7]. The salt consists of random values generated by the TrueCrypt random number generator during the volume creation process. The header key derivation function is based on HMAC-SHA-512, HMAC-RIPEMD-160, or HMAC-Whirlpool (see [8, 9, 20, 22]) – the user selects which. The length of the derived key does not depend on the size of the output of the underlying hash function. For example, a header key for the AES-256 cipher is always 256 bits long even if HMAC-RIPEMD-160 is used (in XTS mode, an additional 256-bit secondary header key is used; hence, two 256-bit keys are used for AES-256 in total). For more information, refer to [7]. 1000 iterations (or 2000 iterations when HMAC-RIPEMD-160 is used as the underlying hash function) of the key derivation function have to be performed to derive a header key, which increases the time necessary to perform an exhaustive search for passwords (i.e., brute force attack) [7].

Header keys used by ciphers in a cascade are mutually independent, even though they are derived from a single password (to which keyfiles may have been applied). For example, for the AES-Twofish-Serpent cascade, the header key derivation function is instructed to derive a 768-bit encryption key from a given password (and, for XTS mode, in addition, a 768-bit secondary header key from the given password). The generated 768-bit header key is then split into three 256-bit keys (for XTS mode, the secondary header key is split into three 256-bit keys too, so the cascade actually uses six 256-bit keys in total), out of which the first key is used by Serpent, the second key is used by Twofish, and the third by AES (in addition, for XTS mode, the first secondary key is used by Serpent, the second secondary key is used by Twofish, and the third secondary key by AES). Hence, even when an adversary has one of the keys, he cannot use it to derive the other keys, as there is no feasible method to determine the password from which the key was derived (except for brute force attack mounted on a weak password).

I would be hesitant to go that route personally because of concerns due to entropy diffusion (I used to say distribution but seems everybody calls it diffusion so time to switch my terminology. Diffusion = the input entropy is evenly distributed throughout the output) from the hash function.

Some links and short quotes from them


Quote
A class of functions called "message digests," "cryptographic checksums," etc. have a number of useful properties. They are designed for producing digital signatures, integrity checks, and so on, and to do so in the face of an adversary who wants to forge one of these. Digesters are designed in Ron Rivest's words to be secure in that, "It is computationally infeasible to find two messages that hashed to the same value. No attack is more efficient than brute force." Thus, if we hash a series of random samples, it is not practical to learn what those samples were. Note that this is the same thing as my definition of the output's being perfectly random, and thus the hash preserves the entropy found in the samples. This has the additional useful effect that many weakly entropic samples can be combined to carry entropy equivalent to the whole of the entropy of all the samples. Note that while these hashes distill entropy, they cannot hold more entropy than their size. They are bottles that you can shake up entropy in, but a 128-bit hash cannot hold 129 bits worth of entropy.

These characteristics make them excellent functions for our purposes. Common functions used today are MD2, MD4, and MD5 (done by Ron Rivest), SHA (the US government's Secure Hash Algorithm, also known as SHS, the Secure Hash Standard), GOST (the Russian hasher), RIPE-MD, and RIPE-MD160 (which are European standards for hashes).


www.iacr.org/archive/crypto2004/31520493/clean.pdf

Quote
    The tools used to derive a uniform key from these sources of imperfect ran-
domness are often referred to as randomness extractors. The amount of theo-
retical results in this area is impressive; moreover, some of the constructions
that have proven extraction guarantees are also efficient (see [Sha02] for a recent
survey). One such example is the so called “pairwise independent universal hash
functions” (also called ”strongly universal”) [CW79] which have quite efficient
implementations and provable extraction properties. In particular, [HILL99]
shows (see also [Lub96,Gol01]) that if an input distribution has sufficient min-
entropy (meaning that no single value is assigned a too-large probability even
though the distribution may be far from uniform) then hashing this input into a
(sufficiently) shorter output using a function chosen at random from a family of
strongly universal hash functions results in an output that is statistically-close
to uniform. (This result is often referred to as the “Leftover Hash Lemma”.)

Actually had some trouble digging up citations for these properties, I wish I could find the first thing I read when I first learned about cryptographic hash functions, it defined all of these properties. But hopefully these two quotes are enough to show my concern: the hash function distills randomness up to the maximum size of the output of the hash function, and it takes the possibly non-uniform randomness of the input and produces a uniformly random output. My concern about using SHA512 to produce a key for a 256 bit symmetric algorithm is that if only half of the output of SHA512 is used, perhaps only half of the randomness of the password is used, if the password contains less than 512 bits of entropy.

PBKDF2 doesn't XOR together bit pairs of the output, or take the SHA256 value of the output. It keeps running SHA512. So they really are keying AES-256 with partial output from SHA-512. I would love for someone to explain to me why entropy diffusion after hashing a password with less than 512 bits of entropy doesn't lead to a weakened key when half of the 512 output bits from the hash are used. I did ask about this in the past and someone said he would argue that using part of a SHA512 hash like this would be just as safe as using SHA256, but he didn't explain why or seem 100% certain. I would imagine it is safe or else there would be warnings about it with PBKDF2 or something I imagine, but to me it doesn't make sense.

If hashing an input uniformly distributes its entropy into the output, and the input has 256 bits of entropy, and the output has 512 bits, it seems that each bit of output has half a bit of entropy, and therefor taking 256 bits from this output to key AES-256 would have 128 bits of entropy only. Again, love for someone to explain to me why I am wrong (I wouldn't be surprised if I am, but I just don't see why), or explain to me why it is better to use half of a SHA512 hash versus just using a secure hash that produces the number of bits needed to key the symmetric algorithm in the first place.


In the case of using a hash function that produces less than 256 output bits I wouldn't see this concern, because the PBKDF can stretch the randomness of the password into an arbitrary length stream, but when using a hash function with more than 256 output bits it seems that although it can stretch the randomness of the password into pseudorandomness still, the entropy will still be diffused throughout the output bits (meaning with 256 bits of randomness in the password, you still have 256 bits of entropy in an arbitrary number of 512 bit outputs, but each of the output bits only has half a bit of entropy), which would seemingly cut the effective entropy of the password in half if it isn't enough to fill the limit of the hash function used (because 256 bits spread over 512 bits of output means each bit has half a bit of entropy, and when you use half of the final output to key the 256 bit algorithm, it means your key only has 128 bits of entropy. Or if your password has only 30 bits of entropy, the key has only 15 bits of entropy, since 30 bits of entropy diffused over 512 bits means each output bit has .05859375 bits of entropy, and .05859375 * 256 used bits = 15 bits of entropy). 

However even in the case of using a hash function with 160 bits of randomness, it seems that the limit of the security would be 160 bits. You can stretch a 160 bit seed out to an arbitrary length stream, but cracking the initial seed will always allow you to generate the entire stream. This is easy to prove, assume you have a single random bit, it is either 1 or 0. You can stretch this out indefinitely by hashing it with a counter for example, so:

H({1,0}) = O
H(O || 1) = O1
H(O1 || 2) = O2

but this only has 1 bit of security, because the attacker knows you either started with 1 or with 0. So I think you can stretch the initial entropic seed out indefinitely, but the total security of the system cannot be larger than the initial seed. So using a 160 bit hash function for the PBKDF to key a 256 bit algorithm means you cannot have more than 160 bit security.

So I am not sure how I feel about ANY of the hash functions that Truecrypt offers! Either we can use a 512 bit hash algorithm and diffusion of entropy will cut the effective keyspace of most passwords in half (it seems to me, please tell me why I am wrong), or we can use a 160 bit hash and the security of AES-256 is actually limited to 160 bits, since passwords with more than 160 bits of entropy don't contribute additional entropy to the PBKDF output . Why don't they include a 256 bit hashing algorithm??
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: bitfool on September 17, 2013, 07:41 am
"D-Wave founder Geordie Rose claims that D-Wave has now accomplished its goal of building a quantum computer that, in his words, is “better at something than any other option available.”  This claim has been widely and uncritically repeated in the press, so that much of the nerd world now accepts it as fact.  However, the claim is not supported by the evidence currently available.  It appears that, while the D-Wave machine does outperform certain off-the-shelf solvers, simulated annealing codes have been written that outperform the D-Wave machine on its own native problem when run on a standard laptop.  More research is needed to clarify the issue, but in the meantime, it seems worth knowing that this is where things currently stand."


So, stop babbling about working qm computers that can break public keys?
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kittenfluff on September 17, 2013, 09:33 am
Certainly that is the case with quantum cryptography, which is very different from traditional cryptography and has a very physics oriented slant to it. (IE: Traditional cryptography you may scramble a plaintext and transmit it on the line, such that if it is intercepted it cannot be deciphered between location A and B. With quantum cryptography, you may use quantum teleportation to transfer a plaintext from point A to point B such that it does not exist at any point between A and B to be intercepted in the first place.)

Actually, it's my understanding of quantum-cryptography that what happens is that the message is transmitted in such a way that if it's intercepted or interfered with en route that quantum interference will make it unreadable, or at least alert the recipient that the message was intercepted. That said, I just took a look at the wiki page and there seem to be several theoretical cryptographic techniques all under the banner of 'quantum cryptography'....

Quote
Sounds right, nice source I have never been able to find exact numbers for how many qubits are required to break an X bit RSA key. On the other hand we should be a bit worried, because over the past few years the number of qubits in quantum computers has grown by two orders of magnitude already. If they keep up at this rate, and they only need 1.5 times as many qubits as RSA key has bits, they may be able to break even 4,096 bit RSA keys in the next couple of years.

Quote
The final point is this - even if they did have a black box that could do this, it still takes some time and resources each time. They can't just decrypt everything in real time, and even if they could they do not have the HuMint resoruces to interpret it in real-time. The more encryption used, and the better the encryption, the harder and more costly it is for them and the more they have to use discretion over who they target.

Shors algorithm can decrypt things in nearly real time. If a quantum computer exists that can crack RSA-X, it can crack RSA-X almost instantly.

Ok, I'm not sure I made myself entirely clear. Even IF (big IF) they had a quantum processor (and I'm even more doubtful now I've read GGGreenbud's comments above re q-bits vs qubits - Shor's algorithm does require actual quantum entangled bits, not just some fancy finessing and high-level emulation. I will be following up that train of thought) and it could decrypt messages in 'real time', it would still be a far-less-than-trivial endeavor to actually decrypt everything. The D-Wave2 (which couldn't do it anyhow) is a super-cooled 10m box. There are actual physical limits to the resources they could possibly command. Long before it gets to the point that they could decrypt everything in real-time better, quantum-proof, cryptography will HAVE to come along because you can bet some scumbag fraudster is gonna get hold of a quantum box and banks need security. And, again, they cannot even review all the un-encrypted data they have now - the bottle neck is not a technological one, it's a human-resources one.... So, they may or may not be able to do it now or in the near future, but it's only useful for ensuring they get digital evidence post hoc, not that useful for catching you in the first place. But if you're so in their sights that they will spend precious time using a multi-billion$$$$ super-cooled 10m^3 quantum box to decrypt your data you are already fucked...
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: PinnacleGoods on September 17, 2013, 11:24 am
A better answer from me would have been that the NSA probably actually cannot break all encryption, even with their multi billion dollar super computer. But even assuming they can, it doesn't mean encryption is worthless. If it takes them two days to decrypt a single message, why do you think they gonna spend two of those days decrypting your order for an ounce of bud.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: PinnacleGoods on September 17, 2013, 12:21 pm
This is of course assuming we have properly implemented crypto, without deterministic random numbers. It seems a lot of us don't, and there's definitely some tricks being used at the NSA to lower the entropy of public key cryptography according to Schneier, who's upped his key to 4096 since 2048 RSA/OpenSSL/PGP is no longer reliable.

We're all likely running backdoored machines. Intel HW RNG is almost certainly diddled (https://www.schneier.com/blog/archives/2013/09/surreptitiously.html), ethernet cards and chips are all proprietary source, most likely backdoored (https://blogs.oracle.com/ksplice/entry/hosting_backdoors_in_hardware), toolchains and compilers are suspect and require multi signed builds to compare just to ensure they haven't been backdoored (http://cm.bell-labs.com/who/ken/trust.html) Linux code is a fucking shambles these days and we all essentially lucked out Theodore T'so who maintains /dev/(u)random prevented Torvalds and RHEL developers from forcing exclusive Intel RdRand TRNG and ditching the CSPRNG pool or else all our crypto would be completely useless. https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J

I guess it's time to start building tiny Lisp machines with FPGAs (http://www.aviduratas.de/lisp/lispmfpga/) and using TRNG from a reverse-biased PN junction powered by two 9volt batteries in a shielded box just so we can send each other provably secure messages. Either that or OpenBSD Loongson/Lemote laptops.

From the article referred to with "ethernet cards and chips are all proprietary source, most likely backdoored":
"What does all this mean in practice? Just like you should not run untrusted software, you should not install hardware provided by untrusted sources. Unless you work for something like a government intelligence agency, though, you shouldn't realistically worry about installing commodity hardware from reputable vendors. After all, you're already also trusting the manufacturer of your processor, RAM, etc., as well as your operating system and compiler providers. Of course, most real-world vulnerabilities are due to mistakes and not malice. An attacker can gain control of systems by exploiting bugs in popular operating systems much more easily than by distributing malicious hardware."

So, don't worry, you're hosed anyway is the conclusion. Nice.

Of course, that isn't much of a consolation for us end users.  We do have tools we can fight back with.  As long as we understand what's happening on our systems at least as well as a typical NSA employee.

NSA employees, mind you, are still government employees, not super humans.   I would take someone from a startup or an established and respected linux-heavy organization over an NSA employee any day of the week. NSA and other government employees lack experiences like going on death marches, 24 hour coding sessions, or any of that other fun stuff that comes with being dedicated to delivering the most impressive results possible while using as few resources as possible. Don't underestimate the value of operating in a free enterprise environment, it really does equip us so that we have an opportunity to defend ourselves - if we study our systems closely.

That said, crypto is clearly nothing more than the equivalent of a timer-based lock - after a certain amount of time has passed, the crypto we used will be well below the standard of the day and will be easily crackable. OTP is the way to go. Government cracking crypto has no impact on government crypto, because anything that matters is OTP.

If you don't trust the basic tools in Linux (you should...) why not boot directly to bash or something else by using init=/bin/bash or something like that on the grub kernel options line?  I've dissected grub more than once, and am totally comfortable putting my name on grub being free of backdoors... This approach seems relatively secure - I know a taxi TV service that does what I've just described - since you only bring up services as you see fit, and as necessary.

Compile SystemTap tapsets that detect any attempt to 'phone home' or perform any similar unauthorized behavior, and put them into use.  You can do some pretty amazing things with systemtap.

Concerns about the integrity of toolchains and compilers leads me to proposing a busybox-based system with uClibc in place of glibc.

Using a raspberry pi with a stripped down system might make you marginally safer than you would be otherwise. But I bet using this system will attract A LOT more unwanted attention than using a more run of the mill system would.

Just a basic Linux system can be locked down pretty securely these days...  I don't care a thing about what NSA or other supposed watchers might have inserted into Linux source code, it is audited and reviewed, and your example of Theodore T'so saving the random day strengthens my belief that the systems in place for auditing code at that level are sufficient.

I don't know if I would go with a .deb or .rpm based system, or something else, a la DIY slack style or gentoo, if security was the primary concern.  I would want SELinux and SystemTap, I have audited the source code for SELinux very thoroughly (at one point that was the only way to figure out wtf it did...) and I am comfortable deploying SELinux on hundreds of production systems with a targeted policy.  SystemTap is just awesome.

Does Linux From Scratch have some inherent problems I am unaware of?

Bottom line, you're going to have to trust someone to write some code, you can't do it all unfortunately.

OK, now an 'easy' question: what do you think about LUKS (Linux Unified Key Setup)/ dm-crypt for full disk encryption?  I think it works well for USB disks, anyone have an opinion on this topic they would be so kind as to share with me?

Thanks
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: Nightcrawler on September 17, 2013, 04:22 pm
According to an article  published on 9/5/13 in USAtoday.com  NSA spent  many billions building a supercomputer that can crack any and all encryption software  >:( After reading the article I wondered if its useless to encrypt??

The intelligence agencies WANT you to think that encryption is useless, or too difficult, or too complicated, because then you'll transmit in the clear, which is the easiest for them to read. Nothing brings a smile to their lips more than the idea that "encryption is useless". If enough people begin to believe this, they'll be popping the champagne corks in celebration.

The laws of physics are the same for us as for them. There are only the same number of hours in the day for us and for them. Granted, their resources are huge, but they are NOT infinite. If it was easy for them to crack all the current crypto, then they wouldn't be trying to subvert crypto standards, insert backdoors, and weaken things like random number generators. If they could truly crack everything they wanted, none of this would be necessary.

Right now, only a tiny minority of people use encryption -- even if only 10% of the traffic was encrypted, they would literally be overwhelmed.

Nightcrawler
4096R/BBF7433B 2012-09-22 Nightcrawler <Nightcrawler@SR>
PGP Key: http://qtt2yl5jocgrk7nu.onion/pks/lookup?op=get&search=0xB8F1D88EBBF7433B (IndyMedia .onion keyserver)
PGP Key: http://dkn255hz262ypmii.onion/index.php?topic=174.msg633090#msg633090     (Silk Road Forums PGP Key Link)
PGP Key Fingerprint = 83F8 CAF8 7B73 C3C7 8D07  B66B AFC8 CE71 D9AF D2F0

Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 17, 2013, 09:45 pm
Quote
Actually, it's my understanding of quantum-cryptography that what happens is that the message is transmitted in such a way that if it's intercepted or interfered with en route that quantum interference will make it unreadable, or at least alert the recipient that the message was intercepted. That said, I just took a look at the wiki page and there seem to be several theoretical cryptographic techniques all under the banner of 'quantum cryptography'....

Quantum cryptography is any cryptography that is based on the laws of quantum physics. The two most popular techniques used are quantum teleportation based systems (which is the direction China seems to be going), and quantum uncertainty based systems (which is the route the US seems to be going). Quantum teleportation uses entanglement to 'teleport' information from point A to point B, such that it never passes through any other points. The quantum uncertainty based systems transmit data from point A to point B such that it cannot be intercepted at any of the points in between without the interception being immediately detected by the people at point A and B. So with quantum teleportation you would teleport a symmetric key from point A to B and then use that to encrypt data which you transmit over the line as normal (or you might be able to teleport the entire plaintext), with quantum uncertainty based systems you would transmit the keying material and if you detect an interception you would generate new keying material and try again (perhaps after finding where the interception was carried out on the line, and capturing the enemy spies trying to steal your information). In either case you can do key exchange without the threat of interception, either because interception is impossible or because interception is impossible to do without it being immediately detected. There are probably other quantum encryption systems as well but these two are the most popular by far.

Quote
Ok, I'm not sure I made myself entirely clear. Even IF (big IF) they had a quantum processor (and I'm even more doubtful now I've read GGGreenbud's comments above re q-bits vs qubits - Shor's algorithm does require actual quantum entangled bits, not just some fancy finessing and high-level emulation.

Technically classical computers can do anything quantum computers can do, but it is only theoretically because you would need so many classical computers they would form a black hole before you got the power of a much smaller quantum computer.

Quote
I will be following up that train of thought) and it could decrypt messages in 'real time', it would still be a far-less-than-trivial endeavor to actually decrypt everything. The D-Wave2 (which couldn't do it anyhow) is a super-cooled 10m box. There are actual physical limits to the resources they could possibly command. Long before it gets to the point that they could decrypt everything in real-time better, quantum-proof, cryptography will HAVE to come along because you can bet some scumbag fraudster is gonna get hold of a quantum box and banks need security. And, again, they cannot even review all the un-encrypted data they have now - the bottle neck is not a technological one, it's a human-resources one.... So, they may or may not be able to do it now or in the near future, but it's only useful for ensuring they get digital evidence post hoc, not that useful for catching you in the first place. But if you're so in their sights that they will spend precious time using a multi-billion$$$$ super-cooled 10m^3 quantum box to decrypt your data you are already fucked...

yeah pretty much
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: anchientlib on September 17, 2013, 10:06 pm
I guess I better say no to that twitter account I was gonna open.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: DrMDA on September 17, 2013, 11:34 pm
I was researching quantum computers months ago and if I remember correctly I learned that it is just a misunderstanding that quantum computers can break all encryption. It is apparently only certain encryption applicable to Shors algorithm. If I remember I was left being totally comfortable with TrueCrypt and my PGP key.... One big feeling in the computer security industry though is why people even care about front door brute force attacks when the side windows are always completely open. No need for the NSA to break your PGP password when they can oh so much easily just take over your computer and watch what password you type in.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 18, 2013, 04:14 am

Note nobody should read this and get paranoid, I'm just thinking/ranting out loud.

Using a raspberry pi with a stripped down system might make you marginally safer than you would be otherwise. But I bet using this system will attract A LOT more unwanted attention than using a more run of the mill system would.

pi is a shitshow of proprietary broadcomm firmware. OpenBSD refused to make a port for it, basically because it is nothing but binary blobs. Plenty of alternatives exist like http://www.pcengines.ch or beagleboard. Also you would fake your user-agent/fingerprint, nobody would know what you're really using.

Quote
Just a basic Linux system can be locked down pretty securely these days...  I don't care a thing about what NSA or other supposed watchers might have inserted into Linux source code, it is audited and reviewed, and your example of Theodore T'so saving the random day strengthens my belief that the systems in place for auditing code at that level are sufficient.

The problem is they don't do deterministic building (bitcoin project does, in 3 different countries even), so you have no idea if the NSA backdoored Torvalds toolchains and compiler. It would be relatively elementary to do, and is certainly something the NSA (or China) would target. You would have to build from scratch using the David A. Wheeler method on Gentoo. Does that mean as drug dealers they would they care to bust us? Probably not. But we all know the lines of federal agencies have been blurred. DEA is openly lying in court where they get their "tips" from. There's also cases of mistaken identity, where you have been arbitrarily targeted because all your traffic is encrypted. They go to the trouble of breaking your end point, or whittling down your 2048 PGP key and lo and behold, a petty drug dealer. Hey let's pass this guy to the DEA. Don't assume the NSA won't toss down your information. Google "DEA NSA" and read the horror stories.

Also, keep in mind just because you aren't American doesn't mean you aren't fucked either. Look up the 5 eyes alliance. All those countries have access to NSA tracking tools and are now fully rogue.

Quote
I don't know if I would go with a .deb or .rpm based system, or something else, a la DIY slack style or gentoo, if security was the primary concern.  I would want SELinux and SystemTap, I have audited the source code for SELinux very thoroughly (at one point that was the only way to figure out wtf it did...) and I am comfortable deploying SELinux on hundreds of production systems with a targeted policy.  SystemTap is just awesome.

I would use Chromium browser in a SELinux sandbox, to protect the sandbox Chromium is already using http://danwalsh.livejournal.com/28545.html if I were still using Linux.

But remember SELinux can't protect against kernel exploits, of which there are plenty. Additionally, Linus doesn't give 2 fucks about security. In fact he called grsecurity and the like "retarded". Brad Spengler, of grsecurity and the PAX team has nothing but disdain for Torvalds. Read @grsecurity on twitter sometime. Linus is constantly sabotaging his own kernel. It's chock full of drivers from the 1990s you can exploit to your heart's content that haven't been maintained in 20yrs. You can fake emulation of an old ethernet card and load it up into the kernel, look up ancient exploits for it and go to town to get root, unless grsecurity/PaX is installed.

Kernel is now approaching 16 million lines of code. That's insane. Nobody can audit that. You will have to build a custom kernel and rip literally everything out of it except the drivers you yourself expect to use, and route modprobes to /bin/false to prevent hardware backdoors.

Something else the Intel engineers brought up was VPS systems with no human interaction, like Whonix. Tor requires CSPRNG to init encrypted (by ECC) routes. Well, whonix has this running on it's own isolated VPS with no user interaction. Remember /dev/random does not know if the entropy pool is insufficient to provide PRNG, it will do so anyways. I asked Matthew Green about this and he assumes the entropy would be very low. This means it could be possible for feds to decrypt your Tor traffic easily. Again... as petty drug dealers would they give a shit once they factor ECC (of which Schneier assumes they can do) to low enough entropy and discover just a random weed dealer? Probably not. But they might just kick that down to the DEA anyways since the origin of how you were found will be protected by lying to the court, so why not.

Yeah this sounds paranoid, but why take the chance. You can configure linux kernel to use fortuna for PRNG, and keep on using whonix without worry, or start an mp3 on boot and sample entropy from it, or just use BSD instead with yarrow and other solid PRNG built into the kernel that actually checks it's entropy pool before handing out CSPRNG unlike Linux.

I emailed Stallman and asked him what he's using these days. He's still using a Yeesong/Loongson netbook (last one was stolen in Argentina, bought a new one) with totally open firmware, initializes the machine with PMON and his chosen distro is gNewSense, He uses emacs for everything including emails and literally does nothing else on it except programming in Lisp. He still emails himself scraped webpages in plaintext preferring not to directly expose himself to exploits and advertisements, though he's buffering lynx output straight into emacs anyways I don't see how that could happen, but I'm not Stallman.

Lately been attacking OTR and browser js implementations and finding literally all crypto engineering clownshoes. It's amazing more of us aren't busted. We have really, really bad crypto tools, and terrible CSPRNGs. No wonder the cloud wants to become our feudal security lords. Everything available to us is truly garbage, with a few exceptions.

Speaking of garbage, I just found my countermail key IN FULL inside my JVM garbage collector just sitting there in memory, and it's random numbers are pencil and paper solvable. Lol. I also wrote a deterministic PRNG that overrides silently the countermail page and feeds 123123 repeating and it was accepted by the javascript execution environment without questions. After that I wrote an invisible DOM attribute that backdoors routines and just deposits the key in cleartext on my desktop. Granted these attacks require also bypassing TLS, but countermail is just using RC4 128bit, already revealed to be broken. Debian Iceweasel on my test system defaults to TLS 1.0, which is wide-open vulnerable.

Everything is broken, severely. No wonder the NSA has free reign over the internet right now.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: PinnacleGoods on September 18, 2013, 10:05 am
Also getting paranoid wouldn't really help anyone regardless.  But it's not as bad as you might think.


Agreed rasp pi is shit, never had or will possess one.  Just used to illustrate that going to extremes in one direction (albeit a bad one...) or another may yield a tiny benefit, or no benefit, to the security conscious despite best intentions and the best laid plans. Yes brcm are crap!  But who's much better? rtl? atheros? Can't think of any name that doesn't raise a grimace here...

If you could please, I would like to hear a bit more about what you like about John A Wheeler's build methods, I would appreciate the contribution :)  Agreed his "High Assurance ..."  paper is good stuff, but curious to know what items particularly impresses you.  Specifically, how are these builds more trustworthy/secure than a typical OpenBSD build? Surely Theo wouldn't Raadt...  If there's significant improvement over recommendations for the 'hardened' linux from scratch build (not unlikely) surely proposing and incorporating those improvements into their work would be appreciated by that group.

Vanilla kernels wouldn't make a good OS to build a more secure computing environment around, and as you point out, kernel development is tending towards feature creep / bloat and away from having a thin profile and even considering security implications of decisions.  Linus has been clear about his position for years, as you noted.

Devil's advocate, but if RHEL systems are so obviously not appropriate for secure deployments and horrendously insecure why are they located all over 'secure' gov't networks, including in places deemed so sensitive to security concerns that they are cut off from any larger network?  The builds from accompanying source may not be deterministic, but packages are singed with published GPG keys, and trusting a software vendor to deliver their own software is a common practice...

No need to mention how gov't 'keeps it in the family' and works together to make sure no one's rice bowl is taken away.  Sure all USA intel services should be expected to share info whether they are allowed to or not.  Things get kicked down from one state enforcement agency to the next law enforcement agency down not only in USA but also worldwide, on one level or another. Yes sure lots of eyes share tracking tool access, more than those 5 to some degree. How many can actually use some data they might find requires another list.

Still using linux? Won't ask about other options now, there's too many options out there...

SELinux isn't supposed to protect against kernel exploits, it is mandatory access controls for governing user and application access to resources like files and network ports. The whole of reactive security, which is nearly the whole of most organizations security, is weak against kernel exploits and the like.   Have you used stap before? Like dtrace some ways, but in other ways not.

Building a custom kernel with only needed drivers is not new, or hard. One option to more securely run that kernel might be tricks with modprobe. stap or SELinux could work to prevent the same threat.

/dev/random knows what it has entropy-wise. <cleartext warning - man 4 urandom - http://linux.die.net/man/4/urandom > openssl and other tools check entropy levels in /proc/sys/kernel/random/entropy_avail before nearing entropy exhaustion, why not employ a similar approach prior to offering and committing to 'provide prng' - can you please help explain what you mean by this? seed a prng pool, or create and use a brand new prng, or ?  Want to make sure we talk about the same thing, and don't talk past each other

To be clear, vps = vm ? That's what whonix has, it's a fine approach and lots of good is done there, but it is not perfect. Not that I heard any claim it is. seems offloading a large and important need for entropy to a separate system, which likely is not generating much entropy, is one way to imperfectly address a problem that I don't understand why it is not addressed elsewhere.  Is there also an assumption being made here that law enforcement can reduce how much entropy_avail a system has?

fortuna for prngs, sensible yes.

LOL ask RMS when GNU/HURD is going to take off! Damn hippy emacs user!

names of 'tech deities' will never be dropped or make much of an impression here, unless it's your name you're dropping... been working with people whose code we all (windows, linux, mac, and other OS users alike) rely on daily for a long time now.

Damn.. Bad on countermail! Java is entirely garbage waiting to be collected too often.

Everything isn't so broken that badly, or clients would have no money to pay top dollar for good consultants...

Okie, so, any feelings one way or the other on LUKS, or for that matter aboriginal linux  <cleartext warning http://landley.net/aboriginal/  > ? ? ?
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: offbeatadam on September 18, 2013, 03:27 pm
Agreed rasp pi is shit, never had or will possess one.  Just used to illustrate that going to extremes in one direction (albeit a bad one...) or another may yield a tiny benefit, or no benefit, to the security conscious despite best intentions and the best laid plans. Yes brcm are crap!  But who's much better? rtl? atheros? Can't think of any name that doesn't raise a grimace here...

Beagleboard and such are TI. I have a Pandaboard... well, a few actually, and a couple beagleboards. Started buying the pandaboard since it's the upgraded ARM spec. OMAP is nice. I tend to buy a lot of TI ICs now that I think about it. But yea, pi sucks - and it sucks that it was so well publicized. Especially when it's hardly the first of its kind... more like 5th generation, and it's obvious they didn't read any of that historical material.

Devil's advocate, but if RHEL systems are so obviously not appropriate for secure deployments and horrendously insecure why are they located all over 'secure' gov't networks, including in places deemed so sensitive to security concerns that they are cut off from any larger network?  The builds from accompanying source may not be deterministic, but packages are singed with published GPG keys, and trusting a software vendor to deliver their own software is a common practice...

Operating system decisions are hardly based on security in a business. The government is a business - that is the only thing it ACTUALLY is. I could sell something that has that "visible history" a lot easier than Gentoo. It's a name - and its a well marketed one. Notice, those emails don't go to us, and it isn't us that end up running down the halls going "Hey guys, what do you think of this?"

Windows is chosen for similar reasons, in light of the epic security disaster is has been in the past. While it's largely a bad decision according to the people who would know that its a bad decision, the problem is they aren't normally even included in that decision... and if they are, interest in their opinion is generally lost rather quickly as we tend to be boring and overly specific. The answer to our questions is money, something they don't want to give... and more heads who know how to think for themselves. Security is a marginal effort - as long as it meets some arbitrary criteria the rest is irrelevant.


Damn.. Bad on countermail! Java is entirely garbage waiting to be collected too often.

LOL. I become irritable when Java comes up anywhere I've been employed.

In my first job in something of a mentorship, my mentor referred to Java as Jawa(s). The logic being, they were the garbage collectors of the galaxy... can't trust em, and everything they do is either broken, or destined to be.

=====

Blah, I came to this thread too late. Don't have much to add beyond what was already said.

Honestly though, if you're too afraid of your encryption being broken, watch what you encrypt - consider not having the information at all. The only way something is truly secure, is if it doesn't exist at all.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: comsec on September 18, 2013, 06:33 pm
If you could please, I would like to hear a bit more about what you like about John A Wheeler's build methods, I would appreciate the contribution :)  Agreed his "High Assurance ..."  paper is good stuff, but curious to know what items particularly impresses you.

It is the only existing method to defeat the paper "trusting trust" from decades ago when it was shown how easy it would be to slide in backdoors into compilers (and now toolchains). It's similar to what the bitcoin team use to build bitcoin releases so they can be sure there isn't a backdoor being distributed worldwide where somebody can steal coins. It also stands as a solid point of reference so you can build your own and compare it to their proven build.

Tor developers now do deterministic builds as well: https://blog.torproject.org/blog/deterministic-builds-part-one-cyberwar-and-global-compromise I have no idea if Tails is doing this.


Quote
Devil's advocate, but if RHEL systems are so obviously not appropriate for secure deployments and horrendously insecure why are they located all over 'secure' gov't networks, including in places deemed so sensitive to security concerns that they are cut off from any larger network?  The builds from accompanying source may not be deterministic, but packages are singed with published GPG keys, and trusting a software vendor to deliver their own software is a common practice...

The NSA uses Fedora, which they no doubt have carefully stripped. RHEL is used mainly by corporations and foreign governments because it's free, and there's a gigantic consulting base for it so they can outsource everything. I would say it would be target #1 for all state sponsored shady hacking teams to infest with backdoors. Torvalds also has an incredible amount of problems with RHEL developers, many of them hilarious when he rages at their stupidity. They also wanted exclusive intel RdRand TRNG and to throw out the /dev/(u)random pool.. which they already did for x86/64 builds.

Quote
/dev/random knows what it has entropy-wise.

Theadore T'so, the maintainer of /dev/(u)random says it doesn't on his google+ page, which is why they include some TRNG from Intel RdRand (and other hardware TRNG if they are available on the system) to seed the pool in case entropy pool is insufficiently random like if there is was no physical user. Intel developers also said /dev/(u)random doesn't do this, which is why they came up with RdRand in the first place for the multitudes of unmanned cloud machines.

Whonix, uses haveged to provide extra VM entropy (since VMs are notoriously bad for PRNGs) however haveged seeds itself with physical events, and since Whonix-Host has no physical user just a Tor daemon that's a huge potential problem. Even worse, they claim by using tests they can verify this but since such tests are for statistical patterns, not for unpredictability they are essentially worthless. If you seed haveged with a fixed 0 you will also pass the tests with success, and your CSPRNG entropy will nonetheless be nil since it can be determined. Again asking anybody like Matthew Green if a statistical test is worth anything while auditing RNG and his answer will surely be no. This can be fixed in whonix by lot's random events like just moving the mouse pointer around for a while in the Host VM before starting Tor.

Quote
Okie, so, any feelings one way or the other on LUKS, or for that matter aboriginal linux  <cleartext warning http://landley.net/aboriginal/  > ? ? ?

LUKS is fine if your PRNG is solid. On a virtual machine this is questionable. I wouldn't trust Virtualbox devs to properly return from a page fault let alone create CSPRNG. I have no idea what Tails is using for extra entropy, I'm sure they have looked into this I'll have to check it out. Aboriginal Linux is great for testing and development, since you can quickly deploy a bunch of platforms for testing reasons I'd never use it for a security build when life in prison for trafficking across borders is on the line.

If you're interested in this, sign up for throwaway email somewhere and take the Matasano Crypto Challenges. It's how I figured out how to discover all my countermail passwords lying around in memory and feed it my own deterministic numbers masquerading as random numbers in a TLS 1.0 MITM attack.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: kmfkewm on September 24, 2013, 02:21 am
In regards to my concern about Truecrypt using a 512 bit hash algorithm to gather entropy for keying a 256 bit symmetric algorithm, I have found out why it is not insecure for them to do this. The issue was that I had a misunderstanding of what it means for a hash algorithm to evenly distribute entropy of the input into the output.

My original fear was that since a hash function evenly distributes entropy of the input to the output, that feeding a 512 bit hash algorithm with 256 bits of entropy would produce an output of 512 bits each containing half a bit of entropy, meaning taking 256 bits of this output to key a 256 bit algorithm would result in the key having only 128 bits of entropy. This is not correct, and the problem was my understanding of the meaning of "evenly distribute entropy of the input into the output".

In reality, if you feed a 512 bit hashing algorithm 256 bits of entropy, each output bit will have 1 bit of entropy, up to 256 selected bits. This is not very intuitive to me, but it makes sense when you think of it as follows. Imagine there is an algorithm that takes a fair coin flip (producing a 1 or a 0 with equal probability) and outputs the input bit followed by the opposite of the input bit. Feeding this algorithm a 1 will then produce 10 and feeding it a 0 will produce 01. Now the entropy of the coin flip is 2^1 because the result can be either 0 or 1 with equal probability. The entropy of the second bit is also 2^1 then, because it can also be a 1 or a 0 with equal probability. So after feeding this algorithm 1 bit of entropy, the output contains two bits each with 1 bit of entropy, this is what is meant by evenly distributing the entropy of the input into the output. However, note that the output string itself also contains 1 bit of entropy, because it is either 10 or 01, so 2^1 possible states. So even though each individual bit of output has 2^1 entropy, the entire output string also has 2^1 entropy. This can hold true even if the algoritm repeats the pattern, feeding it a 1 produces then 10101010101010, and each individual bit in that pattern has one bit of entropy, but the entire string also has 1 bit of entropy because it is either 10101010101010 or 01010101010101, 2^1. So when you feed SHA512 256 bits of entropy, you can take the first 256 bits and they contain 256 bits of entropy, or you can take the second 256 bits and they contain 256 bits of entropy, even though the sum entropy of the 512 output bits contains 256 bits of entropy total. Any individual 256 bit selection from the 512 bits contains 256 bits of entropy, the even distribution of entropy doesn't mean that each of the 512 bits contains half a bit of entropy.

Just thought I would clear that up.
Title: Re: Google just acquired a 512-qubit Quantum Computer. Is our encryption in danger?
Post by: postrex on September 24, 2013, 04:10 am
The DWave Quantum machines are not a threat to encryption, at least not yet.  The special quantum algorithms the machine uses so far are not even faster then optimized conventional systems at tasks the quantum computer is specifically designed for.  The day when these machines can crack any RSA key in the blink of an eye might be coming, but it's almost certainly not here yet.