Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
- Mok-Kong Shen
September 1, 2015, 11:09 am
http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/
The article doesn't seem to be much more optimistic than reports on
other well-known currently running big projects of physics, e.g.
nuclear fusion.
This means that there is in the foreseeable future no danger of the
currently used asymmetric encryption schemes being broken by quantum
computers and one could consequently concentrate one's efforts in
attempting to improve the practical security of these schemes, e.g.
in authentication of the public keys and in prevention of eventually
possible backdoors being implanted in the software or hardware involved.
M. K. Shen
Re: Researches in quantum computing seem to progress only extremely slowly
["Followup-To:" header set to comp.programming.]
The reference is that the entire sequence coming out of a PRNG only contains as
much information as its seed. For instance, a 32 bit seed means that the
entire sequence contains at most 32 bits of information. (This is true even if
the PRNG is a good one with a big state vector, and a long period.)
The seed is effectively a selector which chooses one of 2**32 different
sequences.
If you generate, say, a 1024 bit key with a PRNG that is seeded with, say, 64
bits, then it's effectively a 64 bit key. Given a known plaintext and
ciphertext pair, we only have to search a 64 bit space to recover the key.
The encryption algorithm might be RSA-1024, but it's not really because
of the weak seeding; it is a misleading lie and "security through obscurity"---
you hope that the scheme is secure because the attacker doesn't know
that a particular weekly-seeded PRNG was used.
Do you also require a reference for the claim that water is wet?
Moreover, a PRNG may have other problems with it even if the state space is
large enough and the seed has enough entropy for the given crypto use.
About stream ciphers; yes they are lot like PRNG's where the encryption key
is a seed. The seed has an appropriate size to achieve a given security
level, and no misleading claims are made about the space from which it
is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
that uses a 32 bit seed, we have the same problem: the cipher is effectively
32 bit (but the users are duped into believing that it's the 256
bit real thing).
No, key entropy does not dilute with the increasing length of an encrypted
message. Suppose we have a very good symmetric cipher against which there is
no known attack other than brute force. Suppose the attacker knows all of our
plaintext. It does not help the attacker to have a large quantity of known
plaintext. In fact using more plaintext/ciphertext pairs only slows down the
brute force search. For each key which is tried, it is enough to try a single
known ciphertext/plaintex pair.
Encryption does not work by spreading key entropy across a message.
The entropy in a key is important, however, for obvious reasons:
more entropy means a larger key space.
If an encryption algoirthm requires keys with a certain amount of entropy,
and is given less entropy, it is incompetently implemented. Its security
is weakened.
The reference is that the entire sequence coming out of a PRNG only contains as
much information as its seed. For instance, a 32 bit seed means that the
entire sequence contains at most 32 bits of information. (This is true even if
the PRNG is a good one with a big state vector, and a long period.)
The seed is effectively a selector which chooses one of 2**32 different
sequences.
If you generate, say, a 1024 bit key with a PRNG that is seeded with, say, 64
bits, then it's effectively a 64 bit key. Given a known plaintext and
ciphertext pair, we only have to search a 64 bit space to recover the key.
The encryption algorithm might be RSA-1024, but it's not really because
of the weak seeding; it is a misleading lie and "security through obscurity"---
you hope that the scheme is secure because the attacker doesn't know
that a particular weekly-seeded PRNG was used.
Do you also require a reference for the claim that water is wet?
Moreover, a PRNG may have other problems with it even if the state space is
large enough and the seed has enough entropy for the given crypto use.
About stream ciphers; yes they are lot like PRNG's where the encryption key
is a seed. The seed has an appropriate size to achieve a given security
level, and no misleading claims are made about the space from which it
is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
that uses a 32 bit seed, we have the same problem: the cipher is effectively
32 bit (but the users are duped into believing that it's the 256
bit real thing).
No, key entropy does not dilute with the increasing length of an encrypted
message. Suppose we have a very good symmetric cipher against which there is
no known attack other than brute force. Suppose the attacker knows all of our
plaintext. It does not help the attacker to have a large quantity of known
plaintext. In fact using more plaintext/ciphertext pairs only slows down the
brute force search. For each key which is tried, it is enough to try a single
known ciphertext/plaintex pair.
Encryption does not work by spreading key entropy across a message.
The entropy in a key is important, however, for obvious reasons:
more entropy means a larger key space.
If an encryption algoirthm requires keys with a certain amount of entropy,
and is given less entropy, it is incompetently implemented. Its security
is weakened.
Re: Researches in quantum computing seem to progress only extremely slowly
[For completeness I send a copy nonetheless to this group]
Am 01.09.2015 um 20:43 schrieb Kaz Kylheku:
> ["Followup-To:" header set to comp.programming.]
>> Am 01.09.2015 um 16:23 schrieb Kaz Kylheku:
>>>>
>>>>
http://www.theplatform.net/2015/07/22/google-sees-long-expensive-road-ahead-for-quantum-computing/
>>>>
>>>> The article doesn't seem to be much more optimistic than reports on
>>>> other well-known currently running big projects of physics, e.g.
>>>> nuclear fusion.
>>>>
>>>> This means that there is in the foreseeable future no danger of the
>>>> currently used asymmetric encryption schemes being broken by quantum
>>>
>>> Phew! Your python-PRNG-based security schemes is safe!
>>
>> In another thread I asked you to provide a reference to support your
>> claim there but you still kept silence on that!
>
> The reference is that the entire sequence coming out of a PRNG only
contains as
> much information as its seed. For instance, a 32 bit seed means that the
> entire sequence contains at most 32 bits of information. (This is
true even if
> the PRNG is a good one with a big state vector, and a long period.)
> The seed is effectively a selector which chooses one of 2**32 different
> sequences.
>
> If you generate, say, a 1024 bit key with a PRNG that is seeded with,
say, 64
> bits, then it's effectively a 64 bit key. Given a known plaintext and
> ciphertext pair, we only have to search a 64 bit space to recover the
key.
> The encryption algorithm might be RSA-1024, but it's not really because
> of the weak seeding; it is a misleading lie and "security through
obscurity"---
> you hope that the scheme is secure because the attacker doesn't know
> that a particular weekly-seeded PRNG was used.
>
> Do you also require a reference for the claim that water is wet?
>
> Moreover, a PRNG may have other problems with it even if the state
space is
> large enough and the seed has enough entropy for the given crypto use.
>
>
> About stream ciphers; yes they are lot like PRNG's where the
encryption key
> is a seed. The seed has an appropriate size to achieve a given security
> level, and no misleading claims are made about the space from which it
> is chosen. If we use a 256 bit stream cipher, but seed it with a PRNG
> that uses a 32 bit seed, we have the same problem: the cipher is
effectively
> 32 bit (but the users are duped into believing that it's the 256
> bit real thing).
>
> No, key entropy does not dilute with the increasing length of an
encrypted
> message. Suppose we have a very good symmetric cipher against which
there is
> no known attack other than brute force. Suppose the attacker knows
all of our
> plaintext. It does not help the attacker to have a large quantity of
known
> plaintext. In fact using more plaintext/ciphertext pairs only slows
down the
> brute force search. For each key which is tried, it is enough to try
a single
> known ciphertext/plaintex pair.
>
> Encryption does not work by spreading key entropy across a message.
> The entropy in a key is important, however, for obvious reasons:
> more entropy means a larger key space.
>
> If an encryption algoirthm requires keys with a certain amount of
entropy,
> and is given less entropy, it is incompetently implemented. Its security
> is weakened.
In my code PROVABLEPRIME
(http://s13.zetaboards.com/Crypto/topic/7234475/1 /) there is no seed
to be input by the user at all. When the Python session starts, the
system employs the current time to seed its built-in PRNG. So each
time one uses the code to e.g. generate RSA keys, one gets a different
pair by chance. Certainly one could question the security of that from
an "exact" standpoint (I mean in the sense of proofs of pure math),
but there is in "practical" crypto in general IMHO no way to take that
exact standpoint and yet have useful things done. Does e.g. AES have
an exact proof of its security? There is none, at least to my humble
knowledge.
To repeat a few points of mine in another thread: (1) if a CSPRNG were
required in the implementation of Maurer's algorithm (detailed in HAC),
the authors of HAC would have explicitly mentioned it according to the
common style of writing in such contexts, (2) the algorithm given in
HAC of implementing a CSPRNG via RSA would barely have had any
practical sense (since one has a "need" of a CSPRNG "only" in
situations where one doesn't yet have one).
BTW, I like to mention (though this is certainly not any argument of
mine here) that a copy of my code was sent to the authors of HAC
since, if I don't err, it is the first publically available
implementation of Maurer's algrorithm in any popular programming
language.
M. K. Shen
Re: Researches in quantum computing seem to progress only extremely slowly
No. It is known to be very insecure. You might get 10-20 bits of randomness
that way but not more.
Rot 13 cannot be proven to be secure, AES 256 cannot be proven to be
secure. Therefor Rot13 is as strong as AES 256. Can you see something
wrong with that logic?
Re: Researches in quantum computing seem to progress only extremely slowly
Am 02.09.2015 um 18:24 schrieb William Unruh:
I have in comment lines in my code already indicated how one could use
Python's random.SystemRandom() instead of the normal random module.
I am now preparing an update that actually uses random.SystemRandom().
I am conscious that I could never exclude the possibility of having
security problems in my codes (seeing that even professional code
writers could make errors) and therefore I always ask for critiques
and comments.
I think it is interesting to report here that, after Kylheku has
set follow-ups to comp.programming, there were a few persons who
discussed there with me. The last post I wrote to Kylheku was
asking him to clearly resolve a paradox of mine (concerning AES in
CTR), which seems to indicate in my view some posssible problems
with security arguments based on entropy in general. I hope that he
would reply to that soon. Another person, Wessel, agreed with my
calculation of entropy in the paradox but asked about my intention
in that. I explained and it seems that he has no more questions.
A third person, bartekltg, wrote (especially in his more recent
posts) arguments that IMHO are quite strange. Since he continued
to claim that my calculation in the paradox is wrong, I asked him
in a last post to similarly refute Wessel and I'll delay further
discussions with him before seeing his post to Wessel. (He nonetheless
wrote a last post to me, which I didn't answer.)
M. K. Shen
I have in comment lines in my code already indicated how one could use
Python's random.SystemRandom() instead of the normal random module.
I am now preparing an update that actually uses random.SystemRandom().
I am conscious that I could never exclude the possibility of having
security problems in my codes (seeing that even professional code
writers could make errors) and therefore I always ask for critiques
and comments.
I think it is interesting to report here that, after Kylheku has
set follow-ups to comp.programming, there were a few persons who
discussed there with me. The last post I wrote to Kylheku was
asking him to clearly resolve a paradox of mine (concerning AES in
CTR), which seems to indicate in my view some posssible problems
with security arguments based on entropy in general. I hope that he
would reply to that soon. Another person, Wessel, agreed with my
calculation of entropy in the paradox but asked about my intention
in that. I explained and it seems that he has no more questions.
A third person, bartekltg, wrote (especially in his more recent
posts) arguments that IMHO are quite strange. Since he continued
to claim that my calculation in the paradox is wrong, I asked him
in a last post to similarly refute Wessel and I'll delay further
discussions with him before seeing his post to Wessel. (He nonetheless
wrote a last post to me, which I didn't answer.)
M. K. Shen
Re: Researches in quantum computing seem to progress only extremely slowly
The advantages of a provable prime are overhyped. The probability of not
finding a prime if you use a probablistic approach are extremely small,
and algorithm for proving primality AFAIK is very slow. Already
generating primes is slow enough that people do not want to do it.
And, AFAIK if you use a non-prime in RSA you will not get the right
answers when you try to decrypt. So you will soon discover that you do
not have a real prime. Ie, speed is probably more important that
provability in this case.
So what is the speed of your implimentation vs the speed of
probabilistic approaches?
Re: Researches in quantum computing seem to progress only extremely slowly
Am 04.09.2015 um 20:32 schrieb William Unruh:
As I noted in Epilogue of the software, the time for generation
of RSA keys with moduli of the order of even 8000 bits (current
practice 2000) is well acceptable for my targeted users.
On the other hand, I am not blindly ignoring the efficiency issue.
Having better efficiency is anyway a desirable property to be
strived at for any software. Please however kindly be patient at
the moment. I am writing code to perform an extensive comparison
of the cpu-times of generation of provable primes vs generation
with the probabilistic method. But I need yet some time to collect
sufficient results, analyze them, eventually learn something
useful from them and provide some good arguments for the pros and
cons of employing the two approaches. You'll hear from me in due
course of time.
M. K. Shen
As I noted in Epilogue of the software, the time for generation
of RSA keys with moduli of the order of even 8000 bits (current
practice 2000) is well acceptable for my targeted users.
On the other hand, I am not blindly ignoring the efficiency issue.
Having better efficiency is anyway a desirable property to be
strived at for any software. Please however kindly be patient at
the moment. I am writing code to perform an extensive comparison
of the cpu-times of generation of provable primes vs generation
with the probabilistic method. But I need yet some time to collect
sufficient results, analyze them, eventually learn something
useful from them and provide some good arguments for the pros and
cons of employing the two approaches. You'll hear from me in due
course of time.
M. K. Shen
Re: Researches in quantum computing seem to progress only extremely slowly
Am 04.09.2015 um 20:32 schrieb William Unruh:
I have done a comparison. With my Python codes the mean values of
runtime obtained are as follows, where nb is the bit size of the primes
generated, tprov is the time with Maurer's algorithm and tprob is that
with Miller-Rabin test (with prior sieving with trial divisions,
different sizes of the table of small primes employed were tried and
the least runtime values listed).
nb=1000 nb=1500 nb=2000
tprov: 0.493 sec 1.739 sec 4.648 sec
tprob:
t=1 0.324 sec 1.228 sec 3.462 sec
t=2 0.340 sec 1.282 sec 3.567 sec
t=5 0.357 sec 1.297 sec 3.534 sec
t=10 0.394 sec 1.436 sec 3.926 sec
t=20 0.450 sec 1.594 sec 4.191 sec
t=30 0.517 sec 1.801 sec 4.670 sec
t=40 0.570 sec 1.945 sec 5.035 sec
It can be seen that my implementation of Maurer's algorithm starts to
have a runtime shorter than with the Miller-Rabin test at t=30 and is
superior for higher values of t. Even for t values less then 30, the
differences are only moderate and certainly not extreme.
Thus with additional consideration of the benefit of obtaining primes
that are definitely prime, the results obtained support in my view the
general use of Maurer's algorithm for generation of random primes of
the said sizes in case my coding is employed.
M. K. Shen
I have done a comparison. With my Python codes the mean values of
runtime obtained are as follows, where nb is the bit size of the primes
generated, tprov is the time with Maurer's algorithm and tprob is that
with Miller-Rabin test (with prior sieving with trial divisions,
different sizes of the table of small primes employed were tried and
the least runtime values listed).
nb=1000 nb=1500 nb=2000
tprov: 0.493 sec 1.739 sec 4.648 sec
tprob:
t=1 0.324 sec 1.228 sec 3.462 sec
t=2 0.340 sec 1.282 sec 3.567 sec
t=5 0.357 sec 1.297 sec 3.534 sec
t=10 0.394 sec 1.436 sec 3.926 sec
t=20 0.450 sec 1.594 sec 4.191 sec
t=30 0.517 sec 1.801 sec 4.670 sec
t=40 0.570 sec 1.945 sec 5.035 sec
It can be seen that my implementation of Maurer's algorithm starts to
have a runtime shorter than with the Miller-Rabin test at t=30 and is
superior for higher values of t. Even for t values less then 30, the
differences are only moderate and certainly not extreme.
Thus with additional consideration of the benefit of obtaining primes
that are definitely prime, the results obtained support in my view the
general use of Maurer's algorithm for generation of random primes of
the said sizes in case my coding is employed.
M. K. Shen
Re: Researches in quantum computing seem to progress only extremely slowly
On Tue, 1 Sep 2015 13:09:25 +0200, Mok-Kong Shen
Even if significant progress in quantum computing does occur, a number
of public key algorithms, for example the lattice-based schemes, are
known not to be vulnerable to quantum computing (or at least not any
more than to conventional computing).
As for private key algorithms, most of those will not be hit worse
than halving their effective key length by quantum algorithms, so
AES-256 should be fine (although it would be no stronger than AES-128
is now).
IOW, should quantum computing actually become practical, cryptographic
implementations will need some updates, but it will hardly be the end
of the world. Especially since we'll likely have considerable advance
notice as quantum machines start to grow large enough to be
meaningful.
Even if significant progress in quantum computing does occur, a number
of public key algorithms, for example the lattice-based schemes, are
known not to be vulnerable to quantum computing (or at least not any
more than to conventional computing).
As for private key algorithms, most of those will not be hit worse
than halving their effective key length by quantum algorithms, so
AES-256 should be fine (although it would be no stronger than AES-128
is now).
IOW, should quantum computing actually become practical, cryptographic
implementations will need some updates, but it will hardly be the end
of the world. Especially since we'll likely have considerable advance
notice as quantum machines start to grow large enough to be
meaningful.
Site Timeline
- » [CFP]: 2nd ACM Cyber-Physical System Security Workshop (ACM CPSS'16)
- — Next thread in » General Computer Security
- » [M] Laika BOSS malware detection donated by Lockheed Martin
- — Previous thread in » General Computer Security
- » Special Offers
- — Newest thread in » General Computer Security
- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware