Fujitsu Cracks Next-Gen Cryptography Standard

[HostFat]

http://www.techweekeurope.co.uk/news/fujitsu-cryptography-standard-83185

Fujitsu Laboratories said on Monday it has successfully cracked a next-generation cryptography standard known as pairing-based cryptography, breaking a world record.

Fujitsu and its partners, Japan’s National Institute of Information and Communications Technology (NICT) and Kyushu University, took 148.2 days to carry out a cryptanalysis of the 278-digit (923-bit) pairing-based cryptography, a task that had been thought to require several hundred thousand years.

Is this somehow related to the future of Bitcoin?

[Elwar]

Basically, Fujitsu just bought Bitcoin.

[Piper67]

Basically, Fujitsu just bought Bitcoin.

Using that logic, Fujitsu also just bought every bank in the G-20... not likely, but let's wait for the opinion of those who actually know something about this, shall we?

[paraipan]

watching...

[swissmate]

If they implement that on Bitcoin it will take eons to solve a block .

[Dhomochevsky]

How is that?

[Elwar]

Basically, Fujitsu just bought Bitcoin.

Using that logic, Fujitsu also just bought every bank in the G-20... not likely, but let's wait for the opinion of those who actually know something about this, shall we?

Ya, I have no idea...

[Elwar]

The article mentions that this is just a "new record". Meaning that they have done it before, just faster this time.

So the fact that they have cracked it before and Bitcoin was still considered secure would lead me to believe that this time it should not cause much of a ripple.

[rjk]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

[smickles]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

^ would be nice to know :/

[vuce]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

No. Bitcoin uses ECDSA, not pairing based crypto.

[rjk]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

No. Bitcoin uses ECDSA, not pairing based crypto.

Very good. I was fairly sure that ECDSA was not a subset of any "pairing-based cryptos", but wasn't certain. However, how does this bode for RSA/SSL/PGP/GPG/etc?

[vuce]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

No. Bitcoin uses ECDSA, not pairing based crypto.

Very good. I was fairly sure that ECDSA was not a subset of any "pairing-based cryptos", but wasn't certain. However, how does this bode for RSA/SSL/PGP/GPG/etc?

I can't say I'm overly familiar with the pairing-based crypto, but I think it's mainly used in multi-party key agreement protocols. (basically reducing the number of exchanges needed between people from diffie-hellman protocol)

Pretty much every crypto used today relies either on integer factorisation or discrete logarithm problem. Those still haven't been cracked.

[rjk]

I can't say I'm overly familiar with the pairing-based crypto, but I think it's mainly used in multi-party key agreement protocols.

Pretty much every crypto used today relies either on integer factorisation or discrete logarithm problem. Those still haven't been cracked.

Is it possible that it could affect multisignature (M of N, P2SH) transactions in any way?

[vuce]

I can't say I'm overly familiar with the pairing-based crypto, but I think it's mainly used in multi-party key agreement protocols.

Pretty much every crypto used today relies either on integer factorisation or discrete logarithm problem. Those still haven't been cracked.

Is it possible that it could affect multisignature transactions in any way?

No, ECDSA is built into bitcoin and it doesn't use anything else, as far as signing is concerned. Implementing something like a pairing-based algorithm would cause a fork in the chain. I think we're still pretty safe for a good while

[Spekulatius]

pfffew, that was close 

[runeks]

Does Bitcoin even use any of the cryptography mentioned? I didn't see a specific technology mentioned, just "pairing-based cryptography".

No. Bitcoin uses ECDSA, not pairing based crypto.

Very good. I was fairly sure that ECDSA was not a subset of any "pairing-based cryptos", but wasn't certain. However, how does this bode for RSA/SSL/PGP/GPG/etc?

I can't say I'm overly familiar with the pairing-based crypto, but I think it's mainly used in multi-party key agreement protocols. (basically reducing the number of exchanges needed between people from diffie-hellman protocol)

Pretty much every crypto used today relies either on integer factorisation or discrete logarithm problem. Those still haven't been cracked.

Isn't the point that as long as we use sufficiently large key sizes, it doesn't matter?

Ie., both ECC and RSA have been "cracked" in the sense that a private key has been deduced from a public key, but only for key sizes much smaller than the ones we use in practice. So just because an x-bit key used in "pairing-based cryptography" has been compromised, doesn't mean that this method of encryption isn't useful - only that larger keys need to be used.

[Etlase2]

Isn't the point that as long as we use sufficiently large key sizes, it doesn't matter?

No, because ECDSA and RSA are based on problems that are considered hard in today's mathematics. That does not preclude them from being easy in future mathematics. The underlying assumptions of discrete logarithms and integer factorizations are that they will remain hard, but there is no guarantee.

And then of course the whole quantum computing thing.

[BkkCoins]

To the best of my knowledge, which isn't that extensive, this just raises the bar on pairing-based cryptography in terms of bit length. But bitcoin doesn't use or have any connection with that cryptography. So unless they discovered some techniques that may be applied to ECC then it doesn't sound like it has any bearing.

It is true that shorter bit length keys in known crypto systems like ECDSA and RSA get tested and broken and this is often the basis for how long a key needs to be to keep safe. ECC keys of length 112 have already been broken but if tomorrow some researchers cracked a key length much greater then security analysts would probably recommend using longer keys rather than just giving up on ECC altogether.

From wikipedia:

The hardest ECC scheme (publicly) broken to date had a 112-bit key for the prime field case and a 109-bit key for the binary field case. For the prime field case this was broken in July 2009 using a cluster of over 200 PlayStation 3 game consoles and could have been finished in 3.5 months using this cluster when running continuously. For the binary field case, it was broken in April 2004 using 2600 computers for 17 months.

[Etlase2]

It is true that shorter bit length keys in known crypto systems like ECDSA and RSA get tested and broken and this is often the basis for how long a key needs to be to keep safe. ECC keys of length 112 have already been broken but if tomorrow some researchers cracked a key length much greater then security analysts would probably recommend using longer keys rather than just giving up on ECC altogether.

A 112 bit ECC key length is only about as effective as 56-bits of security though, and DES (56-bit) was broken in 20ish hours via brute force over a decade ago. It lasted for 20 years though.