Cryptopals challenge 2.11: Distinguish ECB and CBC encryption I'm going through the Matasano crypto challenges (also known as cryptopals) and I recently got stuck in the following challenge: http://cryptopals.com/sets/2/challenges/11

The goal of the challenge is detecting the block cipher mode in AES encryption: ECB or CBC.

I saw the following post that discusses this matter, but it doesn't truly solves the problem: https://stackoverflow.com/questions/17382438/how-to-detect-block-cipher-mode

The only flaw that I know of that can help detecting the mode of operation is that ECB is stateless, i.e. similar plaintext blocks convert to similar ciphertext blocks. But in the challenge it is specified that we need to add a random number of bytes (between 5 and 10) before and after the plaintext, which causes similar blocks to slide a bit so the ciphertext result doesn't necessarily contain similar blocks. Does anyone have any hint or solution to this problem?

Hint: Use the plaintext XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX, where the (arbitrarily chosen) byte X is repeated at least 48 = 3 × 16 times (so that, no matter how many random bytes are prepended to this plaintext, it will always cover at least two successive AES blocks).


The probability of breaking symmetric encryptions The probabilty of cracking AES is $1 \over 2^n$, n being the size of the key. Would this hold true for every encryption of the same size?

This is from RC4's Wikipedia page:

  In March 2015 researcher to Royal Holloway announced improvements to their attack, providing a $2^{26}$ attack against passwords encrypted with RC4, as used in TLS.

This might answer my question, but I'm not sure.

Technically the Caesar cipher is a symmetric encryption algorithm and it is broken so easily it barely requires pen & paper.

So no, this does not hold.

Also, I'm not sure where you got that figure but that is the probability of guessing the correct key in one attempt. Given a modern computer it should at least be feasible to attempt two guesses. ;)


Evaluate the time of Paillier decryption If I have 4 kilobytes of Paillier encrypted data, how can I know the time needed to decrypt it?

You need to know

The size $s$ of the public modulus $n$ in bits.
The number $c$ of cryptograms.
If the code uses the CRT, or not; and in the affirmative, the number $k$ of prime factors in $n$ (usually $k=2$ for $n=p\,q$, with $p$ and $q$ distinct primes).
And of course, some benchmark of the code and hardware!

Each cryptogram is $2s$-bit, thus for 4kbyte ciphertext (at most 2kbyte plaintext) $c\,s\le2^{14}$. The largest range/safer/slower for 4kbyte ciphertext is $c=1$, $s=2^{14}$ (that is 16384-bit $n$, which is rather large).
As a rough approximation, using the same computation means and $k=2$, Pailler decryption with CRT for $s$-bit public modulus $n$ ($2s$-bit cryptogram) is about as fast as RSA decryption with CRT for $2s$-bit modulus. Not using CRT in Pailler causes a moderate slowdown (at most a factor of $2$), less than in RSA. Time is proportional to $c$, and often normalized for $c=1$ in RSA benchmarks.
Extremely roughly, Pailler decryption for $c=1$ is like 5 times slower than RSA decryption at equal size of $n$ and other stuff.
Large savings are possible by increasing $k$, like in multiprime-RSA.


Is there an input length range for SHAKE128 hash function? For SHAKE128 hash function in SHA3VS document, I find this paragraph:

  Therefore, for testing SHAKE128, (168*2)+1) = 337 unpredictable messages will be
  generated with lengths from 0 to 337 336 bytes (omitting 0 if zero length is not
  supported) and SHAKE256, (136*2)+1) = 273 unpredictable messages will be
  generated with lengths from 0 to 273 272 bytes (omitting 0 if zero length is not
  supported).

I know the hash digest length is flexible:
Hash(input, length N) = N-byte digest

Question:

Is there any requirement for input length (minimum or maximum no. of bytes) to achieve 128 security level?

The quoted paragraph talks about the testing of SHAKE128. As usual, for the 128-bit security achievement, you need to think about the generic attacks on hash functions.

For preimage resistance, you need 128-bit digest size. However, due to the birthday attack, you need 256-bit digest size to achieve 128-bit collision resistance. That is $\sqrt{2^{256}} = 2^{256/2} = 2^{128}$.

For the input length; if the input space is small, it can easily brute-forced or a special rainbow table can be implemented to find the preimage of the hash values. For 128-bit preimage resistance, you need your input space to be around 128-bit.


Does pseudorandom secret sharing require a central dealer? I'm trying to figure out whether pseudorandom secret sharing (as described in this paper) requires a central dealer, i.e. one party who doles out keys to the other players and thus who would be able to generate all the pseudorandom numbers on their own.

I'm new to this, so the paper is almost completely opaque to me, and there doesn't seem to be any dumbed down versions of this technique anywhere on the internet.

The implementation of PRSS in VIFF appears to require a central person to generate everyone's initial keys, but this doesn't seem necessary, i.e. you could make an implementation where everyone generates their own random keys and shares them with the appropriate parties as necessary.

However, VIFF's use of "dealer keys" confuses me, and makes me think that at some point, some party could generate all the pseudorandom numbers on their own. I've tried to read through the code, but I've reached a point where it's just as opaque to me as the aforementioned paper.

Is there anyone who can explain this?

In secret sharing, one person typically wants to share a secret. Only that one person knows that secret, so they are the dealer.

In MPC, which VIFF implements protocols for, you actually have multiple parties, each with a secret input(s). So, each of these parties is the dealer for their individual secret input(s). In this sense, there is no central dealer for the entire computation.


Propagating CBC insecure Authenticated Encryption why is Propagating CBC (PCBC) insecure for authenticated encryption?
I received the hint that I should feed a message of length $n$ and a message of length $n-1$ to it, but I don't really get what the result gives me, as we still have this Xor with the previous message.

PCBC doesn't offer authentication at all; there is no cryptographic checksum calculated over the ciphertext, and there is no verification part within the algorithm.

The only thing that PCBC offers is error propagation over all subsequent blocks after a changed block in the ciphertext. However, as there is no verification at the end of the decryption, that will just mean that the (padded) plaintext will contain random data. This may result in a padding error, but it is also possible that it does not by pure chance.

Even if you would add a known plaintext at the end then PCBC will allow you to swap blocks of ciphertext in the middle. And if you add a cryptographic checksum before encryption (i.e. verified after decryption) then you may still be vulnerable against certain ECB-style plaintext attacks.

I'm not really sure what the differently sized messages are supposed to do, to be honest. Maybe somebody else knows the precise attack.

Just like any other secure mode of operation you can still use PCBC for authenticated encryption. For instance, you could use it for a PCBC-HMAC encrypt-then-MAC security scheme where the ciphertext is authenticated before decryption is performed.


What practical uses can random hash collisions be put to? Using magic, I've built a machine that instantly generates hash collisions. To try it out, I set the dial to SHA256 and typed in "e7cf3ef4f17c3999a94f2c6f612e8a888e5b1026878e4e19398b23bd38ec221a".

I hit the button and it showed me a long sequence of bytes starting with "09F7E02F1290BE211DA707A266F153B3...". I hit the button again and it showed me another long sequence of bytes starting with "F326BED0DD25CED6BC1799EAF74E7F8C...".

Every possible hash output has an infinite number of collisions. My machine is just picking one of those collisions at random.

What practical uses could I have for a machine like this? You can't reliably get a collision you want - such as one that starts with a given salt or is structured as a valid Bitcoin package - just one of the many random looking collisions.

Note that attempting to open the machine will cause it to disintegrate, leaving only a golden egg behind.

If it is for completely random data you could still make a program that uses the random looking input to make different choices. For instance, you could sign two .jar files in Java, using the SHA-256 hash over the file in the META-INF folder. Then you can use the different files a property to make one choice or the other. Basically you're replacing one of the data blocks in a hash tree or list (which is in turn signed for Java).

Of course, most hash collisions don't work like that. For instance, the MD5 collisions need to be pre-calculated, but they work for normal data + a postfix. Even then, the amount of attacks that can be launched is limited. Faking a signature is such a big attack that the rest is more or less inconsequential.


How can I ensure forward secrecy when storing encrypted messages in a public blockchain? I want to store encrypted sensitive messages in the blockchain.

I was thinking of using public-key cryptography to achieve this, but as the encrypted data will be stored forever in the blockchain and this data will still be sensitive 100 years from now I am afraid there will be a possibility in the future for people to break the encryption (using quantum computing for example).

Is there a way for me to achieve forward secrecy that will likely not be broken in the near future ?

Thank you

EDIT : I can tolerate a few messages being decrypted in the future (out of the tens of thousands I want to store), but I would like to keep that number as low as possible (less than 0.1%)

As long as you use a post-quantum secure encryption scheme the fact that your messages are on the blockchain is not a problem. Traditionally adversaries are assumed to be capable of recording the traffic on an encrypted channel so theoretically they have always been allowed to keep messages for future decryption.

Currently the best way to get the necessary security is probably to use a symmetric scheme because their security is believed to only halve against a quantum computer. Or you pick your favorite post-quantum crypto scheme and combine it with a traditional one. For example Frodo is pretty conservative in its choices and in the paper the authors describe a combination with ECDHE.

Note that forward secrecy is not actually a property of the stored messages but is about the receiver of the message throwing away the key. The goal is that if somebody compromises the sender or receiver in the future they won't find a key that allows them do decrypt those old messages. In this case the difficult part is for the sender to know the current key. That's why this is only used in interactive protocols in which both parties exchange messages. Otherwise they can not agree on a shared secret without one party proposing it and thus having to encrypt it with some long term key.


What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm? I cannot seem to understand the role or goal of Quantum Fourier Transformation in Shor's integer factorization algorithm. Is it used to collapse all quantum states into one, in which it has a factor of a given input $n$?

To do factoring, Shor's algorithm presents a way of finding the the following problem. If I know some natural numbers $g$ and $N$, with $g < N$, where $\gcd(g, N) = 1$, what is the smallest $r > 0$ such that $g^r = 1 \bmod N$. This is called the problem of finding the order of $g$ modulo $N$.

By Euler's theorem, there will be some such $r$ because $g^{\phi(N)} = 1 \bmod N$ for all $\gcd(g, N) = 1$, where $\phi(N)$ is Euler's Totient function.

The annoying thing about quantum computing, as you may have figured out by this point, is that you can create some arbitrary superposition of states and do computation on all of those states in parallel, but then when you want to get an actual value you only get to see one of those answers, chosen at random from the answer distribution. Say for instance we set $a$ to be some quantum state that is the superposition of all integers from 1 to 10 (each with equal probability). Then we compute $b=2*a$. It will multiply all of the states by 2 in parallel and we will get a quantum state that is the superposition of all even numbers from 2 to 20. Now if we "open" the state of $b$ we get a random even number from 2 to 20. Which is pretty useless. We could have just opened $a$ first and done the computation ourselves.

Now, the Fourier transform takes a function and computes the "waves" that it is composed of. For instance the image below (from this site) shows the wave forms of different instruments and their corresponding Fourier transforms. In particular, notice the spikes in the Fourier transform graphs. The first spike corresponds to the period of the function. The other spikes show various harmonics that exist on top of this.

Now, back to finding the order of $g$ modulo $N$. You start with setting $a$ to be a uniform superposition of all numbers from 0 to $q-1$, for some $q >> N$.

You then compute $(a, g^a \bmod N)$. This will now be a superposition of $q$ tuples.

Now comes the important part. $g^a \bmod N$ is periodic. Specifically, if $r$ is the lowest non-zero integer such that $g^r = 1 \bmod N$, then $g^a \bmod N$ is periodic with period $r$. So, like with the musical instruments, if you were to plot $a$ against $g^a \bmod N$, there would be some visible repeated fundamental frequency and a number of other harmonics on top of this. So now if you compute the Fourier transform on $(a, g^a \bmod N)$ you will get a function showing how often different frequencies appear.

Now we look at the register holding the value of the frequency. There is some chance that we will get one of the higher harmonics, but there is a pretty good chance that we will get the fundamental frequency. This frequency corresponds to the period of $g^a \bmod N$, namely $r$. Since this experiment has a certain probability of failing (picking one of the higher harmonics). But if you repeat it some polynomial number of times, you can make the probability of it failing in all of those times as low as you want.


The probability of finding a limited set of collisions for HMACSHA256 I need some input on the use of HMAC-SHA256 in an open source project, any help appreciated.

The problem I'm solving is session fixation. We have a username, for that username we'd like to generate a session ID that would only be valid for that particular username so that it cannot be reused across users.

The session ID is calculated in the following manner:

|| denotes concatenation
key = 256 random bits from a cryptographically strong RNG
randomID = 128 random bits from a cryptographically strong RNG
username = some UTF-8 encoded string
sessionID = Base64Encode(randomID || HMACSHA256(key, username || randomID))

A few questions:

Will there be no collisions as long as the username <= 128 bits, i.e. the total input is never longer than 256 bits?
When usernames are longer than 256 bits, I assume the birthday paradox applies and you could expect a collision after 2128 distinct inputs (that's when probability reaches ~0.5)?
If we assume 231 valid usernames, what would the probability be that the attackers session ID would also be valid for another user and hence could be used in a session fixation attack? (A collision that does not map to another user would be useless to the attacker)

If there's anything else I should be worried about, I'd appreciate a comment on that.

If anyone's interested in the whole background on this, I'll include a pointer to the draft documentation.

I think most would agree that 2^128 is not plausible without UFO space alien technology (i.e., wildly successful quantum computers).

There is no currently known way to find collisions over SHA-2-256 in any plausible amount of time, with any plausible number of inputs.

As long as the key is secret, there is no known way to someone to find a username or randomID that produces a target HMAC value, or to predict the HMAC value for one username+randomID given the value for another (length extension attack).

However, another thing to be concerned about is timing leaks if you ever compare an expected HMAC value and a value received by a potential attacker. If you use a naive strcmp(), timing will tell the attacker how many initial bytes he got right and he can use that to work out the value he needs to send without even knowing the key, username, or randomID.


Key size vs output size of a MAC What is more important, in terms of security, the size of the MAC or the size of the key that it uses? I'm asking this because I have to answer the following homework question:

  What is more secure? A MAC with a 12-byte key and 6-byte MAC length,
  or a MAC with a 8-byte key and 12-byte MAC length?

For the first one, it's easier to find a pre-image of the result. But for the second one, it's easier to find the key.

The obvious issue is the probability of guessing the key, and the probability of guessing the MAC.

But there's also a qualitative difference.  Suppose you have learned a message/authenticator pair $(m, a)$ where $a = H_k(m)$.

You can test a guess $k_0$ for the key offline by testing whether $a \stackrel?= H_{k_0}(m)$.

The feasibility of finding the key $k$ depends on how much money the adversary has to commit to an offline key search.
You can test a guess $a'_0$ for the authenticator $a' = H_k(m')$ of a forged message $m'$ only by submitting $(m', a'_0)$ online to the legitimate system and seeing how the legitimate system reacts.

The feasibility of forging an authenticator $a'$ this way depends on how much bandwidth the legitimate system has to accept online forgery attempts.


Offline authenticated encryption for pub/sub Requirements:

only publisher can create messages
publisher & subscriber can both read messages and authenticate the publisher
offline message transfer
messages can't be read by non-participants
subscribers can be mobile platforms (Android, iPhone), i.e. less powerful processors
messages lifetime target is 15 years
messages are small, a few dozen bytes

I was looking at ECIES with ECDSA but I cannot seem to find a reference using ECIES where the sender has the static key and the receiver is using an ephemeral key. https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme#Informal_description seems typical, but in my scenario Alice wants to send a message and have any of Bob and his friends read it and know that it is from her.

I know that RSA can do this by encrypting a message specific key using a private key and decrypting using the public key (waving hands over some details here) but the exact same construction doesn't seem to work with ECs. Is there an EC construction that has similar properties? I don't want mobile devices to have to suffer 4k RSA keys (to make them hopefully secure into the 2030s).

You need to sign your messages and then encrypt them (sign-then-encrypt). The signature generation is performed using the private key from the publisher (sender) and the encryption is performed using the public key from the subscriber (receiver). The decryption is performed using the private key of the receiver and the signature verification is performed by the public key of the sender. The private keys remain private, the public keys need to be trusted.

  only publisher can create messages

Anybody can create messages, they are just bytes after all. Only the publisher should be able to create messages accepted by the subscriber.

  publisher & subscriber can both read messages and authenticate the publisher

Encrypt not just for the subscriber but also for the publisher and you should be fine.

  offline message transfer

Sure thing, but note that you may still have all the problems of a transport protocol. For instance, you could be vulnerable to padding oracle attacks if you encrypt using CBC mode.

  messages can't be read by non-participants

Only the subscribers (receivers) and publisher would have the corresponding private keys, so yeah.

  subscribers can be mobile platforms (Android, iPhone), i.e. less powerful processors

Neither of the schemes here would be troublesome for relatively low powered devices (if you can call the latest sets of smart phones "low powered" with 64 bit operations, hardware crypto accellerators and over 2 GHz clock speeds for the top and midrange models).

  messages lifetime target is 15 years

15 years is a long, long time in crypto. But if you use 512 / 512 bit curves and 256 bit symmetric cryptography (256 bit AES, for instance) then your message should be secure for a long time, unless crypto-analysis using quantum computing takes off on a large scale.

  messages are small, a few dozen bytes

An ECDSA signature at 512 bits is already 128 bytes minimum, and an ephemeral public key (needed for ECIES) would take around 64 bytes. A few dozen bytes seems a very small amount of available message space.

  I know that RSA can do this by encrypting a message specific key using a private key and decrypting using the public key (waving hands over some details here)

No, it cannot. The public key should be considered public.


Cryptographically strong seeded pseudo random number generator Why is the following not cryptographically secure?

Seed the algorithm with 32 random bytes S[0].

S[0] --hash--> S[1] --hash--> S[2] --hash--> S[3] ...
 |              |              |              |
hash           hash           hash           hash
 |              |              |              |
 v              v              v              v
R[0]           R[1]           R[2]           R[3]

The hash function is cryptographically strong, i.e. it cannot be reversed.

The outputs (R) comes in 32 byte blocks, R[0] onwards.

Obviously this is far too simple to be secure, but I wondered why.

In your scheme, $R[0] = S[1]$, because hashing $S[0]$ always gives the same result.

So knowing the output $R[0]$, the attacker can predict the entire stream - he knows the complete internal state at the position of $S[1]$.


Davies-Meyer Hash Function So the Davies-Meyer Hash Function is: Hi = Hi−1 ⊕ exi (Hi−1)

Say I pick H0 = 1110 0011

And the message x1 = "5" or "0000 0101"

Is this the correct way to compute H1?

H1 = 1110 0011 ⊕ (0000 0101 ⊕ 1110 0011)

H1 = 1110 0011 ⊕ (1110 0110)

H1 = 0000 0101

I must be doing something wrong because the hash function always comes out the same as the message.

The function $e$ takes two values: $x$ and $H$, and then merges them in a specific way. Your "way" is just XORing them. That's insecure, as you can see. Normally you use a block cipher for the function, like AES-128 for an input of 128 bit.

Example: $$ H_i = H_{i-1} \oplus AES_{xi}(H_{i-1}) $$


What block cipher is used for CBC-MAC? What block cipher is used for CBC-MAC? DES, AES, 3DES? Or it doesn't matter?

Well, yes, it does matter; however the terminology 'CBC-MAC' does not specify which.

CBC-MAC is a generic construction that takes an arbitrary block cipher, and turns it into an object that acts like a MAC for fixed length messages (much like CBC mode is a generic construction that takes an arbitrary block cipher, and turns it into a object that encrypts variable length messages).  And, just like "CBC" isn't necessarily used with a specific block cipher, neither is CBC-MAC.

Note: CBC-MAC has issues if you try to use it with variable length messages; CMAC and XCBC are two modes similar to CBC-MAC that avoid this problem.


Collision probability of MD5 over different attacks I am researching the collision probability of MD5 and various attacks against it. Can someone help me how to learn the least probability that there will be a collision in a specific attack on MD5?

For example: MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox.  Does this apply to any input given to MD5?

Also, is the output of MD5 uniformly distributed to the randomized input? (If, please provide references.)

MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox.  Does this apply to any input given to MD5?

As explained in the other answer, $2^{64}$ is the birthday bound of messages until probable collision, not a collision probability. For two random messages you'd expect a $1/2^{128}$ probability of a collision with a 128-bit hash.

However, MD5 is broken with regard to collision resistance, so for two (or any number of) attacker controlled inputs you can't put a bound on it, they can find a colliding pair easily. (In fact, they can produce any number of messages that all collide, unless there are e.g. restrictions on message length.)

  Also, is the output of MD5 uniformly distributed to the randomized input? (If, please provide references.)

This translates to "is MD5 PRF?", which as far as we know is the case. For a reference to the fact that we don't know how to distinguish it from PRF you can use e.g. RFC 6151, which uses that to justify why getting rid of HMAC-MD5 "may not be urgent".


Is there a way of increasing the time to brute force a cipher, but by increasing the ciphertext size instead of the key size? If you have a symmetric-key algorithm that is limited to using a small key size (say 40-bits) is there any way you could increase the resistance to brute force attacks without increasing the key size?

I am interested in approaches that increase the ciphertext message size (such as padding of some form, or a method that creates a ciphertext larger than the plain text) as I think it would still be affordable to transmit a message that is up to 10 times the original plain text size.

Is there a way to greatly increase the time a brute force attack would require to decrypt the message without increasing the key size?

For prior art I can provide this paper about hiding the key in large amount of random data, and the Chaffing and winnowing method that word plays with authentication and encryption.

Later I found this paper that asks "Is there any way to significantly increase the difficulty for an adversary of performing a brute-force search, while keeping the key size the same and not overly burdening the legitimate communicants?", which is the question I am asking.

Is there a way to greatly increase the time a brute force attack would require to decrypt the message without increasing the key size?

Something tells me you haven't understood what "brute force attack" means. In short, it boils down to: "try every possible key until you guess the correct one".

As a logic consequence, enlarging plaintext or ciphertext does not add anything to the security of a cipher when it comes to brute force attacks. Your cipher would still rely on the security of that

  …small key size (say 40-bits)…

which is definitely too short to make brute-force attacks unfeasible.

Now, instead of thinking about increasing plaintext and/or ciphertext message sizes (which might even introduce additional attack vectors which could void the need for a brute force attack), we usually fall back on KDFs (key derivation functions) to get a stronger key.

Differently worded: instead of trying to make the "message" stronger (which doesn't really make sense), we make the "secret" stronger as that actually adds to security… thanks to the algorithm design of KDFs (with tweakable parameters et al).

Think of it this way — a burglar (read: attacker) doesn't care how big or small your house (read: message) is. All that counts is the strength of the lock (read: cryptographic algorithm) and the strength of the key. A good lock and key can keep a small toolshed in your backyard safe, while a bad lock with an easy to reproduce key can make a military bunker as accessible as a public park bench.

To wrap it up, the security of a cipher mainly* comes from:

the individual cryptographic algorithm used, and
the key, which should be strong/large enough to make it unfeasible to simply "walk all keys until you stumble upon the correct one" (which is what we call a "brute force attack")

When not enough key material is available, KDFs come handy. And in case the cryptographic algorithm doesn't support an accordingly strong key size, you should switch the algorithm for a stronger one. There are ample, well-vetted algos availabe.

* Nota bene: Surely there are some additional nit-bits like initialisation vectors etc that also add to the security of modern ciphers, but I've bluntly skipped all that to keep this answer short and simple.


Could one make an asymmetric encryption scheme based on Sudoku? I was reading about a Polly Cracker encryption scheme based on the graph 3-coloring problem.  Aren't Latin squares just a form of the same problem?  If so, does this mean Sudoku can be used for public/private key encryption?

Sure. How efficient vs secure is another matter.

Look up Merkle's puzzles, as well. A latin square as a higher dimensional object can be related to differential properties of good mappings.


How to calculate period of stream cipher with multiple LFSR and NLFSR I am interested in knowing how to calculate period of a stream cipher with more than one FSR (linear as well as non linear). I know for a single FSR, period can be calculated with farmula q^L-1 where q is elements in finite field and L is length of feed back polynomial. However what I am confused in is, is this period is considered period of whole cipher if cipher has only one LFR?

Also if cipher has multiple LFR (both linear and non-linear), how can I calculate overall period? will it be equal to peroid of LFR with minimum period or there is some thing else?

Thank you.

While I do believe I understand what you are asking for, I will rephrase my own interpretation of the question, and apologize if I have misunderstood the question.

Question: How do you calculate the period of a stream cipher whose output is determined by multiple feedback shift registers (linear or nonlinear)?

"Determined by multiple feedback shift registers" is somewhat vague, so I will give some concrete examples.

Nonlinear combiners

First off, let's talk about nonlinear combiners. That is, the output of the feedback shift registers (linear or nonlinear) are combined in some way. The scheme would look something like this, where $R_1$, ... , $R_n$ are the shift registers and F is some boolean function.

Let $a_{1}$, ... , $a_{n}$ be the periodic sequences produced by $R_1$, .. , $R_n$ respectively and $b$ be the output sequence from F. Now let $P(a_i)$ denote the period of sequence $a_i$ $\forall i \in \{1, .. , n\}$ and $P(b)$ be the period of sequence $b$. Then the following holds:

$$
P(b) | lcm[P(a_1), ... P(a_n)]
$$
Where lcm denotes the least common multiple. Now, if the FSRs $R_1$, ... , $R_n$ were chosen such that $P(a_i)$ are pairwise coprime, we get a stronger bound:

$$
P(b) = \prod_{i = 1}^{n} P(a_i)
$$

In fact this condition ONLY holds if $P(a_i)$ are pairwise coprime. This result is due to Lidl and Niederreiter.

Decimation

Another way to construct a stream cipher from multiple LFSRs is by letting one LFSR clock another LFSR. In this section, I will not discuss NLFSRs.

We will consider two well-known examples, however in order to keep the answer somewhat brief I will not give full descriptions of them. Links will be given to resources below. Only two LFSRs are used in these examples, $R_1$ and $R_2$.

The Binary Rate Multiplier

A theorem due to Chambers and Jennings (1) show that under the following assumptions:

R1 has a primitive feedback polynomial of degree m, and hence a period of $P(a_1) = 2^m - 1$
R2 has a primitive feedback polynomial of degree n, and hence a period of $P(a_2) = 2^n - 1$
All prime factors of $P(a_1)$ divide $P(a_2)$
$gcd[\sum_{i=0}^{2^m-2}x_i, 2^n - 1] = 1$
Then we have that $P(b) = (2^m - 1)(2^n - 1)$

The Shrinking Generator

Shrinking generators are another way of combining LFSRs by decimation. In the original paper by Coppersmith, Krawczyk and Mansour (2), the following bound is given on the period:

$R_1$, $R_2$ have primitive feedback polynomials of order $r_1$, $r_2$ respectively.
$P(a_1)$, $P(a_2)$ are coprime.
Then $P(b) = (2^{r_1} - 1)2^{r_2 - 1}$.

Note that this is only to give you an idea, and only holds for the cases described above. Below I link to a couple resources for further reading on binary-rate multipliers (BRMs) and shrinking generators, if they are of interest.

(1): W. G. Chambers and S. M. Jennings, "Linear equivalence of certain BRM shift-register sequences," in Electronics Letters, vol. 20, no. 24, pp. 1018-1019, 22 November 1984.

(2): Coppersmith D., Krawczyk H., Mansour Y. (1994) The Shrinking Generator. In: Stinson D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg


why can't use only one way function to construct a PRG, and don't use the hard core predicate? The one-way function can expose some of the input and stay one-way, but still, that doesn't give the input.

As I read, we can't just construct a PRG from a OWF, but we need to use the hard core predicate of the OWF. Why is that?
Assuming $|f(s)| > |s|$, why is constructing a PRG in the following way wrong? $G(s) = f(s)$
Suppose $f$ is a permutation function. If $f$ gets a random $x$, then is $f(x)$ also random?

The first one is really simple, you already said it yourself:

  as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that?

I guess you're familiar with the formal statements, but informally speaking we have:

A function $f:\{0,1\}^* \rightarrow \{0,1\}^*$ is one-way, if we give the adversary $y = f(x)$ and the length $|x|$, and he has a negligible probability of finding $x'$, s.t. $f(x') = y$.
a PRG is a function $g:\{0,1\}^n \rightarrow \{0,1\}^m$, where the output is indisinguishable from $U^m$, denoting the uniform distribution over $m$ bits, and $m > n$

Now consider the following construction: $f'(x) = f(x)|1$, with $f$ being a OWF. Just concatenating a $1$ doesn't change much w.r.t. the security property of an OWF. And in fact, any adversary able to break $f(x)$ can easily be turned into an adversary for $f'(x)$ and vice versa. So $f'$ is a OWF iff $f$ is a OWF.

But it is quite obvious, that $f'$ is not a PRG, because the output of $f'$ can easily be distinguished from a uniform distribution, by just looking at the lowest ordered bit (always $1$ vs uniform).

But as you stated yourself: With a hardcore predicate, you can get a length extension. Maybe these lecture notes make it more clear how to achieve that (and why it's necessary). Informally speaking: A OWF does not need to be impossible to invert for all parts of its output - while a PRG needs to be indistinguishable from randomness over all its output.

  why constructing prg in the following way is wrong G(s) = f(s) assuming |f(s)| > |s|?

If we specify $f(x):\{0,1\}^n \rightarrow \{0,1\}^n$ a length preserving OWF, and use the construction above, we get $f':\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, which is also a OWF. This fulfills the length criteria of a PRG, but it is distinguishable. Being a OWF is not sufficient to be a PRG.

  f is a permutation function , if f gets a random x then is f(x) also random?

A permutation is a bijection from a set, e.g. $\{0,1\}^n$ into itself. This means, there are no collisions and every element has a single preimage. Thus, if we consider an input drawn uniformly at random from $\{0,1\}^n$, then the output is also uniformly distributed over $\{0,1\}^n$ - because the permutation has a 1-to-1 relationship between inputs and outputs. But that is also fullfilled for example by $p(x) = x + 1 \mod n$ over $\mathbb{Z}_n$, and I don't think that's what you meant. But this is entirely unrelated to the concept of one-way functions and PRGs.


Lattice reduction question regarding the capability of LLL and BKZ I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things.
LLL algorithm runs in polynomial time, but isn't capable of producing arbitrarily small basis, and is therefore not very relevant in cryptanalysis in most lattice-based schemes. Is that correct?
BKZ algorithm invokes a SVP (Shortest Vector Problem) oracle polynomial number of times, and the lower-bounded of the norm of the basis it produces is inversely proportional to the block size the SVP oracle operates on, regardless of the norm of the input basis; and the SVP oracle it uses runs in time exponential to the block size. Is that correct?

Yes, if you instantiate the SVP oracle in BKZ using sieving then the cost is exponential in time and memory. (If you instantiate it using enumeration then the cost is $k^{1/8\,k + o(k)}$). The norm of the output vector is expected to be $\delta_k^{d-1} \cdot \operatorname{Vol}(\Lambda)^{1/d}$ with $\delta_k \approx GH(k)^{1/(k-1)}$. Here $\operatorname{Vol}(\Lambda)$ is the volume of the lattice, and $GH(k) \approx \sqrt{k/(2\pi e)}$ is the Gaussian heuristic for a lattice with volume 1. This does not depend on the norm of the input basis.


Symmetric encryption construction (meet-in-the-middle attack) This is a question I had from an exercise session.

First we do DES in CBC encryption mode using a key $K_1$ and $IV_1 = O^n$.
Then we do DES in ECB decryption mode using $K_1$. And then DES in CBC decryption mode with a secret $IV_2$ and key $K_2$.

Is this construction safe against meet-in-the-middle attack?

Wouldn't the first two operations negate themselves because $C_1$ would decrypt into $P_1$?

The CBC ciphertext $C_1 \mathbin\| \cdots \mathbin\| C_\ell$ for plaintext $P_1 \mathbin\| \cdots \mathbin\| P_\ell$ under key $K_1$ is $$C_i = E_{K_1}(P_i \oplus C_{i-1}),$$ where $C_0 = \mathit{IV}_1$.  If you then apply ECB decryption under $K_1$, you'll get the ‘ciphertext’ $C'_1 \mathbin\| \cdots \mathbin\| C'_\ell$ where $$C'_i = E_{K_1}^{-1}(C_i).$$  If you then use CBC encryption with a different key and IV, you'll get $C''_1 \mathbin\| \cdots \mathbin\| C''_\ell$ where $$C''_i = E_{K_2}^{-1}(C'_i) \oplus C'_{i-1},$$ where $C'_0 = \mathit{IV}_2$.

If you simplify by canceling inverses, do either of the keys $K_1$ or $K_2$ still figure into this?  If yes, can you find a plaintext/ciphertext pair with an unknown intermediate quantity on which you could apply a meet-in-the-middle attack?  If no, do you even need to apply a meet-in-the-middle attack at all?


Does an adversary require the public key to perform operations when RSA or ECC is broken? If we had a way to break signature or encryption schemes (e.g. recover the key, recover plaintexts from ciphertexts, forge signatures), e.g. a quantum computer that was powerful enough to  break discrete log, would the attacker still need to know the public key used to make the encryption or verify the signature in order to decrypt or forge a signature?

That is, given merely the ciphertext or a signature without the public key, could such an attacker decrypt the ciphertext or forge other signatures?

I'm mostly interested in RSA and ECDSA, but if the situation is different for other schemes, I'd love to hear that.

TL;DR: yes, no, or maybe. Knowing the public key can only help an attacker. How much? It depends.

Usually, the public key is assumed known to all, hence its name; we'll assume it is not.

The answer depends on a lot of things: the cryptosystem, whether it is randomized or deterministic, if more than the ciphertext or signature is known (for example, if it is known matching plaintext/ciphertext pairs; if the message going with the known signature is also known; in the case of encryption, if something about the plaintext is known, like some redundancy ..). In general, the more is known, the easier it would be for the hypothetical attacker to break the cryptosystem even without the public key.

Also, the ability of the attacker matters: if s/he can break the cryptosystem with the public key, when by design of the cryptosystem s/he should not be able to do so, then perhaps she has resources not taken into account by standard security hypothesis, re-purposable for other tasks which could help towards breaking the cryptosystem without the public key: like a general-purpose quantum computer, or means of observing the internals of a supposedly impenetrable device.

Sometime, we can answer conclusively that the public key (or some other extra information) is required. For textbook RSA encryption $M\to C=M^e\bmod N$, a single ciphertext $C$, and unknown random plaintext $M$, the plaintext $M$ demonstrably can't be recovered from the ciphertext $C$, even by an arbitrarily powerful attacker, and even if s/he knows (a single) one of $N$ or $e$.

If we suppose the attacker has $C$, $N$, and its factorization as $N=p\cdot q$ with $p$ and $q$ odd primes, $p<q$, the set of possible plaintexts $M$ is all the $C^{j^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod N$ for $j$ such that this is well-defined. Typically, there are many such odd $j$ in $[3,\operatorname{lcm}(p-1,q-1)[$, and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.
Similarly, if we suppose the attacker has $C$ and $e$, the set of possible plaintexts $M$ includes all the $C^{e^{-1}\bmod\operatorname{lcm}(p-1,q-1)}\bmod(p\cdot q)$ for odd primes $p$ and $q$ such that this is well-defined, $p<q$, and $M<p\cdot q<2^n$ where $n$ is the number of bits in the actual $N$. Typically, there are many such $(p,q)$ , and although some lead to duplicates, the set of possible plaintexts is very large (proof welcome); and the attacker has no way to chose among theses.

Sometime, we can answer conclusively that the public key is not required, because the attacker can find it anyway. For textbook RSA encryption restricted to small public exponent $e$ (say $3\le e\le65537$) and modulus $N$ not unusually oversize, given just three known plaintext/ciphertext pairs $(M_i,C_i)$ for arbitrary $M_i$ (much larger than $N^{1/e}$, which is necessary for security), it is quite easy to compute $N$ with high likelihood by computing $\gcd_i({M_i}^e-C_i)$ until that's not 1, for the few candidates $e$ (a classical result, proof welcome). Therefore, an attacker able to break the cryptosystem with the public key can obtain it under the usual assumption of a few known plaintext/ciphertext pairs, then break the cryptosystem.


Password as it relates to various encryption schemes Suppose you have 2 drives you want to encrypt using different encryption algorithms, as an example: AES256 and Twofish.

I am aware that using the same password for both could potentially weaken either one or both because it would build a relationship.

But AFAIK it's only true if both passwords are hashed into the same bit string.

If this assumption of mine is correct what if:

Different hash algorithms are used? (could introduce another weakness?)
One of the passwords has a 1 appended to the end changing the hash.

Could be I got it completely or mostly wrong, in which case what should I do if I want to encrypt 2+ drives using different software using AES256/AES128. I threw in the Twofish to contrast this problem. I'm not sure if the AES implementation for all the different software is identical, XTC vs. CTS for example.

The goal is to have multiple encrypted partitions/drives across multiple devices utilizing multiple software (dm-crypt, truecrypt for example - assume implementation can vary, but not vulnerable implementation) but having the same password or at least nearly identical one.

If it's not possible then by how much am I weakening myself?

And what if I encrypt the same drive using both Twofish and AES and using the same password (Truecrypt, I think it uses different salts)?
The idea is even assuming AES can be broken somehow in reasonable time through some breakthrough in math or w/e there will be nothing to match to verify a good break other than Twofish ciphertext, or even if Truecrypt isn't so obliging since different salts are used they would still need to brute force the hash to get the actual password string?

So the bottom line, why do people keep saying using the same password is insecure? Do they actually mean the bit string cipher key? Since salts transform the same password into completely different bit keys...

If the password is salted and is long enough to begin with, then yes, using the same password should be fine. (Though a bit riskier than using different passwords --- say, if you have one password stolen by e.g. a keylogger)

The reason for the recommendation "don't reuse passwords" is that it's often hard (or sometimes impossible) to know if the underlying software is properly using salts.


Security of ciphersuite and key Is anyone able to cite resources that can be based on choosing a cipher suite?

In my case, for a VPN server (OpenVPN) I chose a set of ciphers:

TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256

It provides 128 bits of security. I have a dilemma regarding the length of the RSA private key. The 2048-bit key provides 112 security bits. If it is necessary to provide 128 bits, I would have to create a key with a length of 3072 bits - but this will have a significant effect on performance. If anyone could be able to direct me how to choose the right solution so that I could reasonably justify the choice would be great.

The difference between “112 bits” and “128 bits” matters for compliance to certain standards, but not for security. Both are out of reach of current computing technology. Furthermore, 112 bits for RSA-2048 is an estimate based on current attack techniques. A disruption such as quantum computers that are useful at cryptanalysis would break both RSA and AES, but in different ways — RSA would be trivialised at any pratcical key size, while symmetric cryptography would only have its “bit strength” halved.

So either you have to comply to some strict standard, and then you need to do what the standard says; or you don't have to comply to some strict standard, and then RSA-2048 is fine for authentication (which is what it's used for here). This is true even if you're exchanging long-term secrets: to break the security of your VPN by attacking the RSA part, the attacker has to breach it live, to cause the client to accept a fake server. The use of ECDHE provides forward secrecy, so there's no way to reconstruct the plaintext from the ciphertext and the server's RSA key later (if the attacker managed to break RSA, or more realistically to obtain the key). If you are concerned about very long-term secrecy, switching to AES-256 is actually more useful than moving away from RSA-2048 (and then you should also check that you're using a stronger curve, at least P384R1).

However there's little reason to use RSA these days. Elliptic curve cryptography has generally better performance for the same security. Your default choice should be TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (or AES_256 instead of AES_128, or SHA384 instead of SHA256, or CCM instead of GCM), sticking to widely-supported ciphersuites. EdDSA and ChaCha20_Poly1305 are also good choices if supported. RSA as used in TLS_(EC)DHE_RSA_xxx ciphersuites has better performance than elliptic curve methods on the client side (at the cost of worse server-side performance) if you're only authenticating the server, which is often the case on the web. But if the two sides authenticate each other, as is normally the case on a VPN, elliptic curves have better performance.


mixing two asymmetrical random number generator streams Knuth describes in "the art of computer programming part 2" an algorithm called "M" for mixing two streams of random numbers. This can be used to mix random number streams giving the assurance that the result is still random even if one (but only one) of the streams suddenly becomes predictable.

Now I have a situation where I do have two streams but they're asymmetrical: one produces +/- 800 bytes per second, the other +/- 340.

My question now is: what can I do so that I can still combine these two and accomplish the same as Knuth's algorithm?

I was thinking of "just feeding them to a hash" and use that result.
What do you think?

You can slow the faster stream down to match the slower (e.g. throw away about half the bytes) and use Knuth's algorithm. You will only run at the speed of the slower, but that's the only way to assure full entropy when only one of the streams is unpredictable.

If you want to also account for cases where both streams are only partially unpredictable, you could use a hash instead. E.g. take the SHA-256 of the concatenation of 40 bytes from stream A and 17 bytes from stream B, then truncate that to 17 bytes. For example, if the high bit in each input byte was predictable, this hash would still be completely unpredictable, while the XOR would not.

However, hashing may lose some entropy in the case where stream A is completely predictable, but stream B completely unpredictable.


What are the consequences (and potential mitigation) to poor entropy/RNG on server-side during ephemermal key generation and DH exchange I am using a hardware TRNG feeding the entropy pool on the client side. But, in a world of virtualized, headless server hosts, what are the cryptographic/security consequences for random numbers (or a RNG) of possibly poor quality (entropy) being used on the server side of ephemeral key generation and DH key exchange? Are there any mitigation strategies from the client side when server side operation is out of client's control?

In the worst case the result is key pair known to the attacker, in which case an attacker can act as a man-in-the-middle or eavesdrop, leaving you with no security whatsoever. There is nothing the client can do about that; even if his own key pair is fully random then the DH calculations can still be replayed by the attacker.

There is not all that much that a client can do other than to check if the public key received from the server hasn't been send yet. You could store all the public keys and compare new public keys them with previous values. This would catch repeating public keys; if one is found then stop the protocol: the server is insecure.

Fully testing the strength of the server-side RNG is very likely out of reach.

Note that with the advance of hardware-based RNGs the best mitigation against this can be done server side: use RDRAND. This is a user-level instruction that should be available from client VM's. If not used directly it can at least be used to put additional entropy in the randomness pool.

AMD uses the same instruction in their newer chips. The T1 systems from Sun/Oracle also have a hardware RNG. VIA uses a different mechanism (I/O based instructions) but with similar functionality. This kind of random number generation should be very high on your wish list for headless machines.

It could be that VM's also have some ways of mitigating risks (plugging entropy from the host system into the client VM), but I'm no VM expert.


How can DNA Computing solve very complex problems that can present in cryptography? This field was originally founded by Leonard Adelman of the University of Southern California in 1994. He proved the use of DNA as a computational form that solved the Hamiltonian problem.

By parallel search, it aims to solve some of the very complex problems that in cryptography.

How can it solve such complex problems?

The problem is scaling. Donald Beaver, looked at the factoring numbers with DNA. $10^3$-bit number will require $10^{20000}$ test tubes by using the Hamiltonian path idea of Adleman.

Adleman, also, observed that DES key search for 256 keys would occupy only a small set of test tubes. Let say $2^4$ tubes for $2^8$ keys. As a result we need $2^{56} / 2^{8} * 2^{4} = 2^{52}$ test tubes.

The previous statements are from previous DNA computing works directly on Cryptography. There are new studies on computing with DNA;

There is a promising technique, called CRISPR9 with many version that enables editing DNA even at home.
There is also interesting work called BLADE, where authors built 113 circuits from DNA.
And, the DNS USB memory, MinION.

Under these and other new improvements in DNA computing, in the very near future, one may come up with new results affecting Cryptography.

Update: How the Hamiltonian DNA computing is performed;

Encode the vertices with DNA and together with Watson-Crick complement. e.g. ;

ATLANTA DNA name ACTTGCAG complement TGAACGTC and

BOSTON  DNA nameTCGGACTG complement AGCCTGAC.

Here note that ACTT considered as the first name and GCAG considered as the surname.
The Edges defined as  GCAGTCGG where the first 4 char GCAG is the ATLANTA's first name and the last four char TCGG is the BOSTON's second name
Polymerases step; this gene produces the complimentary copies.
Ligases step; Ligases bonds the strand of DNA's together ( normally repairs DNA).
Polymerase Chain Reaction; used to remove all path not starting from starting node and not ending with the end node.
Gel-Electrophoresis, when current applied the negatively charged DNA molecules start to moves to the anode. The interesting part; the longer the DNA strand the slower it moves. So separation by length.
DNA synthesis. The DNA info extracted.

As one can see, the process completely biological, except Gel-Electrophoresis which is not a part of DNA process in nature.

This is almost the view of the step from bird fly of the article of Adleman in Scientific American. A more detail can be found here.

Hamiltonian path to Factorization

Now, let talk about how the Hamiltonian Path problem can be turned into a factorization problem that Donald Beaver used. This is mostly from, normally the reduction is mentioned in the famous Introduction to Algorithms book of Cormen at. al.

Build a non-deterministic polynomial-time turing machine;
given an $n$ and $k$ accepts if there exists some $m$ where $1<m<k$ and m divides n, or rejects otherwise.
For each query (n,k), by the Cook/Levin reduction  to construct a boolean circuit which is satisfiable iff the Turing machine accepts (n,k).
Reduction from Circuit-SAT to 3-SAT.
Reduction 3-SAT to Hamiltonian Path.
Solve the Hamiltonian Path problem with DNA.

Reductions are answer-preserving, so backward available.

This is the process that Donald Beaver looked into and said

  Even in the case of factoring, if every path in a superpolynomial computation is assigned a molecule, then a superpolynomial number of molecules will be needed. Merely fitting these molecules into a polynomial volume is an impossible task, but a necessary one: if the molecules are going to have enough time to mix and react, then light must be able to pass from one side of the test tube to the other within polynomialtime.
  This impossible task does fortunately expose new avenues for further research, leaving open the question of whether black-hole algorithms for factoring exist.

Any other algorithm, with current knowledge, must have to fallow the same reduction step to the Hamiltonian Path problem and will face the same impossible task.


Quantum key exchange skepticism/confusion I was hoping somebody could explain some issues I have with quantum key exchange that I don't quite understand. I've read bits and pieces about BB84 but I'm sure my questions probably apply to other schemes also. My understanding of quantum key exchange is the following (please correct me if I'm wrong):

Alice creates a random bit string and for each bit, selects a random filter (say x or +).
she encodes these choices as a polarized photon and sends over the quantum channel to Bob
Bob guesses which filter to use, if he guesses correctly (assuming no Eve messing around for the moment), he'll get the bit Alice intended. If he guesses the wrong filter, it's 50% chance he gets the bit Alice intended
Alice and Bob exchange what filters Bob should have used; they ignore the bits where Bob used the wrong filter
Alice and Bob then pick a sample of their bits and find out if there are any discrepancies, if there are a lot, they try the key exchange again. If there aren't that many, they proceed to do parity checks to agree on the exact right key, then then use the leftover hash lemma to make sure Eve doesn't know anything much

Please correct me if I'm wrong with the above.
My questions are the following:

What's to guarantee authentication or message integrity (particularly when Alice and Bob are exchanging which filters were correct and so on)?
If Alice and Bob only count the bits where they have the same filter, then isn't it 50/50 whether or not Eve guesses the correct filter also? So can't Eve see about half the key without Alice or Bob even knowing!?
What proportion of discrepancies is too much and why?
We always assume Eve is passively observing, can't she do more than that (like change the polarization to whatever she likes and so on)?
How does the leftover hash lemma actually work?

Apologies if any of the above are stupid questions but I'm very confused with this protocol. 1) and 2) are particularly important to me because they seem like major, major problems I can't seem to understand and I can't find a good article that really explains it properly so an explanation from here would be great.

Many thanks for any help with any question.

Let’s take your questions in order. Note that I’m a physicist working in quantum cryptography, so my opinion on this might be biased
1. What about authentication ?
The classical channel between Alice and Bob has to be authenticated in order for the protocol to work. Formally, this is a pre-requisite for quantum key distribution (QKD), and is not part of the protocol.
In practice, we often uses information theoretically secure schemes (see this answer for pointers), which consume secret keys. The point is to generate key through QKD faster than the authentication consume it, making the whole system a key expansion system.
2. Wait ! Can’t Eve guess half of the basis (filters) without being detected ?
No ! That’s the whole point. Eve does indeed know half of the key, but she’s detected by Alice and Bob. Eve choice and Bob’s choice are independent, so, Eve will have chosen the wrong filter for half of the photons kept by Alice and Bob, and this wrong filter choice would change the photon polarization, inducing errors in Alice and Bob strings (in this case $\tfrac12\times\tfrac12=25\%$ error.) detected in step 5. of your description of the protocol. This lead us to the next question .
3. What is the maximal error rate ? And why ?
An exact answer to this question is still a research subject, and is obviously protocol dependent, but the same ideas (with different numbers) are essentially valid for all protocols.
The attack you proposed is known as an intercept-resend attack, describing an attack where Eve measures the photons and resends something to Bob depending on her measurement. It is proved that there is no way for Alice and Bob to extract a secret key when such an attack occurs, which corresponds to 25% error rate for BB84 protocol. However, this is only an upper bound on the tolerable error rate, and this attack has no reason to be optimal.
To find a lower bound, one uses different techniques to optimize over the sets of attacks, which also depend on the exact way the final key is extracted (after error correction and privacy amplification, in order to use the lefover hash lemma). A commonly used lower bound is $e=11\%$ which corresponds to a case where Eve gather as much mutual information on Alice's string as Bob, but some research papers have some way to tolerate a higher error rate.
4. We always assume Eve is passively oberving ...
NO ! The whole point of QKD is that she cannot passively observe ! Heisenberg uncertainty principle ensures that any observation is active and disturbs the system. Usually, we assume Eve can do anything, but the tricky part is to properly define “anything”, and optimize over this set.
5. How does the leftover hash lemma actually work
I’m a physicist, and I will not give you a theoretical answer on this. You can read the publications of Renato Renner to have a rigorous analysis of this lemma in the presence of a quantum adversary.
On a practical point, Alice and Bob use error correcting codes (ECC) to correct the errors in order to have the same key. Doing that, they leak some information to Eve (at most the number $c$ of exchanged ECC bits, $c≥h(e)$ for BB84). This leakage is added to amount of information which has leaked during the photon exchange, and which can be evaluated from the error rate $e$ (at most $h(e)$ for BB84). Alice and Bob pass their key through a universal hash function, with an output small enough ($<1-c-h(e)$) to ensure the leftover hash lemma applies.
Bonus question (from the comments) : is QKD relevant ?
I’m an academic, and I find it interesting from a fundamental point of view. It clearly changes the way physicist think about quantum mechanics, and is relevant in this aspects.
Whether it will soon be relevant to use QKD now in an industrial setting is a question of engineering, economics, future prediction and beliefs on what the NSA actually does ...
QKD is more difficult to implement than classical cryptography, because it needs specific hardware and has a limited range. However, it is indeed possible today to make QKD systems working over 200km, and small networks exist across a few cities. Some people work to make it practical and cheaper, and they may succeed.
In my opinion, the only reasonable application of QKD today is on securing expensive data which should stay secret for more than a decade (i.e. on an horizon where technological evolution is difficult to predict). The two properties which make QKD useful in this case are :

Its security relies on something completely independent than classical cryptography and it is easy to combine the two such that both have to be broken in order to break the scheme.
In order to break an imperfect implementation of quantum cryptography (aka quantum hacking), one need to break it at the moment where the photon exchange take place. You cannot record the messages in the hope that a weakness in the protocol will later be  found.


Making Pascal Paillier' output absolute Can we make subtraction result of cipher texts encrypted by Pascal Paillier absolute. Just like we use method Math.abs() in Java ?
For example, if we subtract 0 from 1: 1-0 = 1, it is positive but 0-1 = -1. My requirement is that this subtraction should always be positive like:

   1 - 0 = 1
   0 - 1 = 1

Is there anyway i can achieve it please?

No, or at least, if you can, you have an Extremely Significant result; you've just shown that Paillier is a Fully Homomorphic system, and so it could perform any operation on encrypted data (and in a way that's significantly more efficient than any other known FHE system).

Here's why: The $|a - b|$ operation is effectively an $XOR$; if the ciphertexts $a, b$ are known to be either encrypted $0$ or $1$ values, then the result will be a 1 if they differ, and 0 if they are the same.

In addition with a bit more work, we can compute an $AND$.  To do this, we could first compute $a + b - |a - b|$.  This value will be an encrypted 2 if $a, b$ are both 1, and 0 if either is a 0.  Then, multiplying this value by the constant $(n+1)/2$ (which can be done in $O(\log n)$ homomorphic additions) will give us an encrypted 1 if both $a, b$ are 1, 0 otherwise (or, on other words, an $AND$ operation).

The combination of the $AND$ and $XOR$ operations are complete; that is, any function (computable in bounded time) can be implemented by a sufficient number of them.

We don't believe that Paillier is an FHE system, hence either what you're asking for is infeasible, or we have a really exciting result on our hands.


Outlook of trustworthiness of SHA-2 On the Wikipedia page of SHA-2, the following is written:

Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512, and collision resistance for 46 out of 64 rounds of SHA-256.

Can someone explain in simple terms what that means?
Also, for SHA-1, the Wikipedia page currently states:

Since 2005, SHA-1 has not been considered secure against well-funded opponents;[4] as of 2010 many organizations have recommended its replacement.[5][6][7] NIST formally deprecated the use of SHA-1 in 2011 and disallowed its use for digital signatures in 2013. As of 2020, chosen-prefix attacks against SHA-1 are practical.[8][9] As such, it is recommended to remove SHA-1 from products as soon as possible and instead use SHA-2 or SHA-3. Replacing SHA-1 is urgent where it is used for digital signatures.

All major web browser vendors ceased acceptance of SHA-1 SSL certificates in 2017.[10][11][12] In February 2017, CWI Amsterdam and Google announced they had performed a collision attack against SHA-1, publishing two dissimilar PDF files that produced the same SHA-1 hash.[13][2] But SHA-1 is still secure for HMAC.[14]

Microsoft has discontinued SHA-1 code signing support for Windows Update on August 7, 2020.

So, ten years after the original publication, the hash algorithm already wasn't deemed secure enough to be trusted anymore.
SHA-2 was published in 2001. Given the advancements in computing power, does it even make sense to use SHA-2 in new technology? Isn't it reasonable to expect that very soon it won't be trustworthy anymore, seeing how SHA-1 wasn't trustworthy after ten years? Shouldn't we use SHA-3-512 wherever possible to be on the safe side looking forward?

AES-128 (2000) has been around for 20 years and there is no attack faster than brute-force, except the multi-target that affects all block ciphers and hash algorithms. As you can see, an algorithm can withstand attacks for a long time with a good design.
SHA-1 (1995) has 160-bit output, which results in 80-bit generic collision resistance. It was good for the 1990s.  The NIST removed it from signatures in 2013. Today, this is already low, by today's standards where it is considered that we need at least 112-bit security. The chosen prefix-collision attack on SHA-1 (2017) is faster than the generic collision attack; it is faster 100,000s ($\approx 2^{16}$) of times. Maybe in the future, one can present faster collision findings like MD5's imminent collision findings, we don't know.
Now, SHA-256 (2001) has 128-bit generic collision resistance with a 50% probability under the birthday attack. The 128-bit is not easily accessible. The public example is the Bitcoin Miners that they can collectively reach $2^{92}$ double SHA-256 hashes per-year (it is almost $2^{93}$ after two years). Therefore they need $2^{36}$-year to find a collision with 50% probability.
SHA-512 (2001), on the other hand, has 256-bit generic collision resistance. 256 bit is not vulnerable.
SHA-3-512 has the same generic collision resistance as the SHA-512. The main differences are these; the SHA-3  series uses sponge construction and has resistance to length-extension attack whereas the SHA-2 series uses MD construction and if not trimmed, they have no length-extension resistance.
There is also a quantum attack side of the story like the work of Brassard et. al dropped collision finding into the $\mathcal{O}(2^{n/3})$-time and requiring $\mathcal{O}(2^{n/3})$ storage in the total cost of $\mathcal{O}(2^{2n/3})$. This and other quantum attacks are theoretical and should not be considered a real threat. Actually, they are not better than classical algorithms like the parallel $\rho$ based collision search algorithm of Van Oorschot and Wiener based has $\mathcal{O}(2^{n/2})$. See in details in this answer

So, like 10 years after the original publication, the hash algorithm already wasn't deemed secure enough anymore to be trusted.

NIST and the designers of the SHA series (except SHA3) has come from a long way to design a better hash algorithm from the MD5 and earlier MD hashes, SHA-0, & SHA-1. We don't compare something by saying that if $x$ was broken in $y$ years then since $z$ is $y$ years old it must no longer be secure. We compare according to published attacks. SHA-256 has been there for almost 20 years withstanding the classical attacks. Yet no problem seems on the horizon. If you want to be secure for the foreseeable future use SHA-512, besides it has 64-bit CPU support ( SHA-256 has 32-bit CPU support).

SHA-2 was published in 2001, given the advancements in computing power, does it even make sense to use SHA-2 in new technology? Isn't it reasonable to expect that very soon it won't be trustworthy anymore, seeing how SHA-1 wasn't trustworthy anymore 10 years after inception? Shouldn't we use SHA-3-512 wherever possible to be on the safe side looking forward?

The computing power has limits. We have already seen that reaching $2^{100}$ is not easy, and $2^{128}$ has a long time to be secure for direct brute-force.
If there are no new attacks that are going to be performed and much better than the SHA-1's attacks on SHA-2, then there is no problem for the SHA-2 family. However, we always assume that the attacks always become better, not worse.
Conclusion:
Normally SHA-256 is fine with 32-bit CPUs; 128-bit is classically impossible to break. To take the advantage of 64-bit CPUs use SHA-512. Similarly, you can use SHAKE128/256 and BLAKE2 that has both 32 and 64-bit CPU designs. To take advantage of parallel hashes use  ParallelHash (parallel version for SHA-3) and BLAKE3 (parallel).

Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512, and collision resistance for 46 out of 64 rounds of SHA-256.

This is the short story of the big picture

The cost for 52 out of 64 round pre-image attacks of SHA-256 is $2^{255}$
The cost for 57 out of 80 round pre-image attacks of SHA-512 is $2^{511}$

These attacks are on the reduced round of the SHA-256 and SHA-512, i.e. if the SHA-256 uses 52 rounds then the cost of finding pre-images will be $2^{255}$ instead of $2^{256}$ and even on average you will find the pre-image with brute-force with $2^{255}$-time
As we can see, the cost is already far from reachable. While reading an attack in hash functions one must look at all requirements; the complexity compared to generic attack, the memory requirements, possible reduced rounds, or the success of the attack on how many rounds.


How is BCrypt secure when it uses a static dataset for blowfish hashing? I'm planning on using this Javascript BCrypt implementation, but as you can see in the code, it uses a 4KB precalculated dataset for the P and S parameters needed for blowfish hashing. I've also tracked a similar dataset back to the original C BCrypt code.

Shouldn't blowfish hashing use a dynamically calculated dataset? How can this be secure? I'm going to do this client-side, so if an attacker reads the statically stored dataset, will it make it easier to find a collision for the BCrypt hashed value?

The BCrypt password hash algorithm is based on a modified version of the Blowfish encryption algorithm. The $P$ values are the round subkeys (used for XORing with the data), and the $S$ values are components for substitution boxes, both used in a Feistel network.

The initial values for $P$ and $S$ are the same as in the original Blowfish algorithm, and come from the hexadecimal digits of the circle constant $\pi$.

During the key schedule, these values $P$ and $S$ are used to create new (key-dependent) values, and then replaced by those. One critique point of Blowfish always was that it's key schedule is relatively slow (about as much as encrypting 4 KB of data - since we actually encrypt the zero string with the current $P$/$S$ values to create the new ones, and the size of $S$ and $P$ together is just 4 KB).

Bcrypt takes this slowness to a new level, using an expensive key schedule instead of the default blowfish key schedule, which takes a (configurable) much longer time.

This essentially (after a more complicated initial round which includes both salt and password) executes the normal key schedule $2^{\operatorname {cost}}$ times with each of salt and password as input, where $\operatorname{cost}$ is the cost parameter (the original bcrypt paper proposed $\operatorname{cost} = 6$ for normal user accounts, $\operatorname{cost} = 8$ for the administrator account). This is thus (time-)equivalent to encrypting $8·2^{\operatorname{cost}}+4$ KB of data with normal blowfish.

Then, a constant string (OrpheanBeholderScryDoubt) is (64 times) encrypted with the normal blowfish encryption using the thus created $P$ and $S$ boxes as state, producing an 192 bit string, which is then considered the bcrypt output (which is normally stored together with the salt and the cost parameter).

As we can see, the actually used values of $P$ and $S$ are very non-constant, depending strongly on the salt and password input. The initial values being fixed is not a vulnerability, but necessary to get identical output for identical input on each implementation.

Coming from the digits of $\pi$, they also quite likely don't contain a backdoor created by the designers of the algorithm (a nothing-up-my-sleeve-number).

Also, for a password hashing algorithm a collision attack is not the most important attack: An attacker finding two passwords which give (for a specific salt or pair of salts) the same hash, has about no advantage for finding the passwords to existing hashes (which also quite likely are using different salts).


Bouncy jdk 1.51 Serpent KAT tests vs Nessie vectors Having a little trouble getting Nessie vectors working with the Bouncy Castle SerpentEngine. Do the Nessie vectors require a mode or some pre-processing?
Nessie Serpent 128, set 1, vector 0 reads:

key=80000000000000000000000000000000

plain=00000000000000000000000000000000

cipher=264E5481EFF42A4606ABDA06C0BFDA3D

http://www.cs.technion.ac.il/~biham/Reports/Serpent/Serpent-128-128.verified.test-vectors

Bouncy Castle SerpentTest.js, vector 10 reads:

key=80000000000000000000000000000000

plain=00000000000000000000000000000000

cipher=49afbfad9d5a34052cd8ffa5986bd2dd

http://grepcode.com/file/repo1.maven.org/maven2/org.bouncycastle/bcprov-ext-jdk15on/1.51/org/bouncycastle/crypto/test/SerpentTest.java#SerpentTest.0tests

Why the different expected output?

Bouncy Castle seems to be using a reversed byte order for inputs and outputs when compared to NESSIE test vectors.

In order to replicate the NESSIE vector in Bouncy Castle, the order of all inputs and outputs needs to be flipped at the byte level, therefore the following results are given from a NESSIE compliant implementation (Set 1, Vector 120):

key =    00000000000000000000000000000080
plain =  00000000000000000000000000000000
cipher = DDD26B98A5FFD82C05345A9DADBFAF49

Note the first key byte is now in the final position, and the ciphertext when reversed matches BC vector 10. Additionally if we perform a Monte Carlo test, the results should be similar:

Serpent Encryption, ECB Mode, 128-bit key

COUNT =      0
KEY =        d692af3ea36f5ef30de8c5eb79a8fb31
PLAINTEXT =  14f63ff537a39296008945f7125ea070
CIPHERTEXT = 2d74412f3d89016083c93b4d0fa553fc

These results match vector 14 in reverse byte order, using a 100 block loop test, the BC test does not seem to perform an outer key loop like other Monte Carlo test implementations, such as NIST CAVP. The CAVP MCT performs 100 outer key loops with 1000 inner block loops for testing AES implementations. If continued, next iteration in the key loop would be as follows:

COUNT =      1
KEY =        fbe6ee119ee65f938e21fea6760da8cd
PLAINTEXT =  2d74412f3d89016083c93b4d0fa553fc
CIPHERTEXT = 4597017beb21a4c6c75acb85ac4645f7


Msieve & Yafu - RSA Exponents and bruteforcing I am a layman in regards to the math behind RSA (and in general, relatively), and my goal is to bruteforce a large quantity of 512-bit RSA keys. Having searched around, I see that msieve, yafu, and an Amazon FaaS (Factoring as a Service) program are the main candidates, however, cracking the keys with Amazon would be impractical cost-wise, and the keys I would like to crack (for a long-shutdown videogame I'll specify, nothing malicious), have an exponent of 17.

In short, I would like to know...

If specifying the exponent alongside the modulus is needed, and if so, how to actually specify the exponent (preferably with msieve, since according to this it's the only algorithm proven to crack a key of this size) as there seems to be no option for that (msieve version 1.53).
Whether having multiple computers/CPU cores would speed this proccess up, and how to use them if possible (this and the msieve readme seem to imply this is the case). I'm also a bit curious as to how it's done in a mere few hours via Amazon despite the above programs being single-threaded.

The fact that public exponent $e$ is $17$ does not help. The standard attack against RSA keys generated correctly (except for the small size of their public modulus $N$) is to factor $N$. That's the only input of the factoring task, which is where overwhelmingly most of the effort goes.

$e$ is involved only in preparing the final form of the private key, which is easy: the code to prepare the private key from $e$ and prime factors $p$, $q$ of $N$ is in anything that generates an RSA key in the desired format. For the  $N(n,d)$ format, a working $d$ is $e^{-1}\bmod((p-1)(q-1))$ and that's a one-liner in Python: d=pow(17,-1,(p-1)*(q-1)).

At 512-bit, GNFS is the algorithm of choice and the two usual bottlenecks are sieving and the matrix step. Multiple CPUs definitely help for sieving. For the matrix step, it's complicated, but a machine with large memory is required.

Have a look at CADO-NFS for an implementation.

It is disputed if GPUs are useful at factoring, and I have yet to find any account of actual use at 512-bit.

If you have multiple $N$ with some generated by a defective process, there might be special attacks computing the GCD for pairs of $(N_i,N_j)$, $i<j$. When one is found that is not $1$, that trivially factors $N_i$ and $N_j$. It's worth trying if the "long-shutdown videogame" was using a poor key generator, even more so in a CTF context. There are improvements to this, both computational and to extend the class of exploitable weak generators; see this.


How is the matrix A related to the lattice space L in SIS? Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard problem when it's definition doesn't seem to include a lattice.

Following this, the restriction on the the vector $x$ $\leq \beta$. Where does $\beta$ come from? I understand by restricting the value of $\beta$ you increase the hardness of the problem but at what point do you is it defined?

About the basis
As stated in the other answer, the lattice directly related to SIS is actually the $q$-ary lattice defined as
$$\mathcal{L}_q^\bot(A) := \{ u \in \mathbb{Z}^n : Au = 0 \mod q \}.$$
And its basis is not the matrix $A$. To construct a basis to this lattice, one usually suppose that $A$ has $n$ linearly independent columns (let's say, the first $n$) and write $A = [A_1 \quad A_2]$ with $A_1$ being an $n\times n$ matrix invertible over $\mathbb{Z}_q$, then the following matrix $B$ is a basis:
$$
B =
    \begin{pmatrix}
    ~q\cdot I_n~  & -A_1^{-1}A_2 \\
    ~\vec 0~  & I_{m-n}
    \end{pmatrix} \in \mathbb{Z}^{m \times m}
$$
About the hardness
Actually, it could be a hard problem regardless its connections with lattice problems. But it is connect to lattices in several ways. First, it is obvious that finding short vectors in $\mathcal{L}_q^\bot(A)$ gives us solutions to SIS. Moreover, it has been proved that if one can solve SIS in polynomial time in average, then one can solve hard lattice problems.
Roughly speaking: if you had an algorithm to solve SIS with non-negligible probability (for instance, your algorithm could work one time out of one million), then you would have an algorithm to solve approximate versions of GapSVP and SIVP).
About the value $\beta$
The value $\beta$ is a parameter of the problem. It is easy to find $u$ such that $Au = 0 \mod q$ (just use Gaussian elimination), what may be hard is to find a short vector satisfying this equation. But how do you define short? Using $\beta$ as an upper bound to the length.
These are standard facts: if $\beta \ge q$, then $u = (q, 0, 0,..., 0)$ is a valid solution, therefore, SIS is trivial for such values of $\beta$. If $\beta$ is too small, then maybe there is no valid solution. If $\beta \ge \sqrt{m}$ and $m \ge n\log q$, then it is guarantee that there exist at least one valid solution.


Does there exist a deterministic, invertible function $\{0,1\}^n \rightarrow \{0,1\}^n$ that is not a bijection? One of the requirements for a function to be a PRP is

  For any $K \in \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n \rightarrow \{0,1\}^n$.

Taken from Wikipedia

Does this have to be explicitly said? Is it even possible for this not to be true for a deterministic, invertible function where the input and output domains are the same?

Does this have to be explicitly said?

You stripped the preceding context from that quote:

  Let $F$ be a mapping $\{0,1\}^n × \{0,1\}^s → \{0,1\}^n$. $F$ is a PRP if

  For any $K ∈ \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n$ to $\{0,1\}^n$.
  [...]

Not all mappings $F : \{0,1\}^n × \{0,1\}^s → \{0,1\}^n$ are bijections for all choices of $K$, so yes, the definition certainly has to state the bijectivity requirement.

  Is it even possible for this not to be true for a deterministic, invertible function where the input and output domains are the same?

You're reading the definition with an implicit assumption in mind that the function must be invertible, but the clause you're pondering is the one that actually states the requirement.


Brute forcing the value of m in RSA I looked into the math behind RSA and seem to understand the basic encryption and decryption scheme.

Let's say there are two parties, Alice and Bob, who wish to communicate and secure their conversation using RSA.

Alice generates two prime numbers ($p$ and $q$), uses those to compute $n = p q$, and $\phi(n) = (p-1) (q-1)$. Then she computes two values, $e$ and $d$ which are relatively prime to $n$.  She sends over the publicly accessible values $n$ and $e$ to Bob, who encrypts his message $m$ by computing a value $c = m^e \bmod n$. He sends this publicly accessible value to Alice who then uses $d$ to compute $m = c^d \bmod n$.

If an eavesdropper intercepts their conversation and gets the value of $c = m^e \bmod n$ and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?

If an eavesdropper intercepts their conversation and gets the value of $c$ (namely, $m^e \bmod n$) and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?

Yes!

This is part of why we do not use the function $x \mapsto x^e \bmod n$ to encrypt messages directly.  Instead, a sensible sender will pick $x$ uniformly at random from all positive integers below $n$, use $k = H(x)$ to encrypt a message $m$ with their favorite symmetric-key authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and then transmit $x^e \bmod n$ alongside the ciphertext, so that the receiver can recover $x$ and derive $k$ to decrypt the ciphertext.

This system is called RSA-KEM.  There are also more complicated systems like RSAES-PKCS1-v1_5 and RSAES-OAEP, where we pick $k$ up front and then shoehorn it into something that's close to a uniform random positive integer below $n$, but invariably we use a symmetric-key authenticated cipher to encrypt the actual message.

A little more generally, this goes beyond RSA: any public-key encryption scheme is necessarily randomized, because otherwise anyone could verify a guess about what plaintext is concealed in a ciphertext $c$ is simply by testing whether $c \stackrel?= E(m)$ for a candidate message $m$ where $E$ is the public-key encryption function.


What does Maj and Ch mean in SHA-256 algorithm? I'm guessing they're some kind of standard function but what do they do and what do the names mean? A little explaination or link me to an article would be great.

The definitions given in FIPS 180-4 are
$$\begin{align}
\operatorname{Maj}(x,y,z)&=(x\wedge y)\oplus(x\wedge z)\oplus(y\wedge z)\\
\operatorname{Ch}(x,y,z)&=(x\wedge y)\oplus(\neg x\wedge z)
\end{align}$$
where $\wedge$ is bitwise AND, $\oplus$ is bitwise exclusive-OR, and $\neg $ is bitwise negation. The functions are defined for bit vectors (of 32 bits in case fo SHA-256).

$\operatorname{Maj}$ stands for majority: for each bit index, that result bit is according to the majority of the 3 inputs bits for $x$ $y$ and $z$ at this index.

$\operatorname{Ch}$ stands for choose (source: poncho) or choice, as the $x$ input chooses if the output is from $y$ or from $z$. More precisely, for each bit index, that result bit is according to the bit from $y$ (or respectively $z$ ) at this index, depending on if the bit from $x$ at this index is 1 (or respectively 0).


What is Polymorphic encryption? Well i have downloaded some cryptographic algorithm. Do there are those I didn't understand so this is my question: What is polymorphic RC4 or Polymorphic xor encryption?

I heard this in malware encryption.

Perhaps you are referring to a polymorphic virus?  This is a virus which consists of a decryption program along with the actual virus code which is encrypted.  When the virus runs and subsequently spreads, it re-encrypts itself with a different key, thereby appearing to be different each time it propagates.


Key exchange problem I've found the following problem in one of my courses. Any tips on how to solve this would be appreciated!

  Alice has the key pair $(pka,ska)$. Bob has the pair keys $(pkb,skb)$. They want to establish a secret common key $k$ for a fast encryption (using $AES$).

  How?
  How if both want to participate in choosing the key (none of them trusts the other)

Depends how secure you want it to be. Do you want to be safe against MITM, against passive attackers, against active attackers, against replay attacks, ... and so on.

Even though that posting links is not that good, I would strongly suggest to read that paper:
http://cs.unc.edu/~fabian/course_papers/needham.pdf
"Using Encryption for Authentication in Large Networks of Computers" - Needham, 1978.

On the second page it has a nice description of quite a secure protocol for that. ("Protocol 2. With Public-Key Algorithms "), though you would have to modify it since you don't have a CA which both parties trust. (and, as a result, be vulnerable to some attacks)

Also, take a look on TLS. TLS could be with server authentication, client authentication, or both present or both missing. Option 4 is for you, since you do not have any CA's mentioned in your question.


Implementing a web app where the server cannot decrypt its own data? I'm a cryptography novice, but I think that the world needs to move towards an "encrypt everything" mentality as much as possible.  As a result, I've been thinking a lot about ways to build a web app that stores all data on the server in a way that the server can't decrypt the data even if it wanted to.

Here's my thinking.  I'd love feedback.

(Let me start by saying everything would be done over SSL.  This isn't meant to protect the data over the wire, but to protect the data from the server.)

Server = any web server/technology, Client = a JavaScript web app

When a user signs up OR changes his/her password:

Either an RSA key pair is provided by the customer (high security, less convenient) OR a key pair is generated by the server and sent to the client (customer has to trust that we won't store the private key, but more convenient)
Also, a UUID is generated by the server and sent to the client
The user enters their password into the client—this password is NEVER sent to the server
The client uses PBKDF2 to generate a secret key
This secret key is used to encrypt:

The user's private key
The UUID sent from the server

The client then sends the following to the server:

The public key
The encrypted private key
The original UUID
The encrypted UUID

When a user logs in:

The client sends the username to the server
The server responds with the unencrypted UUID & a new UUID
The client sends the following back to the server:

The unencrypted UUID
An encrypted copy of the UUID using the same method as above
The unencrypted new UUID
An encrypted copy of the new UUID

If the encrypted copy matches the encrypted copy on the server, the user is considered authenticated, and the new unencrypted/encrypted UUID pair is stored for the next time this used needs to log in
The server responds with an authentication token that is used for all further requests during this session, as well as the public key and encrypted private key

As the app is used

All data is encrypted using the public key before it's sent to the server, and decrypted using the private key in the client.  If the server has to add content to the database, it's encrypted using the public key so that the server only has access to the data while it's generating it.  Obviously this would not work in all use-cases, particularly highly relational data, but I think if the structure of the data is generally maintained, it wouldn't matter what the content was.

For example:

{
    "username": "jsmith",
    "name": "John Smith",
    "message": "Hello there!"
}

Can be handled by the server very similarly to:

{
    "username": "U2FsdGVkX1+B9f7mMjoU9sWnYU79eN2IiDxNsetNeUI=",
    "name": "U2FsdGVkX188VmG67BS5lGDEs8NAUsQrG8eaVmyOlIg=",
    "message": "U2FsdGVkX1+7cqObxGFq2ZR3rc05NznGdoPENDujAa4="
}

So maybe not all metadata could be encrypted, but it's definitely a step in the right direction.

I'd love feedback!  Like I said, I'm a complete novice, so I could have made a terrible assumption somewhere in there, but it seems like it theoretically would work…

One final note: I recognize that JavaScript isn't ideal for encryption.  That said, I think it's acceptable in this case because we're using JavaScript as an added layer on top of SSL & all other existing security best-practices.

all those concerns have been studied a lot and still are. I'll try to give some keywords for them.

  a web app that stores all data on the server in a way that the server can't decrypt the data even if it wanted to.

Solution for this is User-side encryption. That's why, forget about the server chosing the encryption key himself.

It's quite well spread already. Problems happen when the server is supposed to do something with the data, since he's unable to read it. To tackle this there is a lot of efforts being put in homomorphic encryption, with wich you can manipulate encrypted data without the need (and the possibility) of decrypting it.

When the Server "Has to add data by himself" it works to use public key mechanism, but you cannot have a proof that he did not keep a copy of it, so this falls back to protecting the data against an external attacker (someone who steals the hard disk for instance), disk encryption should do the job and is available almost everywhere.

About the way of logging in without revealing the password, it seems that it called Zero-Knowledge Password Policy Checks (ZKPPC). See this recent paper about it: http://eprint.iacr.org/2014/242


Zero knowledge-proof for discrete log that is not honest-verifier Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge of the discrete logarithm of some group element is honest-verifier zero-knowledge, meaning that if the verifier chooses his challenge randomly, then he learns nothing about the log.

However, I'm looking for a zero-knowledge proof of knowledge of discrete logs that is not honest-verifier zero-knowledge; I want it (and particularly the simulator) to be able to deal with any verifier, honest or not. Preferably as efficient as possible, on the prover's side. My Google-fu seems to have deserted me; does anyone have any pointers?

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is only HVZK.

Another answer is to reduce the size of the challenge space from $p$ (the group order) to $\log(p)$. This gets you full ZK, but your soundness error drops to $\frac1{\log(p)}$ too so you have to repeat the whole protocol $O(\log(p))$ times to get the same soundness as one HVZK Schnorr execution. This repetition doesn't destroy your ZK property however.

Jan Camenisch's work contains a good description of these issues if I remember well.


Why do we require a CSPRNG's output to be indistinguishable from true random? Everywhere I read, indistinguishability of output from true random is stated as a requirement for CSPRNGs. However nobody bothered to give the rationale for such a strong requirement.

Specifically, Yarrow and Fortuna both use a block cipher as the generator, and both limit the amount of output that can be produced by a particular key. The key is changed (aka rekey) once the limit is reached. Their reason is that since the block cipher does not generate duplicate output blocks in their design, the attacker can request for a large amount of output from the PRNG, find that there are no duplicate blocks, and determine that the output is not true random. So what?

The only information the attacker can get from this is the cipher's block size, and this doesn't weaken the security one bit. Furthermore this would have been public knowledge if the implementation was open source. I don't see how the lack of duplicate blocks would weaken our security.

We simply strive for crypto that's as close as possible to ideal. Indistinguishably is the strongest property we can demand from a PRNG/streamcipher.

It's hard to predict which non ideal properties will lead to problems at some point in the future. For example the non ideal properties that lead to padding oracles, BEAST, CRIME or the RC4 biases were known for years before they were shown to be exploitable.

Many security proofs assume indistinguishability, so if the PRNG is distinguishable, this weakens the proof. If the PRNG is distinguishable under certain conditions, even if it's a seemingly harmless distinguisher, then a proof relying on indistinguishability becomes useless if those conditions are met.

Consider a message encrypted using a block-cipher in CTR mode. This has the property that no blocks in the key stream will be identical (just like Fortuna/Yarrow without re-keying). When the ciphertext contains identical blocks, the attacker knows that the corresponding plaintext blocks were different, because the corresponding key-stream blocks were different as well.
Admittedly that's not a huge leak in most contexts, but it is a leak. It might lead to problems in some contexts, for example if the message only uses a few different values for each block.


Difference in the Powers of Simulator and Environment in Universal Composability I know that in UC model, environment controls the real world adversaries but there is still a simulator wrapped around these real-world adversaries in the ideal world (which we sometimes collectively call ideal adversaries). I wanted to know if all the interaction that happens between the real world adversary wrapped inside the simulator and the environment in the ideal world has to go through the simulator?
If this is true, then the simulator can look at all the messages between the adversary and the environment.
Can someone clarify the powers that simulators have in UC versus the powers that environment have in UC?
Can environment also interact with the honest parties? As far as I know, the environment can only interact with adversarial parties and then try to distinguish the real execution of the protocol from the ideal one.

In the real world we do have adversary and environment. The environment interacts with the protocol (real function) and the adversary. The parties are part of the environment. The real function leaks information to the environment/adversary
However, in the ideal world there is no such leakage. Therefore, in order to prevent the environment from distinguishing between these two worlds we need a simulator to create these leakage by getting some information from the ideal world. Here, the simulator is acting like the adversary for the real world. The environment thus is able to interact only with the ideal functionality and the simulator where the simulator is the adversary for the ideal world


AES - MixColumn transformation using the identity matrix I'm analysing how different components of AES influence its security. However, I cannot find a good explanation to what happens if the MixColumn step would use the identity matrix. Intuition tells me, that then AES won't be secure, but why?

If you eliminate the MixColumn (or equivalently, replace it with an identity Matrix), then the resulting cipher will effectively be 4 independent 32 bit block ciphers.  This happens because what happens in one 32 bit row no longer has any propagation to any of the other 3 32 bit rows.

This results in a much weaker cipher; not only would that bring up possible chosen plaintext/ciphertext attacks (where you modify one of the 32 bit blocks, but leave the other 3 the same), you would also have ciphertext only attacks with a birthday bound of circa 256k...