RSA & DH at risk due to math advances, will this eventually affect elliptic curves too? I was looking into the predictions by some researchers that RSA and Diffie-Hellman may not be secure in the next few years due to advances in math and being able to calculate the discrete logarithm problem in new ways no longer making them "impossible" to solve backwards (Math Advances Raise the Prospect of an Internet Security Crisis).  Would this cause problems with Elliptic Curves?  I know they are based on different principles, but could continued advances in this area compromise ECC?  Can we consider ECC a replacement if RSA and DH were compromised?

A couple things:

This article is two years old, so take its predictions with a grain of salt.
In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon.
The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those methods do not directly apply to any standard cryptographic primitive like RSA or DH, and it is not known how to translate Joux's algorithm into an attack on these primitives. The underlying math is fundamentally different.
It's important to be cautious and conservative when choosing cryptographic primitives, but people have been predicting the death of RSA and DH for many years, and they've lasted this long.

Again, it's not known how to translate Joux's methods into a general-purpose algorithm for the discrete log problem in any other group. Thus, while it's possible for his attack to work in elliptic curve groups, there simply isn't any indication that this is the case.


Hash function composition - security level When using two hash functions, g(x)=SHA-512 and f(x)=MD5
g(x) has 512 bit output (using salt)
f(x) has 128 bit output.

Let's say that z(x)=f(g(x))
meaning the output is 128 bit long.

The Question:
Is using z(x) like using MD5 with salt? Hence, the security level is low.
Opposed to using only g(x) with salt and getting 512 bit long output?

On the one hand z(x) is a more complex function than g(x) but on the other hand 512 bit should take longer time to crack vs 128 bit.

z(x) is equivalent to f(x) for your use case. MD5 has known collision vulnerabilities, so your overall output will suffer from the same vulnerabilities. Also since the output is 128 bits long it is discarding the additional security margin of having a longer hash output.

Using SHA-512 alone is safer. If length extension attacks are an issue either use SHA-512/256, SHA3, Blake2b, HMAC, or another secure hash function immune to such attacks.


Is it safe to derive secret from alice's private key and alice's public key? I'm using secp256k1; in normal scenario alice.privateKey and bob.publicKey (or vice versa) is used to derive the same secret.

Is it safe to use alice.privateKey and alice.publicKey to derive secret as a key for encryption for alice's personal information - where alice.publicKey and encrypted blob is publicly available?

Yes, recovering the computed secret is as hard as doing it for conventional Diffie-Hellman and thus infeasible for any secure groups.

This is known as Square-Diffie-Hellman problem, the reduction to the computational Diffie-Hellman problem (CDH) can be found in this Q&A.


How does a rolling code work? I have general questions regarding rolling codes. Basically there is a sender and a receiver. Both have a sequence generator. The receiver checks if the received sequence matches the newly generated. An example used is KeeLoq.

Assuming a car opener (sender) and a car (receiver):

What happens if the sender is at another point in the sequence? Think of that the key is pressed while out of range to the car.
How does they sync the point of the sequence?
Is there any prevention to detect replay attacks? How are they implemented?

What happens if the sender is at another point in the sequence? ...
  the key is pressed while out of range to the car.

In a rolling code (code hopping) system,
the keyfob transmitter maintains a synchronization counter C,
incremented every time a button is pushed.
The car receiver stores the most recent
validated synchronization counter it has received N.

When a rolling code receiver gets a message with a keyfob serial number that seems to match one of the authorized keyfobs in its internal memory,
it extracts the keyfob's synchronization number C from the message and compares it to the most recent validated synchronization number N.

In the normal case:

C in the rolling window of acceptance -- C is more than but within "a few" codes K of the last validated transmission ( 0 < C-N < K+1 ).

When the counter C in the message is in the window of acceptance, then the car accepts that message as an authentic message,
the car overwrites N with the latest value C, and the car unlocks the doors or does whatever else the message says to do.

