Discrete log problem exponential runtime I am trying to understand the runtime complexity of the discrete log problem (in the most basic sense).

So, if we have $\langle g \rangle = G$ and are trying to find $g^x = a, a \in G, 0 < x < ord(G)$, why can we not just iterate through all elements of $G$ and find an answer in linear time? Even if we have to compute $g^x$ by repeated multiplication, wouldn't that just be quadratic time?

wouldn't that just be quadratic time?

No.

TLDR: modular arithmetic.

You may have an impression that it should be easy and takes a small number of steps. But the complexity comes from the fact that we use modular. In a normal arithmetic you know for instance that if $a < b$, then $g^a < g^b$ (for N). But in the modular arithmetic there are no such rule.

Example:

Let's take $g = 2099$, modulo $M = 2179$ and compare 1787, 39 and 1279,
What is greater, $g^{1787}$, $g^{39}$ or $g^{1279}$?

$g^{1787} = 999$

$g^{39} = 1000$

$g^{1279} = 1001$

We see that $g^{1787} < g^{39}$.

Other view on the same numbers. The equation $g^x = 1000$ has solution $x = 39$. Knowing this, can we guess what is solution of the equation $g^x = 999$? Is it close to $39$? No, it is not close. The solution of $g^x = 999$ is $x = 1787$.
There is no simple correlation.

That's why in the modular arithmetic to solve an equation like $g^x = 999$ we have to check every number. If $G = \{1, 2, ..., 10 000\}$, we have to check all these numbers. And if $G = \{1, 2, ..., 2^{512}\}$, we have to check all these $2^{512}$ numbers. In the reality some mathematical properties allow us to skip some groups of numbers and thus to reduce needed calculations. Nevertheless, even if the optimization would reduce that to $2^{256}$, still this would be pretty much work to do. The whole computer power on the Earth will not be sufficient to check all relevant numbers in trillions of years.


Gaussian elimination to equations with errors I am reading
this document and wondering the following part on page 13:
"Consider applying Gaussian elimination to the noisy samples
to find the first bit"

If we take, for example, $n = 3$, $s = (1,0,1)$, $x_1 = (1,1,0)$, $x_2=(1,1,1)$ and $ x_3=(0,1,0)$, what will $q$ and $S⊂[q]$ be?
Also, how to confirm the probability will be $1/2+2^{-Θ(3)}$?

I would be grateful for your help in advance.

$q$ is the number of samples and $S$ is the set of indices such that $\sum_{i\in S}x_i = (1,0,...,0)$. In your example, we have $q=3$ and $S=\{1,3\}$. The first bit of the secret $s$ is equals to $\sum_{i\in S}b_i \mod 2$, but with probability $1/2+2^{-\Theta(n)}$ not $1$, because the noises are also considered in this summation. So we need to repeat this procedure $2^{\Theta(n)}$ times to reduce the error probability.


Decimal point in keyspace notations? (eg 2^54.15)? I was reading up on CryptoCat's (pretty ridiculous) programming issues and how is dramatically reduced the key search space (link to bug synopsis)

One thing that caught my eye was

  So 2^54.15 turns into 2^27.08

Unless I'm missing something, the impact of the fractional exponent is negligible. So, any ideas why the author is reporting it as 2^54.15 and not just 2^54 ? I mean for O notations, we usually state only the degree of the highest order polynomial (that expresses algorithmic complexity), ignoring the factors and lower order powers.

So am I missing something here when it comes to expression of keyspaces?

I mean for O notations, we usually state only the degree of the highest order polynomial (that expresses algorithmic complexity), ignoring the factors and lower order powers.

Consider an imaginary runtime of $5x^{2.5} + 2x - 3$. As $x$ gets large this is almost entirely dominated by $x^{2.5}$. However, $x^2$ is significantly smaller than $x^{2.5}$, especially when $x$ gets large - so when notated in Big-O notation this would indeed be $O(x^{2.5})$ or $O(x^{2}\sqrt{x})$.

However, we're not talking about Big-O notation of an algorithm here. We're talking about key spaces, which are of a specific size, rather than a coefficient of something that might be big. So you'll have to decide on a case-by-case basis whether or not the fractional part is "significant" or not. In this case, $2^{27.08}$ is about 5% larger than $2^{27}$. Apparently the author found this difference significant.

Note that the original fraction came into place due to the author insisting on using $2$ as the base of the exponent. The exact keyspace is $2 \cdot 10^{16}$, which is approximately $2^{54.15}$.


What's the difference between perfect security and unconditional security? This paper refers to two distinct security models: perfect security and unconditional security. Until now, I knew of them as the same thing and equivalent to information-theoretic security.

From the paper, it's obvious that perfect security is the same as information-theoretic security. In this case, what exactly is unconditional security?

According to the references, both perfect security and unconditional security consider adversaries that have unlimited computational power, i.e., information-theoretic security. I think the only difference is that unconditional security allows for negligible failure while perfect security requires zero failure.


why DES encryption uses different modes like ECB,OFB? As without using modes we can also encrypt and decrypt data then what is the need of using modes in DES?

DES is a block cipher. It consists of a pair of algorithms, one for encryption and one for decryption. Each algorithm takes two inputs: the key, and the block to encrypt or decrypt; the output is the encrypted or decrypted block. For DES, the size of a block is 64 bits. So DES only tells you how to encrypt or decrypt data that consists of exactly 64 bits.

If you have more or less than 64 bits of data, you need to specify how the data is split into 64-bit blocks, what processing to apply to each block, and how to combine the output blocks together. By definition, this is called a mode of operation. Usually the splitting and combining is trivial, but the part about processing each block can be more or less complex.

Even when you happen to have exactly one block of data, modes can achieve things that DES alone doesn't. In particular, DES is deterministic: encrypting the same plaintext with the same key always leads to the same ciphertext. All good modes include a unique tag as part of the encrypted data (called an initialization vector in most modes), so that no two runs of the encryption algorithm ever produce the same ciphertext, which avoids leaking the fact that two messages are equal. Modes can also build algorithms that do things other than encryption, such as a message authentication code, or authenticated encryption which combines encryption and MAC together in a single algorithm.


Choice of authenticated encryption mode for whole messages There are several well-regarded block cipher modes for authenticated encryption which have made their way into standards and protocols: CCM, EAX, GCM, OCB, …

If I am designing a new messaging or storage protocol which requires both confidentiality and authenticity of the data, how do I choose between these modes? I am specifically interested in the case of whole-message encryption and integrity verification (as opposed to block storage).

I'm after answers like “pick whichever of X or Y is easily available in your programming environment”, or “padding for this mode is delicate to implement, but it is more robust to a broken RNG”.

(This is in the spirit of AES CBC mode or AES CTR mode recommended? for modes that provide confidentiality only.)

GCM

Personally, I would go for GCM (Galois Counter Mode) since it is efficient – meaning: it handles pretty much everything you’ld expect from it, while other modes sometimes tend to lack a specific feature here and there (see image below for a comparison that shows what I’m hinting at). Also, GCM has a pretty good performance (assuming non-flawed implementation). As you most probably already know, it provides Galois mode of authentication with the well-known CTR mode encryption. The CTR aspect practically means that it doesn’t need any padding (which avoids related attack potential) and it means that you keep a bit of flexibility when it comes to message/package lengths (something CCM for example doesn’t offer, since it uses a fixed block length). Also, the Galois field multiplication used for authentication can be computed in parallel, which enables higher speed/throughput than those authentication algorithms that use chaining modes (like CBC etc). Btw: in case you decide to check on GCM, you might find it handy to know that NIST Special Publication 800-38D includes recommendations for IV selection etc.

The rest…

An alternative at the top of my list would have been EAX mode, which also provides several desirable attributes. But: EAX is a “two-pass scheme”… making it slower than well designed one-pass schemes that are based on the same primitives. Since your designing a messaging/storage protocol, you probably will want to get your hands on all the speed you can get. Two-pass seems not to be an option in that case, pushing EAX down on the list.

Now, you also mentioned CCM. That mode is only defined for block ciphers with a block length of 128 bits, which might be a bit restrictive in size for messaging et al. Which is why I would like to remind you of GCM’s counter mode again…

Last on the list of things you’ve mentioned is OCB. I’m a bit uncomfortable when thinking about OCB, because Ferguson found collision attacks on OCB. The attack limits the data that can safely be encrypted with OCB to around and about 64GB per key.  That’s about the same 64 GB limit that GCM has (GCM limits plaintext size to $2^{39} − 256$ bits for any given key and IV combination), but we have to remember that GCM’s limit is “by design”… in the case of OCB, it’s “the result of a collision attack”. From a security perspective, I would therefore tend to avoid OCB. We all know attacks can only get better.

There are a few other things that might or might not make a bit of sense, depending on the individual setting… but in the end, I personally would advise to use GCM for a messaging and storage protocol.

Comparing some of the options…

To compare, you might also want to check out the nice comparison table on slide 7 of this PPT file by David Wagner. I’ll quote it as a graphic here for reading convenience (as you’ll notice GCM is a winner):

EDIT

Sometimes, my brain seems to be a bit slow when it comes to remembering papers I’ve once been reading.

Anyway, I’m pretty confident you’ll enjoy reading “Basic comparison of Modes for Authenticated-Encryption (IAPM, XCBC, OCB, CCM, EAX, CWC, GCM, PCFB, CS)” (PDF) which compares a truckload of modes in terms of attributes, speed, implementation, memory usage, tables showing things like the number of the underlying block cipher invocations for each mode, etc.

After reading that, you’ll have ample info at hand to decide for yourself what makes most sense.


How to decode a caesar that goes to transposed plaintext? When decoding vigeneres, I am left with Caesars. Often when the key is longer, these are shorter so normal frequency analysis won't work.

Is there another method I can implement without adding a load of loops?

The most frequent letter will probably still be e or t, this uniquely determines the ceasar shift, this leaves maybe a few options. You can also do a $\chi^2$ test to match the alphabet in the subcipher with the standard one, or use bigram frequencies to rate combine shifts in adjacent alphabets.

If all alphabets are mixed, not shifted standard alphabets, it's quite a different story, and will depend on the exact method of keying and square construction.


How many low-order bits of an RSA modulus can we safely fix to 1? It's easy to generate an RSA modulus $n=p\,q$ of $k$ bits with $n\equiv-1\pmod{2^\ell}$, for $\ell$ up to about $k/2$: we can choose $p$ as usual, fix the $\ell$ low-order bits of $q$ to $-p^{-1}\bmod2^\ell$, and choose $q$ with this constraint. This fixes the low-order $\ell$ bits of $n$ to 1, and thus appreciably simplifies Montgomery arithmetic when using the public key.
As an aside, that could be used to halve the storage requirement for $n$.
Up to what $\ell$ is that safe?
Some $n$ (in hex) for $k\in\{256,512,1024,2048\}$, $l=k/2$, generated using this TiO.
f0e32fe555bf8c5027734fcb32b6d51bffffffffffffffffffffffffffffffff
dec79757c4b1ca15fbe0854a75f38749df4768884c9e9c24af0f09d61a3d1811ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
af8c7235e1938b869a28c310c362444331f19c9b9cc578751a1a8f0859e1ae72916abd7351d82f0ffcb9b84eca441ee37f3646e5890c4ba94f9d6811d4b7f708ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
b22220297783289475800ddba5f2e9cfbdf64f2de3a23f10ac7d191d2f4fee2bba4d01dee6c851e8ed42fa1c4d5cafbec97e19e1735d1350f6b5ec1e26d9ef557c3c8938dc1b831a917337903977f15573f35be50607e6080dac8f967c6e3f1bea171870205d64f8b7263ed7ff20585c38d62505c77d0206dcc4dabeda45dd11ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Consider the similar RSA key generation process:
Select a random odd value $z$ between 1 and $2^\ell - 1$; choose $p$ as usual, fix the lower $\ell$ bits of $q$ to $z p^{-1} \bmod 2^\ell$ and chose $q$ with this constraint.
Now, this generates RSA keys with the same asymptotic [1] distribution as the standard RSA key generation process.
Now, the only difference between this procedure and yours is that you use a fixed $z = 2^\ell -1$, rather than a random one.  However, the attacker can determine the value $z$ used, and so us telling him which $z$ we picked doesn't give him any additional information.
So, the only question is "does a specific value of $z$ yield a weakness?".  I do not know of any factoring method that is applicable to a specific $z$ value.

[1]: I say asymptotic, as the demonstration assumes that the lower $\ell$ bits of primes are evenly distributed over odd values; this has been proven to be true asymptopicly (for fixed $\ell$), it is a reasonable (but unproven) assumption for smaller primes.


RSA Question- max number of ascii characters encrypted at one time I'm a student new to cryptography and have a fairly straight forward RSA question that I'm struggling to wrap my head around.

"Alice's RSA public key [N:e] is stored in binary as a 16bit integer &: 8bit integer.

What is the maximum number of ASCII letters that can be encrypted at once and sent to Alice if assuming no padding?"

My initial thought was 1 ASCII character at a time because M < N. Therefore it couldn't be 2 characters (2 x 8 bits) because M would = N.

From my understanding of modular arithmetic:
51 mod 5 = 0   But    41 mod 5 = 4

So I kind of understand that if M is equal or greater than N, I will only decrypt an equivalent message but not identical.

Could somebody explain this to me in more detail?

Don't do it!  It's a trap!  Applying the arcane mathemagical spell that is RSA trapdoor permutation to ASCII does not an encryption scheme make!  The RSA trapdoor permutation conceals uniform random elements of $\mathbb Z/n\mathbb Z$; to use it for anything else is a mistake, and a fool's errand clothed in naive textbook idealism.

It's like telling your class that modern aviation is built out of paper airplanes, except unlike the obscure mathematics of RSA, paper airplanes self-evidently cannot function like an Airbus A380 or even a Cessna C-34.  If this is how you are taught aeronautical engineering, I exhort you to find another instructor!

Real encryption schemes based on RSA use the fancy mathematics to conceal a 256-bit secret key for symmetric-key authenticated encryption such as AES-GCM, and use that to encrypt the message.

That preface said, taking your question at face value:

The space of ‘messages’ $M$ is set of the integers between $0$ and $N$.  Any other integer is equivalent, as far as RSA is concerned, to one between $0$ and $N$, because all arithmetic is modulo $N$; for example, $N + 1$ is equivalent to $1$, because they differ by a multiple of $N$.

So, for a modulus $N$ between $2^{15}$ and $2^{16}$, there are at least $2^{15}$ distinct messages.  How many ASCII characters are there?  How many pairs of ASCII characters are there?


Why not generate the authentication key from the key and nonce in GCM? In Galois/counter mode, the authentication key $H$ is leaked if two distinct messages are encrypted using the same nonce. If someone did end up doing that, then they would need to rekey to get a new $H$ as $H$ is derived only from $K$. So, why not derive $H$ from $K$ and $N$ (the nonce).

So, why not derive $H$ from $K$ and $N$ (the nonce).

Well, if you are asking why the original GCM designers made that specific design decision (CodesInChaos point is valid, but software implementations weren't actually considered in the original design):

A critical goal in the GCM design was that it be hardware pipeline friendly; that is, you could process the message in a 10-14 stage pipeline (where each AES round was a separate pipeline stage), and that there are minimal wasted steps.  Doing some additional computation before you could process the initial AAD data would cause a break in the pipeline, and so violate this goal.
It wouldn't help.  If the $H$ value was derived from an $N$ and $K$ pair, then if you repeat an $N$ value, you still repeat the $H$ value (and hence leak that $H$ value).  What your idea would mean is that the attacker would have to repeat the $N$ value to forge (as the attacker wouldn't know the $H$ value for any other $N$); however that is not a practical issue for attackers, who can freely pick the $N$ value for their forgeries.


How can a hash function be suitable for hashing passwords, but not for deriving enctyption keys, and vice versa? Not being a specialist in this field, I am nevertheless constantly trying to keep up with which methods are being considered secure for storing passwords and for encrypting data.

During my research and desperate tries to extract the key points which are important for practice :-), I am reading often that certain hashing functions are suitable for password hashing, but not for deriving encryption keys, and vice versa. Since I absolutely can't get this, but have read it too often, I have to seek help.

For the following, let's forget about all complicated things (rainbow tables, salting, side channel attacks and so on). Furthermore, I am over-simplifying things in the following sections. But the question is so basic that I think that the over-simplification does not hurt in this case.

My understanding problem is this:

An OS should not save a password in clear text for obvious reasons. So a hashing function (MD4 (yes, Windows still uses it), SHA-2, scrypt, ...) is  applied to the password, and the hash is stored on disk instead of the password.

If an attacker wants to crack the password, he has to get the hash, and then has to take every possible input string, apply the hashing function to it, and see if the hash of the input string is the same as the hash of the password the OS had stored.

This means that the hashing function should be slow (in terms of cycles), should be hard to parallelize, and should be memory intensive to make brute force cracking (even with specialized hardware) as expensive and time consuming as possible.

On the other hand, as far as I have understood, when deriving an encryption key from a password, nearly the same method is applied. The difference is that the hash of the password is not stored on disk, but is used directly as encryption key for some symmetric encryption method (like AES) (over-simplified, but shows the general idea, right?).

Now, if an attacker would like to break the encryption, he also would have to test every possible password, apply the hashing function to it, and then decrypt the encrypted data with the hash and test if the result contains something meaningful. Thus, as with password hashing, the hashing function should be very hard to parallelize, memory and cycle intensive so that the attacker could test only a few encryption keys (= hashes) per second.

So the requirements to a hashing function for hashing passwords seem to be the same as the requirements to a hashing function whose output is used as encryption key. For the life of me, I don't get why some hashing functions are considered suitable for the one, but not the other, and vice versa.

Could somebody please explain this in simple words, taking into account that I have a mathematical background in general (if urgently needed :-)), but no background in cryptography's mathematics?

So the requirements to a hashing function for hashing passwords seem to be the same as the requirements to a hashing function whose output is used as encryption key

This is correct only when the encryption key is derived from a password.

The similarity you observe is due to the fact that a password is the input, and passwords tend to be relatively easy to guess.

Other circumstances where encryption keys are derived do not require key stretching, because the input is already an unguessable (psuedo)random value.

As an example, when using a key agreement scheme the resultant shared secret is typically hashed with a fast cryptographic hash function such as SHA256 to protect the private keys in the case that the shared secret key is compromised. Since the value is already random and large enough to be unguessable, there is no need to apply a slow hash to prevent the adversaries ability to guess it.

tl;dr

If the input is a password, then the hash needs to be slow to prevent an adversaries ability to perform exhaustive search on the entire password space.

If the input to the hash is already a large random value, then slow hashing is not required.


About public / private key encryption Am I right with this assumption about the general idea of public key and private key?

The sender encrypts the data with a symmetric key. After that, he encrypts (using RSA algorithm) this symmetric key with the public asymmetric key of the receiver.
The receiver decrypts with his private asymmetric key, and gets the symmetric key used by the sender. With this key, he decrypts the data.

How does the sender know the public asymmetric key of the receiver?
2 options:

Diffie Hellman.
Digital certificate PKI, by querying a CA.

Is this right?

The sender encrypts the data with a symmetric key. After that, he encrypts (using RSA algorithm) this symmetric key with the public asymmetric key of the receiver.

That's one possible implementation of a hybrid cryptosystem for encryption/decryption. It is also quite common to derive the symmetric key using the asymmetric key pair. This is performed for instance by IES for Diffie-Hellman based cryptography but also by RSA-KEM.

How does the sender know the public asymmetric key of the receiver?

Diffie Hellman.

No, Diffie-Hellman is used to derive symmetric keys. It cannot be used to distribute public keys.

How does the sender know the public asymmetric key of the receiver?

Digital certificate PKI, by querying a CA.

An implementation of a PKI could certainly work.
But PKI doesn't necessarily mean that there are CA's (e.g. see how PGP operates).
And if they do exist - for instance in PKI-X used in e.g. browsers - then they generally are only needed to sign certificate requests and verify that certificates are not revoked. During operation the CA certificates can simply be send using a certificate chain. Quering a CA is not required at the time of verification.


What could "look for the constants that you might find in RC6" mean? In this presentation at the 30c3 (long but extremely interesting and well-documented), Jacob Appelbaum gave this verbal advice (circa 43'30"):

  look for the constants that you might find in RC6

I'm trying to make sense out of that; my problem is, there are very few constants that I could find in the description of RC6. Any idea?

The Key schedule appendix of the RC6 paper (Rivest et al.) defines two arbitrary constants in hexadecimal notation. They also appear in RC5.

$P_{32} = \tt{B7E15163}$
$Q_{32} = \tt{9E3779B9}$

Be aware that the binary coding of these constants will vary based on the endian-ness of the computer architecture.

There seems to be nothing 'special' about these constants in relation to the construction of the RC6 algorithm. They can be replaced with any random value, producing an incompatible variant of RC6 with presumably identical security properties, and the authors make note of this. (The 'official' constants were chosen based on open criteria, described in the paper, in order to dispel any notion that they induce a back door.) Thus a serious search for RC6 would include RC6-alikes and look for algorithm structure rather than constants.

There are no other arbitrary numeric constants defined in RC6, unless you would go so far as to consider the number of rounds etc. as such.

By the way, Appelbaum's talk wasn't "well documented" enough to provide any justification for this RC6 hunt. Typically of Appelbaum, he takes the position, "Trust me, I've seen the secret documents." Sounds like some senators I know.


Reduction of Integer factorization to Discrete logarithm problem I was reading Eric Bach paper entitles Discrete logarithms and factoring, in which he states the following reductions:
solving the integer factorization problem suffices to solve the discrete logarithm problem and vice versa.
I could not completely understand the explanation. Could anyone explain it to me or refer me to another source.

Here is a quick summary:

First direction, from discrete logs modulo $N$ to factoring. Assume that there is a fixed basis $g$ for the method that computes logs. Choose a random $x$ modulo $2N$ and compute $y=g^x\pmod{N}$, then ask for the logarithm of $y$. Let $x'$ denotes the answer to the discrete log problem. If $x=x'$ restart, else $x'-x$ is a multiple of the order of $g$ modulo $N$. Once this is known, apply the randomized method described as answer to Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group? and factor $N$.
Second direction. If the factorization of $N$ is known, then $y=g^x\pmod{N}$ implies $y=g^x\pmod{p}$ for each prime factor $p$ of $N$. As a consequence, computing discrete logarithms modulo $p$ gives $x$ modulo the order of $g$ modulo $p$ (this is $p-1$ is $g$ is a multiplicative generator modulo $p$). Assuming for simplicity that $N$ is squarefree, it now suffices to paste together all the partial solution using the chinese remainder theorem and you get the logarithm modulo $N$. Note if the chinese remainder theorem does not give a solution because the logarithms modulo the various orders are incompatible, it means that the original problem does not have a solution.

On squarefreeness. Without the squarefree assumption on $N$, you need to compute logarithms modulo powers of $p$. This is not harder than computing logarithms modulo $p$ but requires some technicalities.


Are all encryption tools made equal? I'd like to encrypt work-related data backups stored on an external drive. The backups contain proprietary company information and trade secrets.
My current backup program, Comodo Backup, allows me to encrypt backup files with AES, Serpent, XOR, and other schemes. However, I've read about vulnerabilities in encryption tools (such as TrueCrypt failing an audit by Google's Project Zero team).
It would be more convenient for me to let CB create encrypted containers, but if necessary, I can have it make uncompressed/unencrypted backups, then encrypt them manually after the fact. Thanks for your help - obviously, my knowledge of security and cryptography is very limited.
Here is the only information I can find regarding their encryption method:

Encryption Algorithms:
3DES - 168-bit/ strong
AES - 128bit / strongest
Blowfish - 64-bit block / strong
DES
Serpent - 128,192 or 256 bit / very strong
Twofish - 128-bit block/ strong
Xor - Variable block size / weak
CBU generates a 32 byte key by applying a SHA256 hash algorithm to the password entered by you. If the encryption algorithm chosen by you requires a key of smaller bit length, the 32 byte key is truncated to the required length. CBU encrypts the backup file with the chosen algorithm using this key. During the restoration the backup file, CBU receives the password entered by you, generates a key by applying the same hash algorithm and uses this key to decrypt the backup file. If a wrong password is entered by someone maliciously, the key required to decrypt the backup could not be generated and the backup could not be restored, ensuring additional level of safety to the backup of your confidential information.

Rather than rely on Comodo Backup to handle the archive encryption, should I use a more specialized tool such as VeraCrypt?

No, not all encryption tools are made equal.

Even when using the same cryptosystem, say AES-256, a tool's choice of cipher mode, how to generate AAD if present, how to generate IV, how to generate key, and the quality of the random source all affect quality.  The quality of cryptography engineering is the major deciding factor at that point and it is tricky to get right.

To determine if you should use VeraCrypt or let Comodo Backup do the encryption you need to assess the effectiveness of their cryptography engineering.

The simplicity of using the built-in encryption supplied by Comodo Backup is a significant convenience advantage.  If their crypto eng is up to scratch I'd make that your choice.


Possibility of the encrypted text being the same as the supplied plain text! I was learning DES when it occurred to me that there could be a possible case where a (key, plainText) pair could result in an encryptedText such that, plainText == encryptedText.

Quickly I found out that there exists weak keys (especially for DES!) that make it quite vulnerable. So, the worst that can happen with these weak keys is that double encryption would return the original plainText.

I want to look at one example where the output of the DES would be same as input.

What I've already tried:

A brute force: wrote a generator for random [key, pText] pairs and DES over them to see if the eText is same as pText. Got a C Language implementation from here. Specs: len(pText) = 64b, len(key) = 56b, Generated random cases: 10M. I do understand that the number of cases barely scratches the surface, but I was hoping (naively I guess) I'd find at lease one such case.
Gave a little thought and realised that, if the crypto function in the Feistel Structure returns 0 in every round, at the end of 16 rounds, we'd have the same output. This depends upon the inputs to that function (which are in-turn derived from the talked about pair)
Yet another thought is that: if the input is small enough (yes assuming we have padding enabled) the output would also be of the same size, which means that there's a very high probability that the pText is same as eText. Just to make my thoughts more clear, if input is of size 1 bit, say 1, the output could be 0 or 1, implying, the chances of my case occurring is 50%!

May be I should see the mathematical model of the DES and infer if it's possible, but I feel like I've already spent too much time on this!

Please suggest me how do I go about cracking this case!

Thanks! :)