(As long as you hold down the button, the keyfob will repeatedly transmit bit-for-bit the same message over and over several times a second. It isn't until you let up the button and press it down again that it transmits a message with the next sequential counter number).

  So it is possible that the sender will get out of range of the k
  accepteded codes?

Yes. The AVR411 receiver defaults to WINDOW_SIZE = 100.
So with a typical AVR411 system, if the car doesn't hear 100 consecutive button-presses,
then the car will ignore the keyfob when it finally gets back in range.

With a typical KeeLoq system, if the car doesn't hear 16 consecutive button-presses, then the car will not unlock the doors on the first button-press of the keyfob when it finally gets back in range. However, if the car then hears 2 consecutive button-presses within the resynchronization window ( K < C-N < Resynchonization_Window ),
typically over a thousand button-presses,
the car will resynchronize and unlock the doors.
With a typical HCS301 system, if the car doesn't hear a few thousand consecutive button-presses,
then the car will ignore the keyfob when it finally gets back in range.

  How does they sync the point of the sequence?
  ...
  How are they
  implemented?

Before the keyfob can be used, the car must "learn" the keyfob.
Typically holding down the "learn button" ("learn switch") for 10 seconds erases the receiver's memory of every keyfob; then letting up on that button makes the receiver go into "learn mode".
Typically, pressing both the lock and the unlock button simultaneously on the keyfob makes the keyfob transmit its unique secret key to the receiver.
The receiver -- in learn mode -- memorizes the keyfob serial number(s) it hears as authorized keyfobs,
and also memorizes the secret key and the current synchronization counter N.
After everything is quiet for 10 consecutive seconds with no button presses, the receiver times-out of learn mode and goes into normal mode.

After that, that receiver -- in normal mode -- is now synchronized to the keyfobs.

The tiny amount of battery power available to the keyfob,
and the fact that the keyfob only transmits -- never receives -- makes it difficult or impossible to use many cryptographic algorithms.

For details on two popular rolling code implementations, see:

Wikipedia: rolling code
Atmel: "AVR411: Secure Rolling Code Algorithm for Wireless Link"
Microchip: "HCS301: KeeLoq Code Hopping Encoder"
Microchip: "AN661: "Code Hopping Decoder Using a PIC16C56"
Microchip: "AN1248: KeeLoq Receiver System"
Andy Carvell: RKE Analysis
Mike Szczys "Key fob programming"


Diffie Hellman Key Exchange (Finding # of bits/digits of secret key) As we know that in DH key exchange, both Alice and Bob would agree on the parameter $p$ and $g$. Next, Alice would choose a secret key $A$ while Bob would choose a secret key $B$. Alice would compute $g^A\mod p$ and Bob would compute $g^B\mod p$. They would exchange these computed values and each side would raise their secret key against the received computed value, i.e. $(g^A)^B\mod p = (g^B)^A\mod p$.

From Charlie's (external party) point of view, he would know values of $p$, $g$, $g^A\mod p$ and $g^B\mod p$. Assuming that $g^A\mod p$ and $g^B\mod p$ are 100 digits long, would he be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$?

Please do point me at any links that is relevant to this question! Thanks & Cheers!

Assuming that $g^A \bmod p$  and $g^B \bmod p$ are 100 digits long, would Charlie be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$ ?

100 digits is approximately 332 bits; if $p$ is 332 bits long, then it is known to be feasible to apply the Number Field Sieve algorithm to recover the values $A$ and/or $B$; that certainly would give him the bound.

For reference, Antoine Joux and Reynald Lercier computed the discrete log of a 431 bit (130 digit) base in three weeks.


How to exchange keys despite a MITM, using some short known password? The simple scenario is two devices on one WiFi network sitting side by side. The user can copy a short code from one device to the other to be the "password" however this code can't be too long. Let's assume it's at most 12 decimal digits. The devices will only allow one attempt so any MITM attacker will have to take a chance with only 1 in a trillion for success, which will also alert the user that he (the attacker) is there, so that would be secure "enough" for me. This is all there is, that is, there is no server which both devices have its public keys.
But how would this work? I thought of something like the following but ran into a problem. If there's a standard solution for this key-exchange scenario, please feel free to ignore the following:

I thought device d1 can create a random number in the above mentioned
range and use it as the key for Rijndael encryption of its public
encryption key but without a need for padding so that all ciphertexts
can be "decrypted" so that the MITM won't be able to brute force which is correct
by being alerted that a wrong one is wrong. The second device d2 then uses that password to
decrypt the ciphertext (which is transmitted over wifi). It then uses it
to encrypt and send d1 its (d2's) keys. The idea is that the MITM
won't know which of the trillion possible deciphered texts is correct.
And even when he (the MITM) sees the message back from d2, won't be
able to brute force it, because the plaintext of the sent ciphertext
will be random-like (because it's a public key of an unknown key pair)
and will be encrypted like the first one, where there is no padding and
therefore an attacker can't see whether they got the correct plaintext
or an error.
Unfortunately this might not work because the MITM might be able to
preemptively craft a set of keys (- a trillion decipherings of some
key) where the key used can be detected from the ciphertext, and send that key to d2 and then discover the "password" from d2's response. Can this
be done?
Also, the usual rule of not rolling out my own encryption scheme.

So, is there a safe way to exchange keys despite a MITM, using some short known password? (Preferably with forward secrecy such that brute forcing, if it takes a month, won't give the attacker the ability to start impersonating one of the devices from then on.)

This is called the Socialist Millionaire Problem. A solution for it exists, as published in this paper.
According to Wikipedia:

It is often used as a cryptographic protocol that allows two parties to verify the identity of the remote party through the use of a shared secret, avoiding a man-in-the-middle attack without the inconvenience of manually comparing public key fingerprints through an outside channel. In effect, a relatively weak password/passphrase in natural language can be used.

The protocol allows two parties to know whether or not they both share the same secret, such as a password, without transmitting it. If the other side, which may be an MITM attacker, is not able to prove that it has the same secret, then the session can be terminated before sending any sensitive information. Neither side learns any information about the secret in the process, other than the fact that the shared secrets did not match. If it succeeds and they do match, then they're MITM-free.
This technique is used in the OTR protocol. Unauthenticated Diffie-Hellman key exchange is done first, after which SMP is performed within the encrypted channel. Further communication is denied unless the other side can prove that it shares the same secret and thus is not an MITM attacker. In order to successfully perform an MITM attack, the attacker would need to either correctly guess the shared secret in its entirety by performing multiple connection attempts and re-trying on each failure without alerting anyone to the attack, or solve the discrete logarithm problem (DLP) that underlies Diffie-Hellman security, which is currently thought to be hard when correct parameters are chosen.
A simplified explanation of the protocol and its properties as used in OTR is available here.


Major code breaks in history What are the major code breaks in the history of cryptography? Which code breaks changed the face of a battle or another major event? Which one had nationwide consequences?

Besides the ones mentioned in the already existing Q&A "Examples of modern, widely used ciphers that suddenly fell?", the following major code breaks have been notable in history:

The break of the German Enigma based codes in the second world war by the team led by Alan Turing;
Project Magic / Purple;
Crypto AG's Hagelin C(X)-52, which can be regarded as a break from an operational standpoint;
The Zimmermann Telegram;
Break of Lorenz cipher;
Halske T52;
Project Venona;
Break of JN-25.


AES in CBC Mode Is totally unsecure if no defense is provided for padding oracle attack, right? Based on a lot of reading here on crypto.stackexchange.com and around the web, it seems like AES in CBC Mode is totally unsecure if no defense is provided for oracle padding attack.  And it’s not just AES, any crypto algorithm that uses CBC mode is totally unsecure if no defense is provided for padding oracle attacks.  There are even step by step videos of how to recover plain text from CBC mode ciphers.  https://www.youtube.com/watch?v=aH4DENMN_O4

All of this kinda blows my mind though given that Wikipedia says that the original padding oracle attack was published in 2002 https://en.wikipedia.org/wiki/Padding_oracle_attack
If that is the case, how can it be that AES256CBC is often touted as strong modern encryption without mentioning that implementations lacking proper HMAC validation (Encrypt-Then-MAC), or some other padding oracle defense,  are  actually not secure at all?  It kinda blows my mind if I’m understanding this correctly.  Am I understanding this correctly?

The cryptographic community moves very slowly. Take MD5 security for example. A design flaw was first published in 1996 and a collision (with more design flaws) found in 2004. Yet in 2012, authors of the Flame malware were able to use an MD5 collision to forge a Windows code-signing certificate. And we still hear of password-hash dumps that use MD5 today.

  how can it be that AES256CBC is often touted as strong modern encryption without mentioning that implementations lacking proper HMAC validation (Encrypt-Then-MAC), or some other padding oracle defense, are actually not secure at all?

This is definitely the way the community is going. I haven't done the analysis, but I'd guess that most TLS/SSL connections these days are using integrity protection (either HMAC or an AEAD mode). Integrity protection is one of the first things that gets mentioned to people on Crypto.SE too when they propose something that doesn't use it.

Something to remember is that padding-oracle attack is an online attack and very noisy. So there are a lot of use cases of cryptography where it simply does not apply. I agree with your sentiment, however. Authenticated encryption should be the default. We are getting there, but it is taking time.


Is it possible to check if a number is the product of two primes without factorizing it? I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox).

I have started to run a factorization algorithm on it, and after a few hours it still has not found any factors. But I wouldn't want to keep the algorithm running for a couple more days (or pay for a few EC2 instances to run the factorization on) only to find out that it is simply the product of three or more somewhat large prime numbers.

So, I was wondering if there was a way (even theoretical!) to check if that number was indeed the product of two prime numbers without actually having to factorize it.

Given a 613-bit integer, it is easy to check that it is composite (and we assume that's been done). It can be hard to factor, but that's feasible with GNFS, including with ready-made tools (see Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, Satya Bodduluri, Nadia Heninger's Factoring as a Service), and that's one sure way to demonstrate how many factors it has.

We can do better! We can use Lenstra's ECM repeatedly, with parameters and runtime tuned to find factors less than about 205 bits. That's within reach of the best current implementations, see Paul Zimmermann's list of ECM factoring records. If that fails, then it is a very strong indication that there is no factor 205-bit or less, thus there must be only two factors (for the product of three or more 205-bit integers has at least 613 bits). If that succeeds, we can test the primality and/or factor the rest.

I believe the tool of choice is GMP-ECM.

Edit: That is not generalizable to much larger integers. Starting about 800 bits, it becomes quite hard to tell apart those with two factors, and those with three factors of about equal size.


How to sign with RSA safely? what should I do to make my RSA signatures secure? If "plaintext RSA" is not secure, is there some sort of "RSA on steroids" I am not aware of? Could anybody tell me what is it?

I read a Wikipedia article "Digital signature". In the "History" chapter we can see:

  ...Soon afterwards, Ronald Rivest, Adi Shamir, and Len Adleman
  invented the RSA algorithm, which could be used to produce primitive
  digital signatures (although only as a proof-of-concept – "plain"
  RSA signatures are not secure

I searched for "rsa signature is not secure" but didn't find anything legible. Does anybody know why are RSA signatures are not secure and how can I make it secure by not doing "plain" signatures? Are there any tricks? The thing is that recently I implemented RSA in my code for my project and was so excited to see that I can sign and verify things with RSA...

The main modern standard RSA-based signature scheme is RSASSA-PSS in PKCS#1 v2, also standardized as IETF RFC 8017 (v2.2, obsoletes v2.1 in RFC 3447).  This is a variant of PSS proposed and analyzed by Bellare and Rogaway in 1996.

Beware: RSASSA-PSS as standardized by RSA, Inc., in the early 2000s, around the same time as Dual_EC_DRBG,* is vulnerable to collisions in the underlying hash function by virtue of using $H(r \mathbin\Vert H(m))$, instead of $H(r \mathbin\Vert m)$, which would have required of $H$ the much more modest security property (enhanced) target collision resistance.  This vulnerability to collisions led to a technique for practical HTTPS certificate forgery by academics, and to a different technique for certificate forgery used in an international incident of industrial sabotage by the United States and Israel against Iran.

If you need to get code running right now and for some reason you need to use RSA, that's the practical answer.  If you need to get code running right now but you don't actually need to use RSA, use Ed25519 instead—except for verification speed, it is an all-around faster, safer, and compacter signature scheme.

If you are studying existing code or an existing protocol that was not designed by a competent cryptographer, and you are wondering whether it uses a state-of-the-art signature scheme, you should expect it to use either RSASSA-PSS or PKCS#1 v1.5 signature.  If it doesn't, your eyebrows should be raised and whoever designed it has some justifyin' to do.

If you are intellectually absorbed by the wonders of the world of cryptography, or if like me you're a bone-eating vulture who likes blathering at strangers on the internet about things you've learned, then you should also know about full-domain hash, which was discarded essentially for political reasons among cryptographers but is easy to implement and instantiate with modern XOFs like SHAKE256, and Rabin–Williams signatures, which are more efficient with a tighter security reduction.  But make sure you know what you're trying to achieve before you go down that rabbit hole!

* I have no evidence to support a connection here, but coincidences like these are remarkably good at playing evidence in games of charades at parties.


Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key? Consider a case where we have a master key MS that is used in pseudo-random function to generate a set of pseudo-random values. Then we use key derivation function to derive a key from each of pseudo-random values. Assume all the keys are long enough (in security context).

Question: In the above scenario can I use the keys derived from the pseudo-random values (or the derived keys) as a encryption key or a key for pseudo-random function?

In other words, is there any situation where we should not consider a derived key as an actual random key?

Yes, this is exactly what KDFs and PRFs are designed for. That is, no reasonably efficient attacker will be able to tell if you used an actual random key or something generated from the KDF/PRF. This is of course assuming that your initial seed/master secret was of sufficient entropy, and the way you derive the various values are not done in a silly way.

The practice of deriving many keys from an initial master secret using a KDF is extremely common and you will find it used in almost any standard security protocol like TLS, IPsec or SSH.

  In other words, is there any situation where we should not consider a derived key as an actual random key?

Above I only considered security from the perspective of practice, i.e., where we assume that the adversary cannot run for an arbitrarily long time. However, in a theoretical model where we allow the adversary to run arbitrarily long, there are  many examples where using anything other than a totally random string will break your security. The most common example of course being the one-time pad.


Zero-knowledge identification of the majority commitment Alice is communicating with $n$ people. We do not assume that the $n$ people don't trust each other or trust Alice. Alice doesn't trust them either, and needs to assume that they will not form a coalition against her, so we assume the $n$ people cannot communicate with each other (except through Alice, if she agrees). Each of the $n$ people owns a secret bit $0$ or $1$. Let $m$ be the majority value, i.e., the bit owned by the largest number of people. (We assume that it is unique.)

Is it possible to design a protocol so that the $n$ people can commit to their value to Alice, and Alice can find out which of the people committed to the majority value $m$ without knowing what the value of $m$ is or gaining any other information about the values?

Here is one difficultly such a protocol can have: say we do have a joint computation protocol that takes $N+1$ parties (Alice and her $n$ people); at the end of the protocol, Alice gets a list of the parties in the majority without learning their secret.

Here is how Alice can attempt to cheat: extend the protocol to $N+3$ parties, and have the extra two parties be two artifical votes controlled by Alice; thing0 will submit a 0 vote, and thing1 will submit a 1 vote; other than that, the protocol continues as is.  thing0 and thing1's vote will not change which bit was in the majority; however, when Alice gets a list of the majority party; either thing0 or thing1 will be in the list; by that, Alice will learn the secret bit.

Any such protocol will need to avoid this somehow; either by simply not being extensible to N+3 parties, or having each party get a count of how many people are participating (so that they'll know that there are two extra ringers)


What does the TLS 1.2 client finished message contain? I am implementing TLS 1.2 and I'm stuck on the client finished message.

My question is: what is the size and structure of a clients finished message in TLS 1.2 when using the ECDHE_RSA_AES_128_GCM_SHA256 cipher suite.

I searched for this question and someone somewhere stated its size is 48 bytes; more specifically:

12 byte verify data
1 byte handshake type
3 byte verify data length
and 32 byte MAC

Is that really correct?

I mean: according to RFC 5246 finished messages have {verify_data[verify_data_length]} and verify_data = PRF(master_secret, finished_label, hash(handshake_messages). Also, according to RFC 5246 section 5 PRF(secret, label, seed) = P_<hash>(secret, label+seed) and P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed). So, when I compute HMAC using SHA256 for verify_data its size is 32 byte.

As a result, I'm a bit confused in relation to the verify_data size and the finished message structure. Can anyone help me to understand this and/or maybe put me on the right track somehow?

rfc5246 7.4.9 defines
verify_data as

     PRF(master_secret, finished_label, Hash(handshake_messages))
        [0..verify_data_length-1];

Note the second line; this effectively truncates the PRF output to verify_data_length octets. It goes on to say that verify_data size

  depends on the cipher
        suite.  Any cipher suite which does not explicitly specify
        verify_data_length has a verify_data_length equal to 12.

ECDHE_RSA_AES_128_GCM_SHA256 is defined in rfc 5289 which does not explicitly specify, so this default applies.

Second, someone somewhere is wrong. GCM and CCM ciphersuites do not have a HMAC on the (plaintext) record, although stream and 'block' (CBC) suites do; instead an authentication tag is added to the encrypted record by the AEAD process. Compare 6.2.3.3 to 6.2.3.1 and 6.2.3.2.


Hash-based asymmetrical encryption (not digital signature) schemes? In the Wikipedia article or another article about post-quantum crypto there's a plenty of information about hash-based signatures. But where are hash-based ecryption with pubkey?

  But, over the long-term, it's generally confidentiality (i.e. encryption) that you need to maintain and I haven't talked about post-quantum encryption at all in this post. (Maybe in the future.)

Why articles about hash-based asymmetric encryption are more hard to come by?

Possible reasons:

It is impossible and the proof is basic enough that it not deserves an article (or a question here)
It is even more impractical than hash-based signatures
It is secret and classified
It is somehow not interesting and nobody cared to research it
It is called by some other term, using which articles get found easily.
Linked articles actually do speak about them, but I don't read attentively and missed it.

It's impossible to construct a strong asymmetric encryption algorithm that relies only on the security of a hash function:

  We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n^2) queries to the oracle.

Boaz Barak, Mohammad Mahmoody-Ghidary - Merkle Puzzles are Optimal

(The proof assumes the attacker is only limited by the number of hash computations and has unlimited computational power otherwise)

The quadratic advantage of Merkle Puzzles is not sufficient to achieve the security and performance levels expected of modern cryptography. For example at a security level of 80 bits (Breaking it is equivalent to about one day of bitcoin mining), the defenders would need to exchange terabytes of information and need an hour or so of computation.

And against quantum computers you don't even get that quadratic advantage.


Security consequences of HMAC(m, K) instead of the correct way HMAC(K, m) I am wondering what is the security loss or consequences of accidentally misusing an HMAC API library in this context:

Regular, correct HMAC:

HMAC(K, m) = H((K' ⊕ opad) || H((K' ⊕ ipad) || m))

Misused HMAC (the inputs to HMAC were accidentally swapped):

HMAC(m, K) = H((m ⊕ opad) || H((m ⊕ ipad) || K))

In this context the 'm' is actually some encrypted random data (used in the standard "Encrypt then MAC" scheme) and could be considered public from an attacker's perspective. The key is 256 bits. The HMAC is HMAC-SHA-256.

Does this swapping of the inputs to HMAC mean that there is now a complete break or complete loss in security or the MAC? Is there now a length extension attack applicable? Or is it not so easily exploitable, seeing that the data is still hashed together by the outer hash?

$\DeclareMathOperator{\HMAC}{HMAC}\newcommand{\ipad}{\mathrm{ipad}}\newcommand{\opad}{\mathrm{opad}}\newcommand{\xor}{\oplus}\newcommand{\concat}{\mathop{\Vert}}$Yes.  It becomes vulnerable to collisions in $H$, if $m$ is longer than the block size of $H$, because in that case $\HMAC_m(k)$ is not actually $$H\bigl((\opad\xor m)\concat H((\ipad\xor m)\concat k)\bigr).$$  Rather, it is $$H\bigl((\opad\xor H(m))\concat H((\ipad\xor H(m))\concat k)\bigr).$$  (See RFC 2104, §2 ‘Definition of HMAC’, p. 3.)

What about single-block messages?  Well, it's unlikely that an attacker could find a structured pair of collisions $(\ipad\xor m_0, \ipad\xor m_1)$ and $(\opad\xor m_0, \opad\xor m_1)$ in $H$ for $m_0 \ne m_1$, but if they could, and if $H$ is Merkle–Damgård as is assumed in the usual HMAC security reductions (and if it's in the BLAKE2 or SHA-3 family, why bother with HMAC?), then $(m_0, m_1)$ would collide under $m \mapsto \HMAC_m(k)$ for any key $k$, enabling an attacker to immediately distinguish it from a random function or to forge messages authenticated under it.


Elliptic Curves for Pairings how can is possible to know if an elliptic curve is suitable for protocols that adopt pairing?

For example, in Certificateless Cryptography with pairing, is it possible to know if all elliptic curves (e.g. $secp160k1/r1$, $secp192r1/k1$ and so on) are suitable?

Is there a list that facilitate me to see if a curve can be adopt for Certificateless or not?

The usual curves we use in ECC are often not suitable for pairing-based cryptography (e.g. you may not find an efficient bilinear mapping), while pairing-friendly curves may not be suitable for normal ECC (e.g. in gap Diffie–Hellman groups, DDH is not hard).

There is an IETF draft on Pairing-Friendly Curves, summarizing the popular curves used in pairing-based cryptography


Proof for the SHA3 claim that 256 bit security is "post-quantum sufficient"? On page 14 of "Keccak and the SHA-3 Standardization" (February 6, 2013) it says:

  Instantiation of a sponge function

  the permutation KECCAK-f
  7 permutations: b → {25,50,100,200,400,800,1600}
  Security-speed trade-offs using the same permutation, e.g.,

  SHA-3 instance: r = 1088 and c = 512
  permutation width: 1600
  security strength 256: post-quantum sufficient
  Lightweight instance: r = 40 and c = 160
  permutation width: 200
  security strength 80: same as SHA-1

(note: emphasis mine)

Since I regard quantum cryptography to be currently walking in it's child-shoes, with a high potential of evolving substantially during the upcoming years, I just have to ask: What exactly is the base for the KECCAK claim that a security strength of 256 bits is "post-quantum sufficient"?

Well, cryptographers have been contemplating a post-quantum world for some time now.

Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the field goes back further than that: according to Wikipedia, the field was born somewhere in the 1980s.

The point is that even though quantum computing hasn't produced a usable, useful real-life quantum computer yet, it has been considered for quite a long while now. So while huge breakthroughs are still very possible, it's likely that researchers have exhausted all of the easy lines of attack. Further, since it doesn't seem that in the last 16 years any new, cryptography-threatening quantum attacks have surfaced (at least, none that I am aware of), it seems relatively safe to talk about post-quantum strength.

More to the point, the real threat against hash functions in a post-quantum world would be Grover's algorithm. Using Grover's algorithm, mounting a brute-force preimage search on an $n$-bit random oracle has time $O\left(2^{n/2}\right)$.

Although direct application of asymptotic bounds is rather imprecise, this would lead to a preimage attack in time $2^{128}$ for a 256-bit (preimage-resistant) hash function. This is still secure, and I think this is what the authors were intending when they said "post-quantum sufficient." For more information, see the question What security does Keccak offer against quantum attacks, specifically Grover's algorithm?.


What to watch for with openssl generating weak keys? (low entropy) (Disclaimer: I am regular software engineer with only basic crypto knowledge, so helpful if can be explained for a layman.)

I am concerned about generating weak keys on a shared linux box with openssl.  Some questions:

How low does entropy have to be for it to be dangerous?  If I run cat /proc/sys/kernel/random/entropy_avail i get anything from about 130 to a couple thousand. And it seems to fluctuate quickly.

Is an attack feasible at 130, or how low would it have to go (50, 10, 1, 0)?  I haven't seen any hard numbers on this.  Is the attack just theoretical or how much work would it take to break it in practice?
Does openssl block until there is sufficient entropy to generate a key?  My understanding is that /dev/urandom does not block and is the default, but /dev/random does.  I assume /dev/random is not the default for performance/consistency reasons?  Is there a flag or option in openssl where you can choose to use /dev/random instead in case you want to be sure?
On a shared box, is there any way a neighbor could deplete all the randomness on the system, and force you to generate a weak key?  It seems like blocking until there was sufficient entropy would solve this (#3) above.
Given a public/private key you've already generated - is there any way you can prove it was generated with low entropy?

Sorry for multiple questions, but they seemed related so wanted to post it as one.  Many thanks!

I will answer considering Linux OS, as being one of most popular Unix-like OS (between OSes which have urandom). If you need other OS, please, inform me.
Also I will answer using source code of random.c driver from Linux 3.3.3 Kernel, because it is one of best documentation of /dev/random mechanics. And the other is paper: Analysis of the Linux Random Number Generator, Gutterman
 2006, 086.pdf - check pages 4-6 and Figure 2.1 (slides). Then you can check The Linux Pseudorandom Number Generator Revisited, Lacharme 2012, 251.pdf paper. Even wikipedia may be helpful here.

There are several random pools in Linux:

Primary pool of 512 bytes (128 4-byte words); incoming entropy is added to it;
Secondary pool of 128 bytes to generate random for /dev/random
Urandom pool (or another secondary pool) 128 bytes for /dev/urandom

Separate entropy counters are maintained for all three pools, but usually the counter of primary pool is mean. The 'available' counter is from primary pool.

When you asks for random data, portion of entropy is extracted from the corresponding secondary pool (using one-way functions involving SHA1), then it is partly added (mixed into) to the pool. Part of extracted data is given to the consumer of random data. Both user and kernel consume entropy, e.g. kernel uses API to random driver for starting processes when ASLR is enabled (it is enabled in most distros). There is interesting example when doing several cat /proc/sys/kernel/random/entropy_avail will stole most entropy, may be this is the your case too, proof at StackOverflow. To monitor entropy_avail you should use some daemon or simple C program which will reread pool several times without process restarting.

When Secondary pool has low entropy, some portion of entropy from Primary pool is extracted (again with using of cryptographic one-way functions), then part of it is remixed back into primary pool and part of it mixed to the consuming pool.

  1) How low does entropy have to be for it to be dangerous? If I run cat /proc/sys/kernel/random/entropy_avail i get anything from about 130 to a couple thousand. And it seems to fluctuate quickly.

I would like to consider the entropy_avail as estimation of "how many high-quality random bits may I extract from random source". /dev/random gives only high-quality bits and blocks when there is no entropy left, while /dev/urandom gives bits of any quality. When entropy is high, urandom gives high-quality bits, but when entropy is zero, it gives (probably) cryptographic pseudo-random number sequence (there are better examples of such CSPRNG generators in almost every other popular OS: FreeBsd/OpenBSD,MacOS,MS). But 251.pdf (part 4.3, page 16) says "Consequently, the Linux PRNG without entropy input is assumed to be secure if the internal state is not compromised and if the three pools are initialized by an unknown value."

The maths behind the entropy estimation in Linux is analyzed here (nothing useful for software engineer, just adding and subtracting numbers).

There is source code of /dev/random and /dev/urandom driver: http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L261  (you can turn on DEBUG_ENT to see the actual working of the random driver)

 /*
  * Configuration information
  */
 #define INPUT_POOL_WORDS 128
 #define OUTPUT_POOL_WORDS 32
 #define SEC_XFER_SIZE 512
 #define EXTRACT_SIZE 10  --- 10 bytes to be extracted from secondary pools

 /*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
  */
 static int random_read_wakeup_thresh = 64;

If the available_entropy is lower than 64 bits, no one will read from /dev/random. So, this is extremely low, and smaller values will block everyone who are reading from /dev/random

 /*
  * If the entropy count falls under this number of bits, then we
  * should wake up processes which are selecting or polling on write
  * access to /dev/random.
  */
 static int random_write_wakeup_thresh = 128;

If the available_entropy is lower than 128 bits, and there are some good guys who can give us more entropy from userspace, try to ask them to do so. So, even at 128 bits of entropy we are not in best form and willing for getting help.

 /*
  * When the input pool goes over trickle_thresh, start dropping most
  * samples to avoid wasting CPU time and reduce lock contention.
  */

 static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;

If there is more than 128*28 = 3584 bits, we are refusing to add all available entropy from external sources (but some "samples" still will be mixed into out primary pool); when there is lot of available entropy, some incoming entropy will be added to secondary pool (but not to urandom pool).

  1a) Is an attack feasible at 130, or how low would it have to go (50, 10, 1, 0)? I haven't seen any hard numbers on this. Is the attack just theoretical or how much work would it take to break it in practice?

To carry out effective attack the random driver, I think, attacker should somehow predict state of the primary pool. Check part 2.2 from the http://eprint.iacr.org/2006/086.pdf - Initialization. Primary pool is initially filled on boot of system, and attacker want to predict, how it is initialized (what random sources were used and what was the input data). This may be problem in embedded devices or unattended servers or virtualized servers, which have low number of unpredictable entropy sources. The major sources are: user-generated (keyboard, mice), periphery devices (interrupts, e.g. from network), devices with hard-to-predict response times (hard disk).

Most embedded devices will have no hard disk, low number of periphery devices (and all being standard for the model), no any user sitting in front of booting PC and moving mouse and pressing keys at unpredictable moments of time. Also they may have bad-quality timing resource (entropy data from external source is 32 bits of timestamp and 32 bits of attributes; if you can measure timestamp only according to 32kHz quartz you are in bad situation, much better is to use clock tick counter or modern Intel/AMD CPU, which is 3GHz with some hard-to predict variability).

Embedded devices have standardized setup with standard flash image (usually not updated at whole live time of device), and some devices or Read-only bootable medias (Knoppix, OpenWRT) misimplement saving/restoring of entropy at boot/shutdown. Right implementation is to save 512 bytes from some random to persistent storage at shutdown and feed them back into /dev/random early at boot time (there is also comment here in linux sources: Ensuring unpredictability at system startup; /etc/rc.d/init.d/random script in SysV-era startup systems).

There is fresh overview of some embedded problems and where to search good randomness on them: http://cseweb.ucsd.edu/users/swanson/papers/Oakland2013EarlyEntropy.pdf The conclusion of the work: "Randomness is a fundamental system service. A system
cannot be said to have successfully booted unless it is ready
to provide high-entropy randomness to applications."

I think the most dangerous thing is to generate some keys early after boot on them of in known moments of time on highly embedded device. To hack the keys, hacker is needed to backpredict all entropy sources and to model primary pool state and secondary pool state at the time when key was generated. This task is hard, but sometimes it is easier then attack the key itself. I can't show examples of urandom attacks now, but I think they are exist for some vulnerable installations.

Also I think that debian's edition of openSSL was more fatal than bad random quality: http://www.schneier.com/blog/archives/2008/05/random_number_b.html http://xkcd.com/221/ There were possible only around tens-hundreds thousands of keys for every fixed RSA key size, because urandom input was disabled and the only and best available entropy input for openssl was the process ID, or PID, which is usually limited to 32-65 thousands on linux.

  2) Does openssl block until there is sufficient entropy to generate a key? My understanding is that /dev/urandom does not block and is the default, but /dev/random does. I assume /dev/random is not the default for performance/consistency reasons?

openssl will not block (I think, didn't check on modern versions), because there is no clear way to application to detect moment when urandom had too low entropy and switched to almost-fully PRNG mode. There are only several ioctls on /dev/urandom to read avaliable_entropy. openssl only tries to use own PRNG, which is seeded by current time and openssl's pid  and data from urandom or from RANDFILE.

http://lxr.linux.no/linux+v3.3.3/drivers/char/random.c#L109

 109 * The two other interfaces are two character devices /dev/random and
 110 * /dev/urandom.  /dev/random is suitable for use when very high
 111 * quality randomness is desired (for example, for key generation or
 112 * one-time pads), as it will only return a maximum of the number of
 113 * bits of randomness (as estimated by the random number generator)
 114 * contained in the entropy pool.
 115 *
 116 * The /dev/urandom device does not have this limit, and will return
 117 * as many bytes as are requested.  As more and more random bytes are
 118 * requested without giving time for the entropy pool to recharge,
 119 * this will result in random numbers that are merely cryptographically
 120 * strong.  For many applications, however, this is acceptable.

So, as says the source of random and urandom, you should not generate long-term keys from urandom, but still can use it to generate sessions keys for doing something not valuable (e.g. session key for SSL to facebook to view some more images with cats).

And when you are asking about openssl key generation, you should define what is the key to be generated. If it is session key for TLS, and you are on server, then using of /dev/random will limit how much clients can connect (there were no so much entropy and /dev/random will block, I think this is one of reasons to use urandom in openSSL).

But when you are generating some 4096-bit RSA key for 20-year SSL certificate, you want to use machine with good sources of external entropy, correct saving/restoring of entropy around reboots and which was used by human for some time.

Actually it is better to generate more valuable keys when true hardware random sources are available (not the Linux LRNG - PRNG), for example some balanced thermal noise measuring scheme (take only the lowest precision bit of Analog-to-digital converter - ADC). There is good hardware random source (thermal noise of loop of invertors with AES of their output) even in modern Intel CPUs (may be in VIA's cpus too, dont' know about AMD or ARM), check the /dev/hwrng device on your servers. Update There are possible flaws in some HW RNG (paper 2013) which are very hard to check, because the flawed random data is encrypted by private key of device maker.

And the only right way of working with high-valuable keys - is to generate them on (inside) certified HSM (Hardware security module) and keep them in full version (full private key) only inside tamper-resistance HSM (try to open such HSM's case, or remove their battery and your private key will evaporate. Funny case is when the key was the most master key of some bank - millions of PIN-codes may be lost in a moment...).  Extraction of the private key is allowed only as splitted form  - when there are N parts of key distributed around security officers (every part may be encrypted under officer's key) and K of parts are needed to reconstruct original key (e.g. via Shamir's scheme).

The main rule is to estimate the value of the information (e.g. your private photo costs around hundreds-thousands of money; but the SSL certificate of google or facebook costs billions of money), how long the information should be kept secure and how much will be invested to break your information. E.g. It may cost around 100-500 thousands money to setup a rubber-hose cryptanalysis (stealing somebody or something who knows/can access the secret/contains the secret and apply garage wrench/expostulations/soldering iron to get the secret -- soldering iron should be used only to unsolder flash memory chip from flashcard, not to something else), so the HSM and splitted backup of key is the only variant for valuable keys of banks and IT-giants.

  2b) Is there a flag or option in openssl where you can choose to use /dev/random instead in case you want to be sure?

There is a hack to force openssl to use data from /dev/random: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=88728

   dd if=/dev/random bs=1 count=1024 of=filename;
   export RANDFILE=filename
   # use openssl here

(you can verify with strace that openssl actually opened the "filename" to get random and did not open /dev/urandom)

  3) On a shared box, is there any way a neighbor could deplete all the randomness on the system, and force you to generate a weak key? It seems like blocking until there was sufficient entropy would solve this (#3) above.

There is a way to deplete most randomness, (even remotely, via TCP-syn cookie generation, see section 3.4 of 086 paper; around 64-128 bits are reserved to be available only to /dev/random, page 18 of 251.pdf). But even when depleted, neighbor can't predict your generated key via urandom cryptographic weakness only by listening to /dev/random and urandom. Both of you will get partial SHA1-s of different parts of SHA1 of pools (each refilled with parts of SHA1 from primary pool), and no one of your should be able to reconstruct state of primary pool. Worst case is when using urandom and there is 0 available_entropy (this may be bit hard to achieve). And even in this case your will get cryptographic pseudo-random generator with unknown seed. The attacker is forced both to hack recursive SHA1 and to precisely guess seed (128 bytes of random information if the entropy is depleted or 512 bytes of primary pool in non-depleted case). This task is unbelievable to be solved even when there is only one user in system which got all output of urandom exclusively (if he still have no primary pool contents at some time).

Root of shared machine can do everything: write kernel module to dump state of primary/secondary pool; emulate that there is 16 millions bits of available entropy while /dev/random will output in loop something like SHA1("THIS IS TRUE RANDOM,BELIEVE ME"); steal memory dump of your openssl process to dump the key; read your stored on the fs private key;  intercept the key presses sent from you to "your" openssl as passphrase to decrypt your safely stored private key. And the clever neighbor if he is the Wolf in sheep's clothing, will try to get root access to get your keys.

Clever attacker on shared machine may try to install side-channel attack against your crypto library and crypto algorithm, and there are actual attacks, e.g. using precise cache measurements (Bernstein 2005: "Cache-timing attacks on AES"), even if he lives in other virtual machine. This was one of reasons to e.g. move AES crypto inside the Intel CPU as separate hardware block not prone to cache side-channel leak.

So, don't use public/shared machines or machines out of your control (you should be root or somebody reliable should be) to do crypto with valuable information.

  4) Given a public/private key you've already generated - is there any way you can prove it was generated with low entropy?

I think no, if pools were correctly initialized, and their contents is kept secure (no root attacker).

In some very bad embedded installations without timekeeping (device boots to 1970), without pool saving/restoring (or with too late restoring, after urandom read, like in some ubuntus), without any random inputs before key was generated; when keys were generated by some startup script; then attacker may model the state of pool and regenerate the same keys.

And there is a paper with searching of weak keys generated on devices with low entropy: https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices". They detected bad keys ... by scanning millions of devices and comparing their keys:

  In the case of TLS, at least 5.23% of hosts use manufacturer default keys that
  were never changed by the owner, and another 0.34% appear to have generated the same keys as one or more other hosts due to malfunctioning random number generators.

And by checking for weakness in keys; again - by comparing a lot of scanned keys, for RSA they found many modules N1 and N2 where N1=p1*q1 and N2=p1*q2. I understand this situation as there are weak keys, but you can't distinguish weak key from good key. But if the key was generated from fixed low-entropy device state (first boot, early generation), then there is some probability to find another device (same HW platform) which generated same p or q as first device (if both, N will be the same).

  Even more alarmingly, we are able to compute the private keys for 64,000 (0.50%) of the TLS hosts and 108,000 (1.06%) of the SSH hosts from our scan data
  alone by exploiting known weaknesses of RSA and DSA when used with insufﬁcient randomness. In the case of RSA, distinct moduli that share exactly one prime factor will result in public keys that appear distinct but whose private keys are efﬁciently computable by calculating the greatest common divisor (GCD).

DSA requires the "ephemeral key k" to be generated with lot of entropy. k should not repeat for different messages, but some k were same.

  Nearly all (vulnerable hosts) served information identifying them as headless or embedded systems, including routers, server management cards, ﬁrewalls, and other network devices. Such devices typically generate keys automatically on ﬁrst boot, and may have limited entropy sources compared to traditional PCs

  .. Linux’s random number generator (RNG) can exhibit a boot-time entropy hole that causes urandom to produce deterministic output under conditions likely to occur in headless and embedded devices.


Is only one shared secret generated by ECDH per key pair? I'm confused about ECDH. Using their public keys and private keys, two entities can arrive on a shared secret. But from the equations I've seen, it looks like ONLY the numbers present in their key pairs are used to do this, so it would seem that if the shared secret is compromised, then they that particular pair of key sets can't be used again because they would arrive upon the same number as before. Do I have this right?

It sounds like you are thinking of performing static-static Diffie-Hellman. If that is performed naively then it will indeed derive the same secret time and time again. At least one of the key pairs needs to be non-static or ephemeral, or an additional variable (nonce) should be introduced.

For instance in NIST SP 800-56A there is section 6.2.1: "Initiator Has a Static Key Pair and Generates an Ephemeral Key Pair; Responder Has a Static Key Pair, C(1, 2)" for the former and section 6.3: "6.3 Scheme Using No Ephemeral Key Pairs, C(0, 2)" for the latter.

Usually however both key pairs are ephemeral and DH is mainly used for key agreement, relying on another primitive (such as ECDSA or RSA signatures) to add the authentication. If one of the key pairs is newly generated then the resulting keys should be indistinguishable from random (especially if the secret is put through a Key Derivation Function or KDF).

So yes, you have this right, but only for a naive implementation with two static key pairs. The underlying techniques explained above are valid for both Diffie-Hellman (DH) as for Elliptic Curve Diffie-Hellman (ECDH).


Cipher Block Chaining I don't want the answer to this problem, I just want to understand the steps that need to be followed to solve it. Maybe an example could help.

Problem

We use $\mathbin\Vert$ for  concatenation.

Let $P_1 \mathbin\Vert P_2$ be a message that is two blocks long, and let $P'_1$ be a message that is
one block long.

Let $C_0 \mathbin\Vert C_1 \mathbin\Vert C_2$ be the encryption of $P_1 \mathbin\Vert P_2$ using CBC mode with a
random IV and a random key, and let $C'_0 \mathbin\Vert C'_1$ be the encryption of $P'_1$ using CBC
mode with a random IV and the same key.

Suppose an attacker knows $P_1 \mathbin\Vert P_2$ and
suppose the attacker intercepted and thus know $C_0 \mathbin\Vert C_1 \mathbin\Vert C_2$ and $C'_0 \mathbin\Vert C'_1$.
Further suppose that, by random chance, $C'_1=C_2$.

Show that the attacker can compute $P'_1$.

The problem suggests that the encryption does not use padding, and $C_0=\mathit{IV}$, $C_0'=\mathit{IV}'$. Then
$$E_k(C_0\oplus P_1) = C_1$$
$$E_k(C_1\oplus P_2) = C_2$$
$$E_k(C_0'\oplus P_1') = C_1'$$
You also have
$$C_1'=C_2$$
That is enough to find $P_1'$.


Where have all the cypherpunks gone? In 1992, cypherpunks was created as a mailing list for activists advocating for cryptography.

Arguably, the cypherpunks mailing list was the foundation for the movement and the centre of it all.

However, the original list is dead. All I really know of is the moderated cryptography list.

Where have all the modern cypherpunks gone?

A few relevant mailing lists:

cypherpunks@cpunks.org
cryptography@metzdowd.com (moderated)
cryptography@randombit.net
liberationtech@lists.stanford.edu

Other crypto mailing lists with a narrower technical focus:

messaging@moderncrypto.org
curves@moderncrypto.org
cfrg@irtf.org
tls@ietf.org


Not Using RSA In OT1/2 Oblivious Transfer? I was reading Oblivious Transfer (Wikipedia) and the 1-2 oblivious transfer. I was confused why RSA was needed. Why wouldn't this work?:

A:m1, m0

A:x1, x2 -> B

B:k, b

B:Xb+k -> v -> A

A:Xb+k-X1, Xb+k-X2 -> k1, k2

A:m0+k0, m1+k1 -> m'1, m'2 -> B

B:m'b-k -> mb

A:Xb+k-X1, Xb+k-X2 -> k1, k2

  A:m0+k0, m1+k1 -> m'1, m'2 -> B

B knows Xb+k (transmitted it in a previous message), X1, X2 (A sent those), hence he can compute k1, k2.

Hence, he can reconstruct both m0, m1, hence the protocol doesn't have the security properties we're looking at...

Now, you don't have to use RSA, however you really do have to use something that has some cryptographical properties.  After all, Oblivious Transfer is provably impossible between two computationally-unbounded entities, hence for OT to be possible, we need to use something that a real entity can't solve (but an unbounded entity can); RSA is one such problem (but certainly not the only one).


Under which conditions would it be OK to use “H(pass||data)”? I understand that the main motivation for HMAC is extension attacks.  If data always has content-length either implicit in the app or even explicitly put into the hash, I get the impression that HMAC is not necessary.  The motivation is to allow password based encryption of keys, using widely available primitives, and periodic rotating of master-password without re-encrypting data (but re-encrypting keys):

file.name = "foo.txt"
file.iv = freshRandom256Bits()
filekey = freshRandom256Bits() #only master learns this
#encrypted key
file.encryptedKey = sha256(masterpwd+":"+file.iv) ^ filekey
#make it hard to forge data
file.auth = sha256(masterpwd+":"+file.owner+":"+file.encryptedKey)
#write data stream and file meta, then filekey goes out of scope
writeEncryptedIO(file, filekey)

In this case, the encryptedKey has a known length.  In that case, HMAC is not strictly necessary, no?  If I did use an HMAC variant like:

$$h(k || h(k || data))$$

Does it really buy me anything? Is it OK to omit the XOR with constants that are prescribed?  I'm under the impression that the whole reason HMAC is good is that it solves the extension problem by making the thing appended to k be of a known length.

I think the attack by Preneel and van Oorschot (MDx-MAC and Building Fast MACs from Hash Functions, CRYPTO'95) in Proposition 4 applies. It was cited by PulpSpy in reply to my question about H(pass||length(data)||data). With fixed-length data, that amounts to a known suffix for the key.

Proposition 4 states in a nutshell that for a generic construction which generally covers H(…||data||…) where H is an $n$-bit hash function, there is an attack that allows the attacker to replace some trailing blocks. The attack does however require about $2^{n/2}$ known text-MAC pairs, which is not feasible with a 256-bit hash. So this 20-year old result exhibits a theoretical attack. I don't know if there are more recent results that show a more practical attack.


What are unified addition and differential addition in elliptic curve point arithmetic? A lot of papers use these terms but I do not find a proper explanation of them. Can somebody tell the meaning / difference / intuition / application and if possible with an example.

Unified addition means that the formula you use for adding two points doesn't depend on whether they are equal. Simplifying point addition in the Weierstrass form somewhat $s=(y_A-y_b)/(x_A-x_b)$ when $A\neq B$ - this is "Adding". Otherwise $s=(3x_A^2-p)/{2y_A}$ when doubling a point.

The implementation of these steps would normally involve different code paths and this can lead to problems as information about the private key is leaked if you can monitor the power consumption or timing to work out which path was taken even if you can't see the numbers involved. See section one of Barbosa & Page. Also, Bernstein ,on page 3 talks about a stronger but related property called "completeness".

Page 15 of the same Bernstein paper explains "differential additions". Another Bernstein quote is

  Differential addition chains (also known as strong addition chains, Lucas chains, and Chebyshev chains) are addition chains in which every sum is already accompanied by a difference.

They are used to support fast addition on elliptic curves in the Edwards form.


What if an AES GCM nonce overflows and collides with the GHASH nonce (0^128)? When using AES in GCM mode, the GHASH function uses E(0^128) as the initial value for H, the authentication key. The IV, for the underlaying CTR mode, is initialized with:

[prefix (application nonce)] [initial_counter (4 byte counter)]

This initial counter starts at ...02, like explained here. I'm guessing this is done to prevent a collision with the GHASH function.

It's known that letting a nonce overflow is very, very bad, because repeating a nonce completely breaks GCM mode. But what if the prefix is all zeroes, and the counter overflows only to 0xffffff+1 (0^128)? You'd have one block that's xor'ed with the same value as the authentication key. Would this break GCM?

This is not allowed.  An AES-GCM implementation that accepts messages longer than $2^{39} - 256$ bits, i.e. $2^{32} - 2$ blocks, is broken.  A protocol that is defined in terms of AES-GCM on messages longer than $2^{39} - 256$ bits is nonsensical.

Protocols shouldn't be defined in terms of messages that long anyway because an adversary can waste the receiver's resources by sending an obscenely long message.  If you allow terabyte-long messages, an adversary can waste a terabyte of memory before you realize it's a forgery and drop it on the floor.

Instead, you should break messages up into units no longer than you want to have to buffer in memory before you can decide to drop forgeries on the floor, like 1500 bytes for an IP packet, or 64 KB for a TCP segment, or maybe a megabyte if appropriate for your application.

But let's suppose you did have a broken protocol that violated the rules of AES-GCM and a broken implementation that let it happen.  What happens if you do this—encrypt a message of ${>}2^{32} - 2$ blocks, with the counter truncated at 32 bits and wrapping around?  Then:

An adversary who knows the first block of plaintext can solve for the GHASH authentication key and forge arbitrarily many additional messages.
An adversary who knows the third block of plaintext can decrypt block number $2^{32}$ of the plaintext.

If the counter carries into the nonce, rather than being truncated at 32 bits, then it is a slightly different known-plaintext attack—e.g., enabling decryption of the first block of the next message, assuming sequential message numbers for the nonce, rather than block $2^{32}$ of the same message.

In brief, don't do it!


How can comparision like (>=,==) be done using homomorphic encryption? Since we know that Homomorphic encryption allow computation on encrypted data. Let two n-bit integers $(x,y)$ are encrypted using some LWE public key cryptography. For example - if $x'= HEnc(x,pk)$ and $y'= HEnc(y,pk)$, Finding $Max(x',y')$ or $Min(x',y')$ or $Equal(x',y')$ the above comparison is necessary.

Now, we need to perform comparison (>=,==) operation homomorphically. How can we do this? Can anyone describe this with example?

You'll have to write the function you are trying to calculate as a polynomial in the two inputs $x$ and $y$. If you are working over the field with $q$ elements as plaintexts, you have to calculate for equality the polynomial $(x-y)^{q-1}$. Greater-than-or-equal (however you define that for finite fields) will be even more complicated.


Why do we only encrypt nounce + counter in Counter Mode? I do not understand, what the advantage is in only encrypting the nonce + Ctr and XORing this to our plaintext, instead of encrypting everything. (If our block cipher can be easily decrypted)

What would be the other downsides of turning

$c_i = E_k(n + i) \oplus m_i$

into

$c_i' = E_k((n + i) \oplus m_i)$

This should prevent flipping a bit without destroying the entire block, right?

This should prevent flipping a bit without destroying the entire
  block, right?

Yes it does that, but at the cost of loosing security similar to ECB.

So let's go through through the security game for eavesdroppers and for the sake of simplicity choose $n_1=0$ and $n_2=2^{32}$.

The challenger generates a key $k$.
The adversary generates two messages of the same length $m_0=m\parallel (m+1)$ and $m_1=m\parallel m$ for an arbitrary choice of $m$ and submits them.
The challenger encrypts them and returns $c_b=n_b\parallel \operatorname{CTR'}_k(m_b)=n_b\parallel c'\parallel c''$ for a uniformly chosen $b\in\{0,1\}$.
The adversary checks whether $c'=c''$, if yes, 0 is returned, else 1 and this answer is always right and thus security against eavesdroppers (!) is fully broken.

While the above is nice and simple, it requires predictable nonces to work. A variant for unpredictable nonces has been suggested by fgrieu in the comments, with the following modifications to the above:

$m_0=0\parallel 1 \parallel 0$ (that is the first and the third block are all-zero, the second block has only the LSB set) and $m_1=0\parallel 0\parallel 0$ (that is three all-zero blocks)
The encryption now is $c_b=n_b\parallel c'\parallel c''\parallel c'''$
The adversary now returns 1 iff all three $c',c''$ and $c'''$ are pair-wise different, else the adversary returns 0.


have a question in the book "introduction to modern cryptography" "introduction to modern cryptography. 2ed" in page 254

"By obtaining sufficiently many estimates and letting $x_{i}$ be the majority value, $A{'}$can ensure that $x_{i}$ is equal to $gl(x, e^{i})$ with probability at least $1-\frac{1}{2n}$.

Why is the probability $1-\frac{1}{2n}$?

By taking enough samples, it is possible to ensure that the majority value is the correct one with high probability. To prove this, you use Chernoff's bound. Now, the more samples that you take, the higher the probability that the majority value is the correct one (when plugging into Chernoff). So, this is a parameter that you can choose however you want. We choose $1-\frac{1}{2n}$ since this is what we need to finish the proof. There is nothing special at all about it; and you can also get much higher probability by sampling more (but it's not needed). I hope that this is clear now.


Which keys are necessary to decrypt Application data in a SSL connection? I'm debugging an application which communicates between client and server using a SSL/TLS connection, and want to capture and analyze the sent data.

Are the client write keys and server write keys enough to decrypt the data, or do we also need the MAC keys?

To simply decrypt the data, the keys that were used to encrypt it are all you need.

However without the MAC keys you won't be able to verify the integrity of a message, so you won't be able to tell if the data you have decrypted is the same as what was sent (or even who sent it).

If you're debugging on a trusted local network then that might not be too important.


How secure is a book derived key and what can be done to strenghten it? If you have a manual encryption system where the keying is done by extracting a key from a book, a major weakness is that an adversary can search trough all existing books to find a perfect Match and thus the key. But isn't that very theoretical since not all books can be accessed by every one on the internet?

What can be done to strenghten such a book derived key?

The key selection must always be sufficiently random.

The key can never be considered reliably secure if the selection is simple ("Book A, page B") since the number of possibilities is necessarily too low.

Considering poems in Afrikaans has been cracked it's a necessity to NOT rely on a published book being unknown to the adversary.

Secure book based ciphers often include a list of references to individual books, individual pages, and different paragraphs in turn. In this case it is the sum of many independent unpredictable selections that provide the security a key needs.


Comparing two encrypted numbers using El Gamal without using decryption I'm trying to create a protocol for comparing two El Gamal encrypted numbers (both numbers are encrypted with the same public key). However I'm having trouble with figuring out how to do this without using decryption at all.

My current approach for comparing $\mathcal{E}_{pk}(a)$ and $\mathcal{E}_{pk}(b)$ is to encrypt a random value: $\mathcal{E}_{pk}(r)$ and then calculating: $\mathcal{E}_{pk}(ar)$ and $\mathcal{E}_{pk}(br)$. By then decrypting both products and evaluating $\mathrm{max}(ar, br)$ it becomes possible to know which value is largest, without learning anything about $a$ or $b$ (with some caveats of course). However this does involve decrypting two values, which of course requires a private key. As such this approach is not ideal.

Is it possible to do this without having to use decryption?

Edit: As per request, I'll expand a little bit on what it is I'm trying to do.

I have an encrypted database on a server. The database is really nothing more than an encrypted key/value store. In this database multiple users have stored multiple records each encrypted with their own public key.

I now want to add the functionality that a user can search their own records. My idea was that the user sends their encrypted query (for example: "All my records with a value greater than $a$", where $a$ is some encrypted value) to the server.

The server then retrieves all the records belonging to the user performing the query and for each record performs a homomorphic comparison $\mathrm{compare}(\mathcal{E}_{Pk}(a),\ \mathcal{E}_{Pk}(v_i))$ (where: $v_i$ is the value of record $i$) to find all the records which have a value greater than $a$.

Lastly the server sends all the encrypted records back to the user whom will then be able to decrypt and view them.

I believe you're having trouble with achieving your goal, because it actually goes against the security property of ElGamal:

I don't know how deep your cryptography background is, but the security of ElGamal is IND-CPA. It basically states, the attacker chooses two messages, gets back the encryption of one of the message, and he has to choose which message it was and retrns 0 or 1. If IND-CPA holds, then there is no stragety better than guessing that one bit(with negligible difference).

If you have an operation for comparison without decryption, then the above security game is easy: The attacker can encrypt both messages. And he could also encrypt an intermediate value and use the comparison to immediately find out which one it was.

About your general idea, using the multiplicative homomorphic property:

Kep in mind, that you are operating modulo some number. Formally, it's a finite field. But there is no comparison of elements in finite fields. The only way to achieve that, would be to limit the size of the numbers somehow, that you never trigger the modulo operation. That means, you have to keep the products below the modulus, otherwise the simple formula $a < b \Leftrightarrow ar < br$  is not valid any more. At least in general, without some additional constraints, e.g. that $a$ and $b$ are close together.
But then, anyone who sees $ar$ and $br$ can also compute $gcd(ar,br)$. That is divisible by $r$, and if $a,b$ are coprime, it is exactly $r$. It's easy to get $a$ and $b$ then.

So for the purpose of security, this step is exactly the same as giving $a$ and $b$ directly for comparison.

To your acutal question:

There are a few things, which you could use. But they are constructs of scientific papers, not something that you can find fully implemented in libraries:

Order preserving encryption, e.g. see this question or Order-Preserving Symmetric Encryption, Boldyreva et al., 2009
searchable encryption, see this question or our tag for it, or Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,  Curtmola et al., 2006

Order-preserving encryption preserves elements order, so the comparison of the plaintext is just comparing the ciphertexts. However, this comes at a cost: The ciphertexts are usually quite a bit larger than the plaintexts. Searchable encryption is a powerful construction, which could be adapted for your comparison case.

But with ElGamal, you're not going to be able to achieve that without decryption and comparing the plaintext.


In PKCS#1 V2.2, should MGF be based on the same hash function that RSA-OAEP-ENCRYPT uses? In Section 7.1.1 of PKCS#1 v2.2 there are two options for RSAES-OAEP-Encrypt given:

Hash
MGF

Appendix B.2.1 of the same document states that MGF1 is based on a hash function.

Is MGF1 based on the same hash function that is chosen as an option for RSAES-OAEP-Encrypt, or is it a different hash function?

If they can be different, in what common implementations do they differ?

The first hash is only used to hash the label. Most of the time the label will simply be empty, which means that a constant value can be used, identified just by the hash algorithm itself.

Although the hash values may differ and may have any SHA-x value, they are generally set to SHA-1 - which is the default. Note that SHA-1 is considered secure for MGF-1. It's also save to use over an empty string. So generally the use of SHA-1 is no issue and there is little to no reason to use another hash algorithm.

So in general you'll find two kinds of implementations: ones that simply keep to the default at all times (SHA-1 twice) or those that are configurable, such as the one in Oracle's Java (or Bouncy Castle for that matter). The configurable ones also will keep to the default unless specified differently.

Until today all the OAEP implementations that I encountered default to SHA-1 for both, but I guess in this world there could be one that chooses a different hash (if just to avoid SHA-1 altogether).

Et voila, an "unbalanced" OAEP encryption (using Oracle's Java 8):

MGF1ParameterSpec mgfSpec = new MGF1ParameterSpec("SHA-256");
// the "label", currently encoded to zero bytes
PSource pSource = new PSource.PSpecified(new byte[0]);
OAEPParameterSpec oaepSpec = new OAEPParameterSpec("SHA-512", "MGF1", mgfSpec, pSource);

Cipher oaep = Cipher.getInstance("RSA/ECB/OAEPPadding");
oaep.init(Cipher.ENCRYPT_MODE, kp.getPublic(), oaepSpec);
byte[] nothingEncryptedReallyWell = oaep.doFinal();
System.out.println(Hex.toHexString(nothingEncryptedReallyWell));


Encrypt entire payload or only confidential parts of payload? In cases where a large complex data structure contains elements that are a mix of confidential and not-so-confidential data, what would be the pros & cons of:

encrypting the entire structure with one key; or
encrypting only the parts of the data structure that contain confidential data?

Pros of encrypting entire payload:

That's simplest to code.
Encrypting data may have the side-effect of improving the chances to detect an alteration during transfer of the cryptogram (hence enciphering the whole payload may extend that beneficial side-effect to the whole payload); however that is not the function of encryption, and it must not be assumed that encryption ensures integrity, especially facing malicious changes; see second section.

Cons of encrypting entire payload:

The whole payload becomes unintelligible, possibly hindering functionality; e.g. we could loose access to the identifier of the destination of the data (possibly needed for routing to the appropriate location), when it was produced (forcing transmission of obsolete data), or the index/identifier of the key used for encryption (making decryption a guesswork).
Because of the above, some essential data might need to be duplicated in clear, increasing the size of the data transmitted, thus transmission time and cost.
Encryption time has a component proportional to the amount of data enciphered, thus there is more encryption and decryption work to do.
The attacker has potentially more known plaintext/ciphertext pairs; that is a non-issue with modern ciphers, but used to be a way to attack pre-1970 cryptosystems.
It is much easier to get approval for free circulation across borders of a system using secure encryption that enciphers only specific fields of an application-specific message, than for a secure system designed to encipher arbitrary data; this reality often entirely negates the first stated advantage of enciphering the whole payload.

In many practical cases, a sound security analysis would conclude that the right option is to ensure the integrity of the whole payload, and the confidentiality of part of it. Some modern operating modes, like AES-GCM, have provision for that; the computational savings obtained by not enciphering what needs not are significant (at least when AES is in software).


Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? I am currently experimenting with ed25519 and I noticed that on secret key creation, bit 254 is always set and the lower 3 bits are always cleared. I found that bit 254 is always set to protect against timing attacks in this question: When using Curve25519, why does the private key always have a fixed bit at 2^254?

But why are the lower 3 bits cleared. Obviously it has to do with the formula in the curve25519 paper:
The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$

It's because of the 8 in there, but why is that 8 there? I suspect it has something to do with theorem 2.1 in the curve25519 paper, but I am not sure, because I do not understand fully what is being proven there.

I am experimenting with ed25519 primitives in some cryptographic routines which need me to add scalars to the secret key (add secret keys). Even if I add two well formed ed25519 secret keys, the result will not always have bit 254 set and the lower 3 bits cleared. Is this a security problem? I understand the risk for bit 254 but not the lower 3.

Clearing the lower 3 bits of the secret key ensures that is it a multiple of 8, which in turn ensures that no information, small as it may be, about the secret key is leaked in the case of an active small-subgroup attack.

The typical simple Diffie-Hellman key exchange works like this:

$$
\text{Alice} \xrightarrow{\hspace{3cm} a G \hspace{3cm}} \text{Bob} \\
\text{Alice} \xleftarrow{\hspace{3cm} b G \hspace{3cm}} \text{Bob}
$$

$a$ and $b$ are Alice and Bob's secret keys, and $G$ is the base point, which is $(9,\ldots)$ in curve25519. Alice computes $a\cdot bG$, Bob computes $b \cdot aG$, and the shared secret is derived by passing $abG$ through some key derivation function.

Now, as you have noticed, the order of $G$ is $p_1 = 2^{252} + 27742317777372353535851937790883648493$, whereas the number of points in the curve itself is $8 p_1$. This means that there are a few remaining points that have small order. An active attacker can, e.g., replace Bob's message $bG$ with a point of order $8$ and be able to find $a \bmod 8$ by inspecting following messages. When every valid secret key is $0 \bmod 8$, the attacker gets nothing.

One may argue that this wastes 3 perfectly good key bits to prevent an already ineffective attack. Notice, however, that the actual security of the scheme is tied to the order of the base point, $p_1 \approx 2^{252}$. Clearing those 3 bits (out of 255) does not reduce the keyspace since it still leaves 252 useful bits, giving roughly the same keyspace as the number of points generated by $G$.


why people don't use the same generators? i want to make many pederson commitments $C=g^s h^r$ for a long time , do i have to change the generators $g$ and $h$ or its ok if i always used the same ones

You can use the same $g$. However, if the discrete log of $h$ relative to $g$ is known, then Pedersen is no longer binding. Thus, you cannot use an $h$ if there is any possibility of someone else knowing that discrete log.


Introduction to LLL algorithm applied to linear modular inequalities What is the Lenstra–Lenstra–Lovász lattice basis reduction algorithm about?
How is it applied to solve for $x\pmod m$ a system of modular inequalities $(u_i\,x+v_i\bmod m)<w$ for $0\le i<n$?
I'm aware of this related question, but would like something introductory and detached from a Linear Congruential Generator. I understand the notion of basis of a vector space, but would not recognize a lattice or lattice basis should I walk by one.

If a numerical illustration is needed, perhaps consider the PRNG based on a LCG truncated to it's $k$ high bits, modulus $m=2^{k\,n}$, multiplier $a=8\left\lfloor m\,\pi/64\right\rfloor+5$, addend $b=1$, seed term $x_0=x\bmod m$, recurrence $x_{i+1}=a\,x_i+b\bmod m$, output $y_i=\left\lfloor 2^k\,x_i/m\right\rfloor$.
That can be expressed as $(u_i\,x+v_i\bmod m)<w$ as in the question for $w=m/2^k$, $u_i=a^i\bmod m$, $v_0=-w\,y_0\bmod m$, $v_{i+1}=a\,(v_i+w\,y_i)+b-w\,y_{i+1}\bmod n$.

The short answer is that LLL (or more generally, lattice reduction methods) is useful when you can convert your problem into finding a small linear combination of known vectors.
Let's take your example and make it concrete. Let $m = 2^{64}$, $a = 7244019458077122845$, $b=1$, and the we have a generator that outputs the upper 16 bits of the state at each iteration:
sage: k = 16
sage: n = 4
sage: m = 2^(n*k)
sage: a = 8 * floor(m*pi/64) + 5
sage: b = 1
sage: x0 = 5183095426420329486 # randint(0, m)
sage: x = x0
sage:
sage: l = 6
sage:
sage: X = []
sage: Y = []
sage: Z = []
sage: for i in range(l):
sage:   x = (a*x + b) % m
sage:   X.append(x)
sage:   Y.append( x - x % 2^(n*k - k) )
sage:   Z.append( x % 2^(n*k - k) )

Here we have 6 outputs; that'll be enough, as we'll see later. The vector $\mathbf{X}$ represents the full state at each iteration; the vector $\mathbf{Y}$ represents what we obtain from the generator (conveniently multiplied by $2^{48}$), and the vector $\mathbf{Z}$ is the information we are missing. Obviously, $\mathbf{X} = \mathbf{Y} + \mathbf{Z}$.
Now we can indeed turn this into a less recursive function. We can represent each element of $\mathbf{X}$ as
$$
X_i = a^i\cdot x_0 + b\cdot \sum_j^i a^j \bmod m\,,
$$
where $x_0$ here is the seed we are looking for.
sage: A = [ power_mod(a, i, m) for i in range(1, l+1) ]
sage: B = [ b * sum([ power_mod(a, j, m) for j in range(i) ]) % m for i in range(1, l+1) ]
sage: assert( X[i] == (A[i]*x0 + B[i]) % m )

What we have now is a vector relation:
$$
x_0\cdot \mathbf{A} + \mathbf{B} = \mathbf{Y} + \mathbf{Z} \pmod{m} \,.
$$
We can move the $\mathbf{B}$ vector to the other side:
$$
x_0\cdot \mathbf{A} = \mathbf{Y} + \mathbf{Z} - \mathbf{B} \pmod{m} \,.
$$
Because we do not know $\mathbf{Z}$, we can't solve this, of course. But because $\mathbf{Z}$ is relatively small—made up of only 48-bit coefficients—we can do something else. All of the possible elements on the left side can be represented as combinations of the rows of the following matrix:
$$
\begin{pmatrix}
  m &   0 & \dots & 0 \\
  0 &   m & \dots & 0 \\
  \dots & \dots & \dots & \dots \\
  0 &   0 & \dots & m \\
  A_0 & A_1 & \dots & A_{l-1}
\end{pmatrix}
$$
Every vector of the lattice spanned by these rows is given by $(v_0\cdot m + v_{l-1}\cdot A_0, v_1\cdot m + v_{l-1}\cdot A_1,$ $\dots$ $, v_{l-1}\cdot m + v_l \cdot A_{l-1})$, for some integer vector $(v_0, v_1, \dots, v_l)$. Note that the multiplications by $m$ disappear when reduced modulo $m$; they are there purely to represent the modular relation over the integers (seeing that $x \bmod m = x + m\cdot k$ for any integer $k$). By definition we know that there is some point in this lattice that is equal to $\mathbf{Y} + \mathbf{Z} - \mathbf{B} \bmod m$.
Our hope is that we can find some vector in this lattice that will be in the vicinity of $\mathbf{Y} - \mathbf{B}$; that is, even if we don't have $\mathbf{Z}$, if $\mathbf{Z}$ is small enough we may be able to find $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$ anyway. Let's try:
sage: t = vector([ ZZ( (Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l, sparse=False)
sage: L = L.insert_row(l, A)
sage: from sage.modules.free_module_integer import IntegerLattice
sage: from fpylll import CVP, IntegerMatrix
sage: v = vector( CVP.closest_vector(IntegerMatrix.from_matrix(IntegerLattice(L).basis_matrix()), t) )
sage: v
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)
sage: (vector(Z) + vector(Y) - vector(B)) % m
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)

It works! (Don't pay much mind to how this vector is found; let's pretend it's a closest vector blackbox).
Having this vector it is now straightforward to obtain $x_0$. We can use linear algebra, for instance:
sage: L.change_ring(Zmod(m)).solve_left(v)
(0, 0, 0, 0, 0, 0, 5183095426420329486)
sage: x0
5183095426420329486

Why does this work? It's complicated. But the basic idea is, if you have a lattice given by a matrix $L$ of rank $n$, its volume is given by the determinant, and the shortest (resp. closest, with some caveats) vector is known to be at most $\sqrt{n} \mathrm{det}(L)^{1/n}$ distance (usually in $L_2$ norm). In our case, that is
sage: (sqrt(L.rank())*IntegerLattice(L).volume()^(1/L.rank())).log(2).n()
53.9751060324574

But our expected distance to $\mathbf{Y} - \mathbf{B}$, i.e., the norm of $\mathbf{Z}$, is shorter than that, having norm approximately $2^{48}$ (since we are missing 48 bits of state):
sage: (t-v).norm().log(2).n()
48.4871956406101

Therefore it is highly likely that the closest vector to $\mathbf{Y} - \mathbf{B}$ is indeed our solution.
This also explains why when you leak too few bits the method stops working: the norm of $\mathbf{Z}$ becomes larger than the norm of the expected closest vectors, so you start getting unrelated vectors as the closest point. If $\mathbf{Z}$ is 63 bits, then your distance is approximately 64 bits long, which is much higher than $2^{53.97}$.
But we haven't used LLL yet. In fact, LLL does not even find closest vectors! However, up to some approximation error (exponential on the dimension), LLL does find very short vectors. If the error is not too large, LLL can serve as a decent replacement to a shortest vector blackbox. So one common approach is to turn closest vector problems, such as this one, into shortest vector problems that LLL can tackle.
One option, which uses LLL internally, would be to use the Babai nearest plane method to find a close vector. But there is a simpler trick, due to Kannan, to (heuristically) embed a closest vector problem into a shortest vector problem. The idea is to extend the lattice such that the closest vector is a short vector in it. Coupled with LLL (or BKZ), we can obtain a solution that way:
$$
\begin{pmatrix}
  m &   0 & \dots & 0 & 0 \\
  0 &   m & \dots & 0 & 0\\
  \dots & \dots & \dots & \dots & 0 \\
  0 &   0 & \dots & m & 0\\
  A_0 & A_1 & \dots & A_{l-1} & 0 \\
  Y_0 - B_0 & Y_1 - B_1 & \dots & Y_{l-1} - B_{l-1} & M
\end{pmatrix}\,,
$$
where $M$ here is an approximation of the expected distance, that is, the norm of $\mathbf{Z}$. Because we expect $\mathbf{Z}$ to be small, the vector $x_0\cdot \mathbf{A} - (\mathbf{Y} - \mathbf{B})$ is expected to be short as well, and hopefully LLL gives us a solution.
sage: t = vector([ ZZ( -(Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l + [0], sparse=False)
sage: L.set_row(l, A + [0])
sage: L = L.insert_row(l+1, list(t) + [2^(n*k - k)])
sage: L.LLL()
[                 0                  0                  0                  0                  0                  0                  0]
[    84830033144727     99493793228572    193251317565997    195477621437466     41221639930099    247621686570632    281474976710656]
[  -687665523248565   -558678928843390  -2831909104870979    783681348831084   3591271679705919     61017834323238    844424930131968]
[ -1823548220242427   2253638642602902  -3569730745364989   3416755876477276   -751301580596367  -2032834227000110   1407374883553280]
[  7621930640779355   -105157344785070  -3265673334549427   1969120201701820  -1755046640220593  -2112569643194890    844424930131968]
[ -1177023352112110  -3396609545281551    557994199985972  10658623678942411    804267325513190    663710453352693  -7036874417766400]
[  4998293895365537  11389134223649311  -2635952223845275   2485610916234323   4530338313613385   2884351148040487  -8444249301319680]
[  -192992080812070   5962407351033287  11672086573074080   -997631747809227   8935027883752214 -19143574866262125   5910974510923776]
sage: vector(Z)
(84830033144727, 99493793228572, 193251317565997, 195477621437466, 41221639930099, 247621686570632)

The shortest nonzero vector in this lattice is exactly $\mathbf{Z}$ (plus an extra element), the missing information to get us to $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$. We can now solve for $x_0$ as before.
Long story short, if you are able to  coax your problem into a question of finding linear combinations that are either short or near some known vector, lattices might be of use. This, of course, does not even begin to scratch the surface of what you can do with lattices. The article by Joux and Stern entitled Lattice Reduction: a Toolbox for the Cryptanalyst is a good—and far more rigorous—introduction to this topic.


Is it possible to utilize an AES-128 encryption hardware unit for AES-256? There exist processors (for example ARM v8/v9 archicteture based),
which cannot do AES-256 hardware based,
but are equipped with AES-128 encryption hardware units.

Is it possible to utilize an AES-128 encryption hardware unit
in some way to speed up the calculation of AES-256?

There are two important differences between AES-128 and AES-256:

AES-128 has 10 rounds, AES-256 has 14
The key expansion process (that is, how they generate subkeys) is different

If your AES-128 encryption hardware just takes a plaintext block and a 128 bit key, and produces a ciphertext block, well, no, there's not much you can do.  In this case, the hardware knows the AES-128 subkey expansion process, and there's nothing you can do to ask it to do the AES-256 expansion process instead.

However, if the hardware takes the plaintext block and the $11 \times 128$ bit expanded key, yes, there are things you can do.

The obvious approach would be (in the encrypt direction) to perform the first four rounds in software (stopping just before the addround transform at the end of the fourth round); then hand the intermediate block to hardware to compute the last 10 rounds.

In your key expansion process, you'd run the AES-256 key expansion process in software; you'd keep the first 4 generated subkeys for your software routine; you'd hand the last 11 subkeys to hardware as your expanded "AES-128" key.

This idea won't be as fast as doing AES-256 in hardware; however it should be faster then performing everything in software.

Also, you want hardware to handle the last round (in the encrypt direction); that last round is handled slightly differently - while you can adjust for it, there's no reason to.


Can the backdoor in Dual_EC_DRBG be used to create a public key stream cipher? Dual_EC_DRBG has the property that if $Q = e\cdot P$, someone who knows $e$ can break the PRNG.

This seems to lead to a public-key stream cipher:

Alice chooses a random $P, e$, where $P$ is a generator.
Alice computes $Q = e\cdot P$.
Alice publishes $(P, Q)$ as her public key.  She retains $(P, e)$ as her secret key.

To send a message:

Bob chooses a random seed $S$.
Bob publishes the first $n$ bits of the output.
Bob uses the rest of the output as a keystream.

To decrypt, Alice uses her knowledge of $e$ to break "PRNG" and recover the keystream.

Is this system secure? Does it provide any advantage over other forms of asymmetric cryptography?

You can do something like what you are suggesting. But, the EC_Dual_DBRG also has biases in the stream and so you cannot use it without changes (e.g., truncating much more). However, this is based on the same operations as ElGamal.

The public key is set up exactly as proposed. Then, to encrypt a message $m$ of any length, do:

Choose a random $r\in\mathbb{Z}_q$, where $q$ is the order of the Elliptic curve group
Compute $U=r\cdot P$
Compute $k = H(r\cdot Q)$
Encrypt $m$ with $k$ using any symmetric encryption scheme you wish


When truncating an AES MAC value by "w" , how do I justify that "w" is still negligible? I'm taking an online class on cryptography at corsera.org / Stanford, and the professor is explaining that it's OK to truncate an AES MAC to $w$ bits as long as $1/2^w$ is still negligible (say $w > 63$)

Where did the value $1/2$ come from?
How is 64 and above negligible?
What is non-negligible today (5/17/2013) and in the future (5/17/2020)?

One of the factors that determines how hard it is to forge a MAC for a given message is how long the MAC is. If it's 1 bit long, you can definitely produce the correct MAC in two tries.

$2^n$ is the number of possible bit-strings of length $n$; $1/2^n$ is the probability that any random bit-string happens to be the MAC (of length $n$) for a given message and key.

Negligible depends on what you're protecting with your MAC, who your attacker is, and what information / oracles they have access to. In particular, if the attacker has to make some kind of service request to a single point to check that a MAC is valid, $2^{64}$ is an awful lot of requests – this is probably the assumption being made when it was stated that MACs of length 64 or more are secure.

Not all MACS can be truncated safely however. AES-GCM loses more security than expected by truncation, but HMAC is fine.

Given a MAC construction that can be safely truncated, truncating it to 128 bits is unlikely to pose a problem for a long time ($\gg$2020), for any attacker capability.