For a fixed key, a block cipher is presumed to behave like a pseudo-random permutation (PRP) over messages.  What we are interested in is if the permutation contains a fixed point, i.e. if it is a derangement or not.  What we find is that there is about a 63% chance that there is at least one fixed point, and the expected number follows a Poisson distribution (i.e. there shouldn't be many).

Your argument about short messages doesn't apply to block ciphers used in practice, since they don't operate on messages smaller than a block.


Converting a stream cipher into a block cipher The well-known Counter-Mode (CTR) mode of operation for a block cipher essentially converts any block cipher into a stream cipher.  Is there a way to do the reverse?  In other words, given a "good" stream cipher $G$, can we construct a block cipher that builds its strength based on $G$?

In an answer to another question, Zooko mentioned the BEAR and LION constructions,  linking to this paper: Two Practical and Provable Secure Block Ciphers: BEAR and LION.

These build a block cipher (with large blocks) from a stream cipher and a hash function (a keyed one (i.e. a MAC) for BEAR, a unkeyed one for LION).

The authors basically build block ciphers (with variable block sizes $m$) from a keyed hash function (a function family $H_K : \{0,1\}^* \to \{0,1\}^k$) or a normal hash (a function $H' \{0,1\}^* \to \{0,1\}^k$) and a stream cipher (a function $S : \{0,1\}^k \to \{0,1\}^n$, for arbitrary $n$ from context; here $n = m-k$).

These work by fist splitting the input block of size $m$ in two parts, one (L) of size $k$ and one (R) of size $m-k$, doing the encryption/decryption, and putting the two parts again together. We also have two keys $K_1$ and $K_2$, each of length $k$.

For BEAR, the encryption is done by

$$  L := L ⊕ H_{K_1}(R) $$
  $$  R := R ⊕ S(L)  $$
  $$  L := L ⊕ H_{K_2}(R) $$

and decryption the other way around:

$$  L := L ⊕ H_{K_2}(R) $$
  $$  R := R ⊕ S(L) $$
  $$  L := L ⊕ H_{K_1}(R) $$

For LION, we use a un-keyed hash function $H'$, and we have two calls of the stream cipher instead of the hash function instead of two keyed hash calls. Encryption:

$$  R := R ⊕ S(L ⊕ K_1) $$
  $$  L := L ⊕ H'(R) $$
  $$  R := R ⊕ S(L ⊕ K_2) $$

Decryption:

$$  R := R ⊕ S(L ⊕ K_2) $$
  $$  L := L ⊕ H'(R) $$
  $$  R := R ⊕ S(L ⊕ K_1) $$

E.g. decryption is in both cases just encryption with swapped key halves.

These are effectively Feistel networks with three asymmetric rounds.

The paper proves that these are secure (against certain attacks) as long as even one of the component functions is secure (e.g. breaking the composed primitive allows breaking both of the components).

There is a third construction mentioned in this paper, LIONESS, which uses four rounds (two keyed hashes, two stream cipher calls), which also provides resistance against an adaptive combined chosen plaintext and ciphertext attack.


Why does openssl derive IVs from a password? From https://wiki.openssl.org/index.php/Manual:Enc(1):

  When a password is being specified using one of the other options, the IV is generated from this password.

Why does OpenSSL do this? My expectation would be that an unique IV is generated and encoded in the output message every time you invoke OpenSSL. When decrypting, OpenSSL extracts the IV and uses it.

Is there any reason to derive an IV from a password instead? Is that even safe to do? Aren't you using the same IV each time you use the password? What even is the point of using an IV if it's going to be paired to the encryption key?

If you read the manpage you referenced a bit more carfeully, you will find the following lines:

  -nosalt

do not use a salt

  -salt

use salt (randomly generated or provide with -S option) when encrypting (this is the default).

and

  The -salt option should ALWAYS be used if the key is being derived from a password unless you want compatibility with previous versions of OpenSSL and SSLeay.

  Without the -salt option it is possible to perform efficient
  dictionary attacks on the password and to attack stream cipher
  encrypted data. The reason for this is that without the salt the same
  password always generates the same encryption key. When the salt is
  being used the first eight bytes of the encrypted data are reserved
  for the salt: it is generated at random when encrypting a file and
  read from the encrypted file when it is decrypted.

Putting this together we learn:

You should use a random salt, which gets used in the key derivation process (calculating the encryption key and the IV from the password)
If you use a salt, the key and the IV and thus the ciphertext won't be deterministic
Using a random salt is the default behaviour of openssl enc

You can easily check this by running

echo foo |openssl enc -aes-128-cbc -out encrypted -nosalt

and

echo foo |openssl enc -aes-128-cbc -out encrypted

In the first case, the output will be 16 bytes long (one block of AES), in the second case it will be longer, because the salt has to be stored.


Why use IV like this in TLS 1.2 record layer AES-SHA block cipher? struct {
    opaque IV[SecurityParameters.record_iv_length];
    block-ciphered struct {
        opaque content[TLSCompressed.length];
        opaque MAC[SecurityParameters.mac_length];
        uint8 padding[GenericBlockCipher.padding_length];
        uint8 padding_length;
    };
} GenericBlockCipher;

I quoted above from RFC5246.
I am curious why do we use IV like that.
Why not derive IV in the key expansion and use it again again?

If we use it like above, the IV will be public to anybody.
Is it right that the recipient should use the IV to decode block-ciphered struct? So IV is not encoded and only block ciphered struct is encoded.

I am curious why do we use IV like that. Why not derive IV in the key expansion and use it again again?

Repeating IVs is bad, both for CBC and GCM.  And, no, keeping the repeated IV secret from the adversary doesn't help.

  If we use it like above, the IV will be public to anybody.

Well, yes.  IVs do not need to be secret; we don't mind if an adversary hears them.

  Is it right that the recipient should use the IV to decode block-ciphered struct?

Yes.  In CBC mode, the IV is directly used as the CBC-mode IV input (effectively, as the "previous ciphertext block" to decrypt the first ciphertext block).  In GCM mode, it is combined with 4 bytes from the key expansion to generate a 12 byte nonce, which is used as the GCM-mode nonce input.


Can you update a (k,n) scheme to a (k+t, n+t) scheme (assuming old keys can be deleted)? I know that $(k,n)$ can increased to $(k+t,n-s)$ one, by generating a random polynomial $p(x)$ of degree $k+t$ with constant term $0$, and then ordering each agent $a$ to add $p(a_x)$ (where $a_x$ is an agent's public x-coordinate) to their share (if $k$ old shares are compromised, the secret is compromised, but we are assuming enough old shares are destroyed to prevent this) (we get $n-s$ by either ordering $s$ agents them to destroy their share, or, if it is already compromised, not sending an update to that agent.)

Also, I know a $(n,n)$ XORing secret sharing scheme can be increased to $(n+t,n+t)$, by generating $n+t$ bit strings that XOR to $0$, and sending the first $n$ to each agent to XOR with their current share (and send the rest to $t$ new agents). This in particular means there exists a secret sharing scheme $(k,n)$ can be updated to $(k+t, n+t)$ via this.

Can a $(k,n)$ shamir secret sharing scheme can be updated to a $(k+t, n+t)$, without any agents having to reveal their share?

Note: Remember, we are assuming that enough old keys can be destroyed to prevent the secret from being reconstructed from old keys alone (which is why this doesn't apply.)

You can use a variant of the standard "degree reduction" trick from secret-sharing-based MPC protocols, but use it to increase the degree instead.

You start out with a $(k,n)$-sharing of a value $s$. Denote the collective object by $[s]_k$, meaning that party $i$ has private value $p(i)$ where $\deg(p) < k$ and $p(0) = s$. Just so we're on the same page:

$s$ can be expressed as a linear combination of these shares via $s = p(0) = \sum_{i=1}^n c_i p(i)$. The coefficients $c_i$ in this case are public.
if everyone locally multiplies their share of a value $[v]_k$ by a public $\alpha$, the result is $[\alpha v]_k$ -- i.e., shares of $\alpha v$.
if everyone locally adds shares of $[v_1]_k$ and $[v_2]_k$ the result is $[v_1 + v_2]_k$.

Back to our $(k,n)$ sharing of $s$, we want to make it a $(k+t,n+t)$ sharing. To do this, let all of the original $n$ parties make shares of shares. Party $i$ acts as dealer, distributing $(k+t,n+t)$-shares of the value $p(i)$ to create the object $[p(i)]_{k+t}$. Using local computation, everyone computes the desired object $[s]_{k+t} = \sum_{i=1}^n c_i [p(i)]_{k+t}$. They can throw away the old shares of $[s]_k$ now.

Note: all of this assumes honest behavior by the parties. If some are corrupt, then verifiable secret sharing tricks would be needed.


human readable unpredictable & no collision uid based on time I need to create an unpredictable uid based on time.
I plan to allow it to work during a time frame of 100,000,000 seconds.
So the seconds will go from 00000000 to 99999999.

I need an algorithm that will "convert" the seconds to another 8 digit number. 8 digits in, 8 digits out.
Example :

algorithm(00000001) returns 87981278
algorithm(00000002) returns 57941047

The returned number must be unpredictable and there musn't be collisions

If we run the algorithm with the 100,000,000 possible number, we will get 100,000,000 different results (sort of randomization of the 100,000,000 possibilities)

The security does not need to be bulletproof. I just want to avoid id's being in sequence ...

It has to be human readable ... people will need to manually type this id, so big hashes aren't an option.

Any direction you can point me to ?

Thx !

The problem can be reduced to generating a random permutation of the numbers 0 to 99,999,999. One way to do it is to use something like the Fisher-Yates shuffle but this will require you to store 12,500,000 bytes (one bit for every possible number in your sequence). Adapted for your use, what you would do is every time you want a number for your sequence, the Fisher-Yates shuffle would have you:

Pick a random number k from 1 to the number of unstruck numbers remaining.
In your your 100 million bit array, set to 1 the kth remaining 0 bit. Use the position of that bit as the hashed number.

I can't think of a way to assure no collisions without using that much storage.

A cheap solution if you don't mind getting only a small subset of the 100 million factorial possible sequences would be to choose some number relatively prime to 100 million and repeatedly modulo add it to generate your sequence. If you choose a big enough number it will look unpredictable to a human. In abstract algebra terms, we choose a generator of the cyclic group of order 100 million and use it to generate all the elements of the group.


Security of randomized data dependant key schedules? An example to demonstrate the point with two Feistel networks:

Cipher A:
\begin{align}
roundkey = hash(key || counter)\\
roundkey = hash(key || roundkey)\\
left = left\oplus hash(roundkey || right)\\
... swap\ and\ continue
\end{align}

Cipher B:
\begin{align}
roundkey = hash(key || counter || right)\\
roundkey = hash(key || roundkey)\\
left = left\oplus hash(roundkey || right)\\
...swap\ and\ continue
\end{align}

In the above, Cipher A would produce identical round keys during every encryption/decryption, while the round keys in Cipher B would be different for each set of plaintext/ciphertext pairs.

Do key schedules which incorporate plaintext data to generate randomized round keys offer any particular benefits or complaints compared to key schedules which produce the same round key regardless of the data being operated upon?

I understand that incorporating plaintext data might potentially allow an adversary to influence the key schedule, but the extent of which that is a problem probably depends on the specifics of the algorithm in question. I'm more interested about the general case, if there's anything that can be said about it. I'm also interested in whether or not it could complicate statistical side channel attacks like differential power analysis.

Are there many examples of randomized data dependent key schedules? Or better, papers outlining attacks against them? My search mostly turned up "data dependent rotations".

Data-independent key schedules allow the round subkeys to be computed once in advance.  They can be reused for each subsequent block you encrypt.  This potentially allows significant performance speedups.

Data-dependent key schedules don't have that property.

Otherwise, there is no fundamental difference.

Normally, the key schedule is defined or understood to be the part of the cipher that depends only on the key and can be computed in advance (doesn't depend on the data).  So, "data-dependent key schedule" is somehow a contradiction in terms.


If IV is sent/shared with the cipher text then where is the need to randomise the IV? I have been reading to understand the need to randomise the IV but have failed to understand this yet.

Could someone please explain why do we need to randomise the IV if we somehow need to send the IV with the cipher text because the receiver, even though has the key would not know the random IV.

Therefore, wouldn't an adversary who has access to the cipher text can see the random IV for each message?

Why isn't it better to agree on a fixed IV like the key and not send it over with the cipher text?

Randomizing the IV makes it so that you can send the same plaintext twice, and still get different ciphertext. If you don't do that, an adversary will be able to tell whether or not two messages are identical. This can provide a way for an adversary to infer the contents of messages without actually directly attacking the cipher.

A randomized IV prevents this, even though the IV itself is typically made public, since there's no way an attacker can use the transmitted IV to decipher the message without also knowing the key.

It's a lot like salting passwords, really.


Number of keys for a monoalphabetic cipher My teacher stated that…

  The number of possible keys (E) in a monoalphabetic cipher is $26$!

My thinking:

  Every letter in the alphabet can be $25$ different letters hence it the  number of possible keys should be $26^{25}$.

What is wrong with my way of thinking, and how did she come to a conclusion of “$26!$”?

Your teacher is right, and here's why:

What happens if you encrypt A with G and B with G? You can't decipher it, because you have no idea if the G in the ciphertext was an A or a B.

So…

For the plaintext letter A you can use the ciphertext letter A, B, C, … , X, Y, or Z. ($26$ possible letters.)
For B you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A. ($25$ possible letters.)
For C you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A or B. ($24$ possible letters.)
...
For Z you can only use the remaining letter. ($1$ possible letter.)

The whole number of possible keys is $26\times25\times24\times [...] \times2\times1 = 26!$ (The exclamation mark denotes the factorial of a number.)


Mathematically/Theoretically calculating time to brute-force RSA encryption keys for a quantum computer vs a Classical computer? Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys?

I know there is a way to do so with a classical computer and time taken to brute-force RSA keys, but I'd like to specifically know how one calculates the time.

Furthermore, since the technology for brute-forcing RSA keys with a quantum computer differs from the one of a classical computer; How would one calculate the time to brute-force RSA keys using a quantum computer?

To do the calculation I'm guessing you have to take into consideration the amount of computing power. If possible use (or give me an example of) what equal (ish) computing powers in-between Classical and quantum computers would be. For example what scale classical computer is needed to compare (and be on the same level) as a 5-qubit quantum computer (only) in terms of brute-forcing RSA keys?

Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys?

Even classically, this is not so easy as you seem to imply.

RSA is based on the hardness of the integer factorization problem. The fastest classical algorithm known that solves this problem is the General Number Field Sieve (GNFS), and it solves integer factorization in subexponential time, or $\exp((\sqrt[3]{64/9}+o(1)) (\log N)^{1/3} (\log \log N)^{2/3})$ where $N$ is the modulus, and $\log$ refers to the natural logarithm.

However, we can't easily calculate an exact running time using this formula. Asymptotic running times hide constant values, which can vary wildly depending on the algorithm. Additionally, they don't tell us anything about what kind of parallelization may be possible.

GNFS happens to be a very complex algorithm. It involves a significant number of parameters. There are four different "stages" to the algorithm. Some stages can be made to take more time, in order to make the other stages faster. Additionally, some stages are easily parallelizable, while others are not, or only to a limited degree. In other words, coming up with the right set of parameters in order to minimize the total time to break an RSA modulus is very far from trivial. Let alone somewhat accurately estimate how much time it will take.

So unfortunately there's no easy answer to this question. However, you can get an idea by looking at some numbers that have been successfully factored.

  How would one calculate the time to brute-force RSA keys using a quantum computer?

This is easier to calculate but at the same time impossible. Integer factorization can be done using Shor's algorithm on a quantum computer. This algorithm runs in polynomial time, $O((\log N)^2 (\log \log N) (\log \log \log N))$. From this paper you can see that the number of logical qubits required are approximately $2 \log N$, and the number of logical quantum gates $4(\log N)^3$.

As mentioned in the paper, these logical qubits and quantum gates would require many physical qubits and quantum gates to actually implement. It's still not certain whether quantum computation is even possible on a large scale, due to issues with quantum decoherence. So again, I'm afraid there's no answer to this question. How could you possibly estimate the running time of an algorithm on a computer that doesn't yet exist?


Authenticating small packets I intend to authenticate small packets of data, between 16 and 256 bytes each. For some of them encryption will also be required. This will be used on small micro controllers, with RAM sizes ranging in 1 KB to a 64 KB.

My initial approach was to use AES-128 as the base cipher for a block cipher mode with MAC (GCM for instance). However, given the small packet sizes I was wondering if this is secure. So I was considering prefixing to the plaintext, a 32 bit number that is the concatenation of the plaintext CRC16 code and a 16 bit nounce. Then encrypting the result (CRC16 || 16 bit nounce || plaintext) with AEs in block counter mode.

Authentication would be done by decyphering the cyphered packet and validating the CRC16. This approach seems so obvious, but I can't find any implementations of it and I fear that I am overlooking something important.

My question: is encrypting a the CRC together with the packets as secure (meaning as hard to break) as appending a MAC to the packet ?

No, in general using a CRC in this way is not secure. A CRC is not designed to be used against adversaries, it is used to detect random bit changes to the data it is protecting (as well as the CRC itself). A CRC of 16 bit will certainly not be as secure as an 8 byte MAC value, that was designed to protect against such attacks. Without additional measures a 16 bit CRC would be pretty easy to brute force.

Note that there are many arguments against authenticate-then-encrypt. One of the reasons that it may be less secure is that it allows attacks on the block cipher mode of operation. In this case the ciphertext may be vulnerable to padding oracle attacks.


Hamming Distance vs. Index of Coincidence When analyzing a repeating-key xor cipher to find the key length, I've read about two key methods (assuming there aren't just repeating chunks of ciphertext for Kasiski's method), for some assumed key length $l$, checking the Hamming distance of nearby chunks of ciphertext of length $l$, and checking the IoC for columns of text when the text is split into $l$ columns.

When are Hamming distances more effective, and when is the IoC more effective? Is there any way to know based on the ciphertext which technique will be more helpful, or is this a "try them both and now it's more an art than a science" sort of thing?

See also: previous discussion of these methods.

The Hamming distance is more effective when you suspect that the plaintext has been XORed with some repeating keystream.  That's because XOR works at a bit level, as does the Hamming distance.

The Index of Coincidence is more effective when you suspect that the plaintext has been combined with some repeating keystream, where the combiner works character-by-character instead of bit-by-bit.  For instance, the IoC will be more effective for a Vigenere cipher, or for a repeating-key polyalphabetic cipher.  This is because those ciphers transform individual characters of the plaintext as a unit (not individual bits), and the IoC works at the character level.

If you like, you can think of the Hamming distance technique as effectively applying the Index of Coincidence at the bit level: the Hamming distance is effectively a variant of the IoC that works at the bit level, and that is especially effective when the combiner is the bitwise XOR operation.  Therefore, if you know that the plaintext is combined with some repeating keystream using some bitwise operation (such as XOR), then you might use the Hamming distance (effective, applying the IoC at the bit level instead of the character level).

Of course, you can always apply both and see which works better on your particular cipher -- but the above discussion tells you which method you should expect will work better in any given circumstance, and why.


Choice between AES-128 and AES-256 for password protection in MS Office Why are we still using the default of AES-128 when password protecting a Microsoft Word document. My answer is and always has been - because its good enough and MS don't recommend changing to AES-256. However, that has got me thinking: if a user password protects their word document (.doc, .docx) with a 10 character password of P@ssw0rd10 using the default AES-128 encryption, is that a harder password to crack than an 8 character password of P@ssw0rd using AES-256?

What is it a brute force attack is trying to achieve. Crack the AES-128/-256 algorithm which then in turn reveals the password? Does password length and character selection actually matter (you can input a password of up to 255 characters on a word doc) or is it the AES type in use that matters?

A cryptosystem is as strong as its weakest link.  AES-128 is almost certainly not the weakest link in your system.  Therefore, strengthening it by increasing the key length will not make the overall system more secure in practice.

To expand on that, let's consider (some of) the possible attacks on your system:

The attacker finds the user's password written on a post-it note.
The attacker sneaks a keylogger onto the user's computer and captures the password as the user types it in.
The attacker tests common passwords and their variations (e.g. "password" → "P@ssw0rd") until they find the correct one.
The attacker tests all the possible 128-bit AES keys derived from the password until they find the correct one.
The attacker finds a bug in the MS Office implementation of AES encryption that allows them to bypass it without knowing the correct password or key.
A cryptanalytic break of the AES algorithm renders it significantly easier to decrypt than by brute force testing all the keys.

Switching from AES-128 to AES-256 directly affects only one of these attacks: the brute force AES key enumeration attack (#4 above).  Even for AES-128, this particular attack is already considered practically impossible even for large nation states.  Switching to a 256 bit keyspace just moves it from "practically impossible using current or near future technology" to "completely unimaginable using any technology we can currently foresee".¹

That still leaves potential attacks 1, 2, 3, 5 and 6.  Attack #6 (a cryptanalytic break of AES) is not really something an end user should be worried about.  While such a break theoretically could compromise AES-128 while still leaving AES-256 with enough security margin to resist practical attacks, the opposite is theoretically possible as well.²  In any case, a cryptanalytic break on AES itself is a far less likely scenario than a vulnerability in the way a particular commercial software product uses it (attack #5 above).

In any case, the most likely practical threats to your system are attacks 1–3 above, or other similar attacks aimed at compromising the user's password rather than the encryption key derived from it.

While attack #3 can somewhat be mitigated by key stretching (if MS Office uses it, which I don't know), even the best (and slowest) key stretching algorithms can only slow down brute force password cracking by a factor of 230 to 240 or so; i.e. they add at most 30 to 40 bits of effective strength to the password.  Thus, unless your users use passwords with about 90 or more bits of entropy (as provided e.g. by a 7 word diceware passphrase) and unless the software you're using uses proper key stretching with the highest feasible memory usage and iteration counts, brute forcing the password (attack #3) will always be easier than brute forcing even a 128-bit key (attack #4).

And even then, that still leaves attacks 1 and 2, and any other methods (such as "rubber hose cryptanalysis") of extracting the password from the user or their computer.  Those are the threats that you really should be concerned about.

1) In particular, practical large-scale general purpose quantum computers could theoretically break AES-128 about as easily as conventional computers with a similar clock speed could break DES.  So far, the actual quantum computers that have been built aren't anywhere close to being able to do anything cryptographically useful, but it's always possible that there could be some kind of a massive quantum computing breakthrough within our lifetimes.  For whatever it's worth, that's currently the best argument I know of for switching to 256-bit keys.  Of course, such a quantum computing revolution would also totally destroy all public-key crypto algorithms in common use today.

2) Indeed, some currently known related key attacks on AES are more effective against AES-256 due to differences in its key schedule.  Fortunately, such attacks require a very specific combination of circumstances, and are not possible if the AES keys are derived using a proper key derivation function.


do koblitz curves over $\mathbb{F}_{P}$ as generalized in SEC2 always have $a$ as 0? I reviewed all the curves in http://www.secg.org/SEC2-Ver-1.0.pdf . All the secp*k* curves have the $a$ parameters as 0 and those are the only ones with the $a$ as 0.

Is this a defining requirement of a Koblitz curve - that the $a$ parameter must be 0?

http://www.secg.org/SEC2-Ver-1.0.pdf#page=10 says the following:

  The name Koblitz curve is best-known when used to describe binary anomalous curves over $\mathbb{F}_{2^m}$ which have $a, b \in {0, 1}$. Here it is generalized to refer also to curves over $\mathbb{F}_{P}$ which possess an efficiently computable endomorphism

While $a, b \in {0, 1}$ appears to be true for $\mathbb{F}_{2^m}$ it does not appear to be true for $\mathbb{F}_{P}$. In particular, $b$ is not $1$ in any of these curves. In secp224k1 it's $5$. In secp256k1 it's $7$. Maybe the generalization allows for $a \in {0, 1}$ whilst requiring $b = 0$ in $\mathbb{F}_{P}$? Maybe in the generalization $a = 0$ is a requirement? Or maybe the fact that $b = 0$ in all these curves is still, despite the generalization, is none-the-less by random happenstance?

Neal Koblitz is an actual person who did more than one thing in his life. Notably, he proposed several types of curves, which are all "Koblitz curves", but not necessarily all following the same rules.

Generally speaking, the "Koblitz curves" we are talking about have a common property which is that they have an efficiently computable non-trivial endomorphism. An endomorphism $\phi$ maps a curve point to another curve point, with the property that for any two curve points $P$ and $Q$, then $\phi(P+Q) = \phi(P) + \phi(Q)$. When working over a curve of prime order $n$ (or a subgroup of the curve, of prime order $n$), then an efficient endomorphism $\phi$ is necessarily equivalent to multiplying by a given scalar $k$. The endomorphism is said to be "efficient" if it can be computed faster than usual multiplication of a point by a scalar.

On binary fields $\mathbb{F}_{2^m}$, Koblitz proposed curves that are actually defined over $\mathbb{F}_2$. In $\mathbb{F}_2$, there are only two values, $0$ and $1$. Thus, the curve equation $y^2 + xy = x^3 + ax^2 + b$ must be such that both $a$ and $b$ are in $\mathbb{F}_2$, i.e. are $0$ or $1$. Then, that curve equation is used over the field $\mathbb{F}_{2^m}$, which is an extension of degree $m$ over $\mathbb{F}_2$ (we usually use a prime $m$). Such a curve has some interesting property:

Its order is easy to compute. No Schoof/SEA shenanigans, just some plain additions and multiplications.
Since $\mathbb{F}_2 \subset \mathbb{F}_{2^m}$, the curve on $\mathbb{F}_2$ is a subgroup of the curve on $\mathbb{F}_{2^m}$. Hence, the order of the latter must be a multiple of the order of the former. This prevents the full curve from having prime order. If $m$ is prime, though, then it is possible to have the full curve order be the product of a big prime with either $2$ or $4$, which is considered good enough for cryptography. Indeed, the order of the curve over $\mathbb{F}_2$ is $2$ if $a = b$, $4$ if $a \neq b$.
If $b = 0$ then the curve is singular and various problems occur (and it's not good for cryptography). So we can assume that $b = 1$.
The efficiently computable endomorphism is $\phi(x,y) = (x^2,y^2)$. This is known as the Frobenius endomorphism. In a binary field, squaring is an automorphism (notably, $(u+v)^2 = u^2 + v^2$, for all values $u$ and $v$), which makes that operation "compatible" with the curve equation, as long as $a^2 = a$ and $b^2 = b$, which is the case since we chose both values to be $0$ or $1$.
Applying the Frobenius endomorphism $m$ times brings you back to the original point. This, in fact, defines $m$ endomorphisms. A consequence is that it reduces difficulty of discrete logarithm by $(\log m)/2$ bits, which is not a big deal (it means with with $m = 283$, you do not get "141-bit security" but closer to "136-bit security").

The endomorphism can be used for an efficient point multiplication in which point doubling is replaced with application of the Frobenius endomorphism.

On prime order fields $\mathbb{F}_p$, with $p = 1 \bmod 3$ a prime number, Koblitz proposed equation $y^2 = x^3 + b$ (i.e. $a = 0$ in the usual short Weierstraß equation):

Since $p = 1 \bmod 3$, then there are three distinct cubic roots of $1$ in the field. One of them is $1$. Let's call $u$ another cubic root of $1$; the third cubic root is then $u^2$. The roots are linked with the relation $1 + u + u^2 = 0$.
The efficient endomorphism is $\phi(x, y) = (ux, y)$. You can trivially verify that for any point $P$, $\phi(P)$ is indeed a curve point. Less trivially (you have to work it through the addition formulas), this is indeed an endomorphism.
The endomorphism can be used for speed up point multiplications, but not as much as the Frobenius endomorphism in the binary case. The reason is that applying $\phi$ only three times brings you back to the start point. In that sense, it is "less powerful" than the point doubling operation, and cannot be used to replace all doublings in a multiplication. It can still help avoiding half of the doublings; this is known as a GLV curve. This optimization is not often implemented because it has a few hidden costs and is hard to do with pure constant-time code.
If we use the same equation with a prime $p$ such that $p = 2 \bmod 3$ then we get a supersingular curve, with exactly $p+1$ points. Such a curve allows for efficient pairing computations with a very small embedding degree (only $2$, since $p^2-1$ is a multiple of $p+1$). In other words, you need a much larger $p$ to achieve decent security, and that kills performance; this is done only if you want a pairing for advanced things such as identity-based encryption. Even for that, there are better pairing-friendly curves (e.g. Barreto-Naehrig).

Both types of curves are "Koblitz curves", but certainly not the same kind of curve.

In practice, curves on binary fields are being abandoned, because it turned out that we don't have a good intuition about what happens on binary fields, and cryptographers got afraid and panicked. They may be back, much later on, when the current generation has died away. The other type of Koblitz curves, on prime fields, is well alive and kicking; for instance, the main curve in Bitcoin is secp256k1, with equation $y^2 = x^3 + 7$.


NIST randomness test p values I have a binary sequence of length $2^{20}$. I am using the NIST statistical test, assess.

What should be taken for ./assess and  How many bitstreams? in this test?
In the final Analysis report, what p-values should be there to pass this test?

In general, if you draw a sample at random from a distribution $D$, and you apply a statistical test for the null hypothesis $D$ yielding a $p$-value, and you print the $p$-value, rounded to, say, a multiple of 0.05, it is as if you rolled a fair d20 to pick among the possible results.  (For finer granularity, roll a die with more sides.)  That's all that a $p$-value is.

One might hope that the test was designed so that if you sampled from a different distribution $D'$ instead of $D$, an alternative hypothesis, it is as if you rolled a d20 with a weight on one of the faces so that it comes up <0.05 most of the time.  Then if you raise an alarm whenever $p < 0.05$, there's a 5% false alarm rate in your test of the null hypothesis, and a high true alarm rate when there's a problem and you're actually sampling from $D'$.

In the statistics literature, the false alarm rate for a test like this is confusingly called the ‘significance level’; the true alarm rate is called the ‘statistical power’.  The false alarm rate depends only on the null hypothesis $D$, not on $D'$, while the statistical power depends only on the alternative hypothesis $D'$.  A poorly designed test might behave identically on $D$ and $D'$, in which case an alarm means nothing at all about $D'$ even if your ‘significance level’ is 0.05.  (An exceptionally poorly designed test might even have a lower alarm rate under $D'$.)

Typical ‘randomness tests’ like dieharder and the NIST SP 800-22 suite* are collections of statistical tests for a null hypothesis of the uniform random distribution $D$ on bit strings.  They have high statistical power to detect very simple-minded alternative hypotheses like strings of IID bits with 1/4 chance of 0 and 3/4 chance of 1.  They do not have high statistical power to detect alternative hypotheses like strings of $\operatorname{AES256}_k(0) \mathbin\| \operatorname{AES256}_k(1) \mathbin\| \cdots$ for uniform random key $k$.

What really matters in cryptography is how you got your sample.  There are two options:

You got your sample by measuring a physical process like counting ionizing events in a Geiger–Müller tube.  In this case, you should have a specific probabilistic physical model in mind with fancy words like Poisson process: to measure the cryptographic value of this process you need to study the physics and engineering of the process to determine a lower bound on its min-entropy by finding the best way to reliably predict what the output is with the help of teams of trained physicists and engineers.

The NIST tests cannot help you here: they don't know anything about Geiger–Müller tubes.
You got your sample by computing a difficult-to-invert function on a small random input.  In this case, the difficult-to-invert function, like AES-256, should be well-studied by teams of trained cryptographers around the world publishing papers with fancy words like differential cryptanalysis to get confidence that it really is difficult to invert.

The NIST tests cannot help you here: they don't know anything about cryptanalysis techniques.

So what can the NIST tests do?  Not much, really.  They might give you hints about particular nonuniformities in the distribution that lead you to ideas about (1) or (2), that's all.

But, if you want cookie-cutter answers to questions…

  What should be taken for ./assess and How many bitstreams? in this test?

Pass the number of bits in your stream to ./assess.  Specify 1 bit stream.

  In the final Analysis report, what p-values should be there to pass this test?

Always use p < 0.05, unless it's a two-tailed test in which case use $p < 0.025$ or $p > 0.975$.  Beware of green jelly beans.

* Other tools like ent and the NIST SP 800-90B suite fit parameters to model families and compute or estimate the entropy of the resulting models.  Many of the concepts are the same, and likewise these tools are too dumb to know anything about your physical process in (1) or your difficult-to-invert function in (2).


Secure way to derive separate encryption and MAC keys from a single master key? I want to derive a 256 bit encryption key and a 256 bit MAC key from a single 256 bit master key for an authenticated encryption scheme.

I was considering the following construction to derive the two keys using a secure 256 bit hash algorithm e.g. Keccak:

Key 1 for encryption = H(master key | '0')
Key 2 for MAC = H(master key | '1')

The advantage of this is that if the MAC key is compromised, it will not lead to decryption of messages as it should be hard to find a pre-image for the one-way hash to determine the master key and thus the derived encryption key.

Also, if only the encryption key was compromised, then this would also not compromise the master key so the attacker should not be able to determine the MAC key and be able to forge future transmissions.

Is this a secure method to derive two keys from one key? If not, what is a more secure method?

Yes, this should be secure, as it is largely compatible with KDF1 and KDF2 which basically use a 4 byte big endian encoding of the counter instead of a direct ASCII conversion to a byte. Note that this construct works fine for master keys (short length, high entropy) but may be vulnerable to length extension attacks if larger input is allowed.

However, if you want to use the latest and greatest, you could use HKDF, possibly even augmented with a salt for session keys.

HKDF and the KDF's in NIST SP800-108 typically have a better security proof and supply methods of expanding the amount of key material after extracting the key material from the input. They also incorporate methods of supplying an explicit label and other information (using "enc" and "mac" instead of '1' / '2'). Unfortunately they are not often present in cryptographic libraries, they are harder to implement, they are badly defined and they seem to offer relatively few benefits over simpler schemes such as KDF1 and 2.


Why is a certificate needed at client side I was wondering why you need a certificate of the server at client side. Can't you just fetch it from the CA itself? I am using mbedtls to program some small client, and in all the client examples they use a certificate of the server. However, if you need to specify the server certificate to be able to make a connection to it, then how are browsers able to verify all secure websites? I don't think they have all certificates of all servers hard coded (which is off course not possible as new secure websites arise every day)

I think you are confusing something in the mbedTLS ssl_client1 example. The example does not specifiy the server certificate, but the CA (Certificate Authority) certificate. The client loads the CA certificate into its CA chain. Later on it still requests the certificate from the server (ssl_handshake step) and uses the public key inside the CA certificate to verify the certificate it received from the server.


Big Endian conventions or what? Let be $m \in \{0,1\}^{l}$ and $r \in \{0,1\}^{|N|-l-1}$.
I have seen that $m||r$ (where || means the concatenation of the bits) can be seen like an integer, I think using a Big-Endian Convention, and this integer is $m + 2^{l}r$.
The question is why?
What is the way to convert the bits-string $m||r$ to the integer $2^l r$.
I have to understand this because, it is useful to  solve some exercises.

Thank you.

If $m\|r$ is assimilated to the integer $m+2^{l}r$, with $m\in\{0,1\}^{l}$, then little-endian convention is being used.

More precisely: under (unsigned) little-endian convention, a bitstring of $k$ bits $b=b_0\|b_1\|\dots\|b_{k-1}$ where each $b_i$ is a single bit is assimilated to the (non-negative) integer $\tilde b\,=\,\displaystyle\sum_{i=0}^{k-1}b_i2^i$ . It follows that if $m$ and $r$ are bitstrings, the bitstring $m\|r$ is assimilated to the integer $\widetilde{m\|r}\,=\,\tilde m+2^{|m|}\tilde r$ (where $|m|$ is the number of bits in bitstring $m$ ).

For example, if $m\,=\,\mathtt{'00110101'}$ and $r\,=\,\mathtt{'1010'}$ , then $|m|=l=8$ , bitstring $m$ is assimilated to the integer $\tilde m=2^2+2^3+2^5+2^7=172$ , bitstring $r$ is assimilated to the integer $\tilde r=2^0+2^2=5$ , bitstring $m\|r\,=\,\mathtt{'001101011010'}$ and is assimilated to the integer $\widetilde{m\|r}\,=\,2^2+2^3+2^5+2^7+2^8+2^{10}=1452$ , and indeed $172+2^8\cdot5=1452$ .

Under (unsigned) big-endian convention, $b=b_0\|b_1\|\dots\|b_{k-1}$ is assimilated to the integer $\hat b\,=\,\displaystyle\sum_{i=0}^{k-1}b_i2^{k-1-i}$ . It follows that $m\|r$ is assimilated to the integer $\widehat{m\|r}\,=\,2^{|r|}\hat m+\hat r$ .

For example, if $m\,=\,\mathtt{'00110101'}$ and $r\,=\,\mathtt{'1010'}$ , then $|r|=4$ , $\hat m=2^6+2^5+2^2+2^0=101$ , $\hat r=2^3+2^1=10$ , $m\|r\,=\,\mathtt{'001101011010'}$ , $\widehat{m\|r}\,=\,2^{10}+2^9+2^6+2^4+2^3+2^1=1626$ , and indeed $2^4\cdot101+10=1626$ .

The notation $\tilde{}$ for little-endian and $\hat{}$ for little-endian is entirely made up for the purpose of that answer, and omitted in practice. Endianness is considered too mundane to be made explicit, but/thus is a cause of endless headaches, incompatibilities, frustrations, and conversion code.

It is possible to use one convention for bits in $m$ and $r$, and the formula of the other convention for $m\|r$ , that is assimilate $m\|r$ to integer $\hat m+2^{|m|}\hat r$ or $2^{|r|}\tilde m+\tilde r$. That's mixed endianness, and surprisingly common, often with change of endianness at regular intervals, e.g. at the octet (8 bits) or/and word (e.g. 4 octet) level. In that case, the formula converting bits to integer grows hairy (the practitioner's hair looking at bits with a debugging tool are correspondingly pulled out).

Most humans (including cryptographers unless otherwise stated, perhaps obliquely by throwing $m+2^{l}r$ in) tend to use big-endian convention, for natural reasons: when we are told twenty-five predators are approaching, twenty goes before five because that gives the order of magnitude sooner. The same ordering is kept when writing 25.

Little-endian is often used for transmission of individual bits in bytes, historically because it eased interoperability between equipments using asynchronous communication and different character width. However network byte order, or network order for short, refers to big-endian convention at the upper level (if you look at how a 16-bit IP port number is physically transmitted on a network, e.g. with an oscilloscope across the contacts of the LED transmitting into optical fiber, a 10Mbit/s Ethernet twisted pair, or an old modem, you'll find that's with little-endian convention within an octet, and with the high-order octet first, that is big-endian at a higher level).

Intel's convention is essentially opposite: it uses little-endian byte order (the low-order octet of a word has the lowest address, and documentation shows it first whenever octets are separated from each others); but when documentation shows an octet, that's with big-endian convention (always for decimal and hexadecimal, often for binary; however bits remain numbered with 0 for the low-order bit; ISO standards often start at 1 to make things worse, but I digress).

Little-endian convention removes the need for buffer memory when adding integers represented by bitstrings, octet strings, or vectors of limbs made available sequentially or by increasing address (serial memories or CPUs favoring index increment over decrement; ironically, the later applies to the Motorola 68000 CPU, which use big-endian octet order). That makes little-endian popular for implementation of multiple-precision arithmetic, together with the fact that realloc() can be used to adjust storage without changing the value represented.

Big-endian and Little-endian refer to names of the two camps in a fictional war, which wanted to impose on the other side the opening of eggs by the big or little end; see Gargantua Gulliver's Travels for details. This should remind us that "more sensible xxxx endian" should be taken like eggs: with a grain of salt.

The two most common conventions for signed integers are nowadays:

Two's complement, where signed integer $x$ is represented by bitstring $b$ such that $-2^{|b|-1}\le x<2^{|b|-1}$ and the unsigned integer $\tilde b$ or $\hat b$ is $x\bmod2^{|b|}$ , lying in interval $[0\dots2^{|b|})$.
Sign and magnitude, where signed integer $x$ is represented by bitstring $b$ such that $-2^{|b|-1}<x<2^{|b|-1}$ and the unsigned integer $\tilde b$ or $\hat b$ is

$2^{|b|-1}-x$ when $x<0$
$x$, otherwise

Under both sign conventions, one of the bit of $b$ (the first when combined with big-endain convention, the last with little-endinan) is the sign bit, with $1$ for negative.

Under two's-complement, the result of addition modulo $2^{|b|}$ can be obtained using the same rules for unsigned and signed integers (only overflow detection varies). This explains why two's-complement is common in modern CPUs.


What is the LENGTH parameter in EEA2? In the EEA2 option for encryption in LTE the AES-128 algorithm is mechanized. There, the nonce used in the CTR Mode is a 128-bit value. The first 64-bits are covered by a COUNTER, a BEARER, a DIRECTION, and a LENGTH parameter. LENGTH parameter is supposed to control the output of the KEYSTREAM length (not changing the bits themselves).

However, I was not able to find anywhere a useful description of how this parameter actually works. Available documentation gives detailed descriptions of the COUNTER, BEARER, and DIRECTION parameters (these amount to 38-bits) and the rest 26-bits are set to 0 (the remaining 64-bits are set to 0 and then incremented).

Does anyone know what this LENGTH parameter does and how it works? It seems to me it has no particular reason to be mentioned...

It is simply a parameter for indicating the length of the keystream in bits. Internally, EEA2 will call AES the appropriate number of times to produce that much output, truncating the last block as needed. It is not mixed into AES inputs or the key, so like you said it has no effect on the output bits themselves, beyond choosing how many are taken.


Negligible function defined as product of polynomial and a negligible function How do I prove that a function $f_2$, defined as the product of a negligible function $f_1$ and a polynomial $p$, is itself negligible?

$$f_2(n)= p_1(n)f_1(n)$$

I see $f_2$ as negligible simply because I know that if you have something that has a negligible probability of happening $(f_1)$ then if you try a polynomial number of times $(p)$ we are still left with a negligible result. But I do not know how to prove this. I would appreciate if someone could point me in the right direction.

I have had a look here in  particular the proof for the second Lemma, I think my question is related to the necessity part of the proof, but it seems to have confused me more than it helped.

Since $f_1$ is negligible, it is smaller than the inverse of any polynomial, for all sufficiently large $n$. In particular, given any polynomial $q$, it is smaller than $1/p_1q$.


While generating a random Elliptic curve what are the conditions i have to considerd? I want to generate a random elliptic curve over a prime field. What are the conditions I should satisfy?
For the NIST recommended standard ECC-224 bit curve with prime $p=2^{224}-2^{96}+1$, a reduction technique is given by $(z_1+z_2+z_3-z_4-z_5)
\bmod{p}$, what is the logic behind in this?

Baring other requirements that you did not explain:

An elliptic curve can be written as $y^2=x^3+ax+b$. To generate a random curve over a prime field, choose $a,b$ at random from the prime field.


Can you help me understand PFS and wPFS? Every time I encounter the concepts of PFS (perfect forward secrecy) and wPFS (weak perfect forward secrecy), I feel uncertain about them.

My understanding is that:

PFS ensures that, if the parties' long-term keys have compromised in the future by an active adversary, he cannot calculate the session key.
wPFS ensures that, if a passive adversary has learned the private keys of both peers to the session, and if the session is "clean", he still cannot recover the session key.

I'm not sure whether my understanding is right or not.
And I don't know the if these are the correct definitions of PFS and wPFS.

Can you help me understand PFS and wPFS?

The difference between weak and strong perfect forward secrecy lies in the capabilities of the attacker. Perfect forward secrecy is strong if it remains secure in the face of an active attacker, while weak perfect forward secrecy's security claim only covers passive attackers.

If I'm not mistaken weak perfect forward secrecy (wPFS) is a term introduced to claim perfect forward security for a 2-message protocol, disregarding MITM attacks.

A quick Google search revealed that this term was probably coined by Hugo Krawczyk in his 2005 paper HMQV: A High-Performance Secure Diﬃe-Hellman Protocol.

I don't know how commonly understood this term is however, so if you're intending to use it for a paper make sure to explain it.


How to solve the Diffie-Hellman problem if $g$ is unknown? I am trying to solve the Diffie-Hellman problem modulo a composite number $N$, which I have factored. In this question, it was answered how to deal with such a situation. But how can I solve the problem if I don't know $g$?
$$y = g^x \pmod{N}$$

The exact numbers are:
$$N=442101689710611$$
$$g^a = 421049228295820 \pmod{N}$$
$$g^b  = 105262307073955\pmod{N}$$

And I need to find $g^{ab}\bmod N$.

In general, there are a huge number of possible values for $g^{ab}$, depending on what $g$ is.

However, in this case, whoever set up this problem took care to radically reduce the number of possibilities.

Here's how you would attack this problem:

Step 1: factor $N$
Step 2: for each prime power factor $q^k$ of $N$, we need to determine the set of values of $g^{ab} \bmod q^k$.  Two special cases where this is easy:

If $g^a = 0 \pmod q$, then obviously $(g^a)^b = g^{ab} = 0 \pmod {q^k}$, and so we have one solution to this subproblem.
If $g^a = 1 \pmod{q^k}$, then $(g^a)^b = g^{ab} = 1 \bmod {q^k}$, and so we have one solution to this subproblem.

In practice, these special cases don't come up that often, in this case, it does.

Step 3: once we have the set of possible solutions to each of the subproblems, we can use the Chinese Remainder Theorem to join them together to come up with the set of solutions to the original problem.

Now, normally, each subproblem comes up with a large number of potential solutions, and so the combinatorics of step 3 comes up with a truly huge number of solutions.

However, in this case, it turns out to be only two solutions to the overall problem (and, as luck would have it, you really don't need the CRT to join those solutions in step 3; there's a simpler way to compute them).


how to get top 10 numbers after using Pallier cryptosystem Assume I encrypted 1000 Integers using the pallier cryptosystem.

Since each time I encrypt a number using pallier I'm using a random r element from Z* then the encrypted numbers aren't in order anymore i,e: we have 2<3 but Enc(2) with pallier doesn't necessarily mean it is < then Enc(3) with pallier.

So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?

So how would it be possible to get the top 10 biggest Integers out of those 1000 Integers  when the numbers are encrypted?

That's easy; decrypt them with the private key, and then pick out the top 10 plaintexts...

If you don't have the private key (and can't interact with someone who does have the private key), then we hope it's impossible.  I say 'hope', because if it were possible, then you could deduce the contents of a Paillier ciphertext with just the public key (and hence, Paillier would be insecure).

Suppose we did have a way to find the top 10 out of a group of 1000; here's how we can test a ciphertext $C$ to see if its plaintext $P$ is $> k$ or $< k$ (for an arbitrary integer $k$); we would encrypt the value $k$ 999 times, and give those 999 ciphertexts, plus the ciphertext $C$ we're testing, to our method to find the top 10 - if the plaintext we're trying to deduce is $P > k$, then $C$ will be one of the 10; if $P < k$, it will not be.

Doing that technique, we can do binary search to reduce the possibilities for $P$ to a range of two values $k, k+1$; we can then homomorphically add $C$ to itself, and then perform the above test one last time to see if $2P$ is greater than or less than $2k+1$ - this gives us the final answer.

We hope that someone cannot do this, and so we hope that the problem you're asking to solve is infeasible.


Practical probabilistic proof systems not based on polynomials All practical probabilistic proof/argument systems I know of are based upon polynomial identity testing in finite fields. These constructions include QAPs, STARKs, GKR and many variants. In particular, they all rely on the Schwartz-Zippel lemma, and thus they all take place in a polynomial setting.

There are constructions that do not take place in a polynomial setting, such as the expander-graph based PCP. But they are impractical both asymptotically and in practice.

Are there constructions that do not take place in a polynomial setting, but are still potentially practical?

You can look the Groth-Sahai proof system; Its practical and has been well studied and it's not reliable to The Schwarz-Zippel lemma.
But it depends of the form of the equations you want to prove.


What is Deterministic Authenticated Encryption? I came across something known as deterministic authenticated encryption in my studies, and a lot of people were associating it with Synthetic IV mode.
I am having trouble understanding what exactly DAE is because I thought that if something was deterministic, it didn't have a sense of authenticated encryption. It violates the confidentiality of the message -- deterministic encryption modes are prone to CPA attacks.
Can someone explain in layman's terms what exactly DAE is? How does DAE differ from just normal deterministic encryption modes like ECB mode?

Deterministic authenticated encryption indeed provides authenticity and it doesn't require a nonce or IV. In that sense it doesn't provide CPA security as identical messages would result in identical ciphertext.

Authentication however doesn't really have to do with CPA security. It is about ensuring that the ciphertext was created by a specific party holding the secret key. In other words it provides authenticity of the ciphertext (and therefore plaintext). Furthermore it ensures that the integrity of the plaintext after decryption (and possibly the ciphertext before decryption) is maintained; i.e. that the ciphertext wasn't altered by an attacker or damaged somehow. If not the verification of the authentication tag will fail.

DAE differs with ECB in the sense that ECB doesn't provide authenticity or integrity of the ciphertext (if multiple blocks of plaintext are encrypted anyway). Furthermore ECB mode leaks information if identical plaintext blocks are encrypted. SIV mode on the other hand calculates an IV using the entire input. Even if just a single bit of plaintext is different the entire ciphertext will be indistinguishable from ciphertexts created from previous plaintexts.

This matters if you for instance wrap a large set of keys that do not encode to fully randomized blocks of data. Take for instance an RSA private CRT key, which consists of many numbers. Usually these are encoded, including the public modulus. It could well be that the same block contains only one byte of a private value. If you have many of those blocks then you will find duplicates, leaking information about the RSA private key. Horrible practices such as wrapping RSA keys using only ECB or CBC (using a zero-valued IV) are pretty wide spread.


Why is asymmetric encryption IND-CPA? According to Wikipedia, the IND-CPA game is:

  The challenger generates a key pair PK, SK based on some security
  parameter k (e.g., a key size in bits), and publishes PK to the
  adversary. The challenger retains SK. The adversary may perform a
  polynomially bounded number of encryptions or other operations.
  Eventually, the adversary submits two distinct chosen plaintexts
  $M_0$, $M_1$ to the challenger. The challenger selects a bit
  b $ \in \{0, 1\}$ uniformly at random, and sends the challenge
  ciphertext C = E(PK, $M_b$) back to the adversary. The
  adversary is free to perform any number of additional computations or
  encryptions. Finally, it outputs a guess for the value of b.

http://en.wikipedia.org/wiki/Ciphertext_indistinguishability

Because the adversary has the PK, this means he can encrypt any arbitrary text. Why can't he compare the ciphertexts from $M_0$, $M_1$ with the challenge ciphertext? Is the function $E$ different for the adversary and for the challenger?
Does this mean classic hash functions like SHA1, MD5, etc are not IND-CPA secure?

Thanks in advance!

This isn't just limited to asymmetric schemes; in any chosen-plaintext attack, even for symmetric ciphers, the attacker can (by definition of the CPA game) compute as many encryptions as they like (limited to polynomial time, of course). Formally, we say the adversary is given access to an "encryption oracle."

Anyway, you have stumbled across a necessary property for CPA security: any cipher that has IND-CPA security has to be nondeterministic. That is, every time a value is encrypted, the ciphertext should be (with overwhelming probability) different. Hence, an attacker can compute $E(m_1)$ and $E(m_2)$, but the challenge ciphertext will be different from either of those thanks to nondeterminism.

As a concrete example, look at the CBC mode for a block cipher. In this mode, each encryption uses an unpredictable IV which is XORed with the first block. Hence, each time you encrypt the same message, it will be (again, with overwhelming probability) a different ciphertext. So, you can't compare ciphertexts to learn if the plaintexts are equal.

In the case of RSA, a careful padding scheme has to be used to transform RSA into a nondeterministic scheme. One such popular padding scheme is Optimal Asymmetric Encryption Padding, often abbreviated as OAEP.

  Does this mean classic hash functions like SHA1, MD5, etc are not
  IND-CPA secure?

Hash functions aren't encryption schemes, so the notion of indistinguishable encryptions doesn't really apply. However, I suppose you could say they don't have "indistinguishable digests" under chosen-plaintext attacks because they are deterministic: if you wanted to build a distinguisher under CPA, you'd do exactly as you suggest in your question, namely compute $H(m_1)$ and $H(m_2)$ and compare that to the "challenge digest."

Actually, there is no secret associated with a hash function, so hash functions don't have indistinguishable digests under any model. If the attacker gets to know the messages, they can just compute the digest of the messages and compare them directly. So, in some sense, an attacker always has access to a "hashing oracle" by the nature of the algorithm. Instead of "indistinguishable digests", a hash function's quality is usually judged on how collision-resistant it is, how hard it is to find pre-images, and so forth.


Cipher recommendation for known-plaintext attack I need to encrypt a 4-digit number. The cipher-text can be up to 11 digits long and there are no limits for the key size.

Considering that the attacker has access to both the cipher-text and the plain-text but I want the key to remain secret, what algorithm would you recommend?

AES-128 in CTR mode would be more than sufficient. There is no efficient known-plaintext attack publicly known for it. Many others would also do the job.

However, the secrecy of the key depends primarily on the key itself. It should be sufficiently large and sufficiently random, so that it can't be brute-forced.


How to exchange a secret through untrusted server in two steps? I have a web application where I control the server, however, it should not have any knowledge of secrets that are exchanged between its users. This server holds RSA public keys of each registered user and can be trusted to deliver the correct public keys for each user when asked for them. A user's RSA public key is provided to the server whenever they register with the server. Users belong to "teams" and a user can only join a team by way of invitation from another already registered user that is a member of the team.

Alice is already registered and needs to invite Bob to her team and also deliver a team member secret to Bob. Bob is not registered yet, so Alice cannot ask the server for Bob's public key. Right now I have implemented this type of team member exchange where one user is registered while the other is not yet using a three step process:

Alice sends a team invitation to Bob.
Bob accepts the team invitation and registers with the server, providing the server with his public key.
Alice then asks the server for Bob's public key, encrypts the team secret and sends it to the server for Bob (who is now a member of Alice's team) to download.

Bob can now get the encrypted team secret from the server and decrypt it with his private key.

I am trying to reduce this team secret exchange to only two steps. Often times Alice will forget to come back and perform step 3 and would prefer to send the team secret in a secure way at the time of inviting Bob. This is simple to do if Bob was already registered with the server (the encrypted team secret could just be part of the invitation), but often times Bob is not yet registered.

Is there a way that I can perform this team secret exchange in a secure way using only two steps from the user? The server can be used as an intermediary to facilitate the exchange, but should not be able to read the secret.

Without changing an assumption somewhere, it does not look possible.

Here is what your ideal protocol would look like:

Alice sends the invitation to the server (to pass along to Bob), along with a message that is encrypted somehow, but not bound to Bob (as Alice doesn't have anything from Bob to distinguish him from anyone else)
Bob gets the invitation, and the encrypted message, and somehow (without any further interaction from Alice) decrypts the message

The problem is with step two; if Bob can decrypt the message, why can't anyone else (in particular, why can't the server)?  The server knows everything that Alice knows about Bob, and so the server can perform the decryption operation just as well as Bob can.

Now, a similar problem lies in the original protocol; when Alice downloads Bob's public key, the server could provide his own (and when Alice uploads the encrypted message, the server decrypts it, and reencrypts it with Bob's public key).  You did say that the 'untrusted' server can be trusted not to do this.

Obvious ways to address this:

Change the trust assumption; you already trust the server to be honest about public keys; also trust the server not to be malicious about reading intermediate mail (and with this assumption; Alice can encrypt the message with the server's public key, and have the server reencrypt it with Bob's when he downloads it).
Give Alice something from Bob (even a symmetric key) that the server doesn't know.


Is a die implemented in a physics engine truly random? So, a fair die throw is really random, not pseudo. So, would a RNG implemented as the result of a die throw in a physics engine (say, Newton, Havok, Nvidia's PhysX) be regarded as both cryptographically secure and really random (Not a PRNG, but a real RNG)?

No, that would not be a true RNG, because these physics engines would just repeat the exact same calculation and thus repeat the whole sequence of random numbers - like a PRNG. The starting conditions are the seed of this PRNG.

Dice are truly random in the real world. Well, are they? If we ignore quantum effects, we could measure all relevant values of the environment and then calculate the next value of the die - at least in theory. In practice the calculations are much too difficult, and the quantum effects destroy even the theoretical possibility to calculate the result.

The physics engines mostly calculate only the important parts of the calculation: the collision with other objects and the gravity. But in the real world, we got air movement (wind, breathing of a human), fluctuation in the temperature, very small movement of the earth, difference in the gravitational field of Earth, or even the vibrations of the heart, wear and tear of the dice or just contamination in the material.

Even if the engine could calculate all this in an acceptable time period, it would have to introduce a RNG itself to simulate the quantum effects. If the engine does this (like mentioned by mikeazo in a comment), then why use the engine and not the RNG directly? If the output of the engine is bigger than the input from the intern RNG, it can't be a true random number generator anymore. It would have to stretch the random numbers. Maybe it's still secure, but using AES in CTR mode would do the same with surely much better properties.

Fun fact: There's the Dice-o-matic which again and again rolls many dice to determine random numbers. It's used to get random numbers for an online game platform. Well, that could be the closest you will come to get true random numbers from a machine with dice.