Distinguishing between a Polynomial and a Laurent Polynomial Let $f(x) \in \mathbb{Z}_p[x]$ (for a prime $p \gg d$) be a polynomial of degree $d$, and let $g(x)$ be a Laurent polynomial with the same degree and only the first negative exponent term ($g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d$) over the same field.

Now, say we are given oracle access to both these functions with the additional condition that we can only $< d$ queries (Else we can just ask $d+1$ queries and interpolate the points to check if the function is a polynomial or not - this was the only way I could think of.)

Is this possible - if the test doesn't have to be perfect and can have some false positives or negatives?

Is this possible

Unless querying $g(0)$ gives you a distinguishable error for a Laurent polynomial, and assuming that the values $a_0, …, a_d$ are equidistributed (for both the Laurent and normal polynomial cases), it's not possible if you are limited to $d$ queries.

The question is equivalent to asking "you're given Oracle access to a Laurent polynomial $g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d$, can you determine whether $a_{-1} = 0$?" [1]

Well, for any fixed value of $a_{-1}$, the $d$ queries can result in any of the $p^d$ possible sets of responses with equal probability (because there exists a unique polynomial $a_0 + a_1 x + \dots a_dx^d$ that results in the $d$ required $g(x) - \frac{a_{-1}}{x}$ values).  Because this is true for any value of $a_{-1}$, we cannot gain any information on its value (including whether or not it is 0).

[1]: Along with the convention that $\frac{0}{0} = 0$


Why would we use a Key Agreement Protocol if we already have a key between 2 entities? For example in my course there is this protocol :

Initialisation: A and B are sharing a symmetric key S.
(1) A -> B: Ra ; A generates a random number and sends it to A
(2) A <- B: Rb ; B does the same
A and B computes the session key K := E_S(Ra XOR Rb).

Why A and B would establish a new key K if they already have the key S ?
I don't get it.

For me, the Diffie-Hellman protocol is coherent because it establishes a key between 2 entities that have never talked before.

Hint

Consider what would happen if an adversary somehow managed to recover the session key.

Spoiler

If they simply used the shared key as the session key directly, then an adversary who compromises the key can then compromise all future communications.

If they derive the session key using the shared key, then an adversary who compromises the session key only compromises the current session.

Why not just use DH?

There are plenty of reasons - the first is probably to demonstrate the point above.

Secondly, DH is more computationally expensive then the pre-shared key technique.

Some real world protocols do in fact offer the ability to secure a communications channel via pre-shared keys.
A constrained device may not be able to afford the circuit size/power/time/bandwidth to use DH


How can I send a secure public message using ECC? I want to know how to send a secure message protected with elliptic curve private and public keys.

In this case, the private key will be included in the site code and anyone can read it.

No, the private key is not in the "site" code, it is not send. It is just used to authenticate the TLS session, by placing a signature that can be verified with the public key in the X.509 certificate. This certificate has been exchanged before in the handshake and it has been verified & validated in the browser. The private key must be kept private, as the name implies.

  How can I send a secret message encoded with a key (key1) and only able to be decoded with another secret key (key2), which I only know it, (using ECDSA).

The ECDSA encryption method cannot be used to encrypt messages to keep them confidential. But it can authenticate the handshake. This handshake establishes the session keys, commonly by performing (EC)DH key agreement using two temporary (ephemeral) key pairs generated both by the client and server. These symmetric session keys can then be used to protect the messages.

If you want to perform encryption with Elliptic Curves then you should have a look at the Elliptic Curve Integrated Encryption Scheme or ECIES.

Minimal description of ECIES

For ECIES the sender generates an message specific EC key pair.

The sender then performs key agreement with the generated private key and the (trusted) public key of the receiver. The sender then uses the resulting key material for normal symmetric encryption. The message specific private key of the sender can be discarded after the symmetric key has been derived; it is just needed to calculate the symmetric key once.

The established symmetric key can be used with any block cipher mode of operation - or indeed with a stream cipher to create the ciphertext. It would of course be a good idea to use authenticated encryption to do this. The message specific public key and ciphertext can be combined and send to the receiver.

The receiver then performs his own key agreement with the receivers static private key and the senders message specific public key. This should derive the same symmetric key, which can finally be used to decrypt the ciphertext.


Why does a broken hash function undermine an HMAC? For instance, what makes MD4 a bad choice for an HMAC?  In this case I am asking about MD4 because its less than ideal.  I know that a preimage attack can be used to undermine the system,  but why?  What is the attacker calculating?

Actually, HMAC might still be secure for a hash function that is broken (with respect to the requirements of a cryptographic hash function, such as primary preimage resistance, secondary preimage resistance and collision resistance), but it must not be too badly broken. If you read the original paper, you see that the authors assume things such as the hash function being "weakly collision resistant", or more precisely that the inner hash function is collision resistant only to adversaries that see the hash value only after it being hashed again with a different secret key.

Also, since HMAC, contrary to NMAC, doesn't use two independent keys, but a single key that is combined with two different pads using XOR, additional assumption about the pseudo randomness of the hash function are made.

I believe MD4 does not even meet these weaker assumptions, and that is why HMAC-MD4 is considered to be broken, while e.g. HMAC-MD5 is not (yet).


Exploitability of AES in CBC Mode For Recovery of Plain Text I'm aware of existing literature that shows in a comprehensive manner just how simple it is to tweak the ciphertext of AES-CBC such that the decrypted message ends up being entirely different than what it was originally (due to the lack of a MAC to provide AEAD).
Can This Be Used to Compromise Encrypted Keys?
Specifically, I came across documentation for a popular piece of software that countless individuals around the world use. This software package generates a private/public key pair for the end user (secp256k1) and encrypts the private key with AES-256-CBC.
Wondering if CBC Mode Poses Any Issue Here
To be clear, by 'issue', I'm referring to the outright recovery of the private key that was encrypted.
If the secret key is damaged / altered in this scenario, that's of no concern (for the question). Not sure if it makes a difference to add in that the key will be decrypted and re-encrypted as it is used (not sure if there is any leakage of the private key data that occurs during this time).

No, in this situation, CBC mode doesn't pose any security with a 256-bit uniform random AES key.
At data on rest, the AES-CBC has Ind-CPA security.
There is a padding oracle attack on the CBC mode due to PKCS#7 padding, however, that is not applying here since there is no server to query the padding.
There are multi-target attacks and quantum attacks on the AES, however, they are not possible on AES-256 which is the reason that it is the golden standard around.
The only problem that can occur on the user's side,

User has a weak password that can be found, severe!
User-machine has been hacked, severe!


Are there any LFSR-based ciphers with variable feedback polynomials? All LFSR-based stream ciphers that I know of use a fixed feedback polynomial (i.e. the taps are always in the same position). I know that, at least for non-trivial output lengths, it is necessary to ensure that the polynomial is primitive to avoid creating an LFSR with a short cycle. Are there any published stream ciphers which use a secret-dependent or otherwise variable feedback polynomial? I am only aware of one proposed modification to A5/1. If there are good reasons why this design is so rare (just as there are good reasons why data-dependent rotations are rare), what are they?
I can think of a few possibilities:

The security improvement is too slight to be worth the added implementation complexity.

Deterministically selecting a new feedback polynomial with good properties on-the-fly is difficult.

There simply is not enough research into the behavior of LFSRs with variable taps.

To the best of my knowledge, an $n$-bit LFSR requires $n$ bits of keystream to determine the state. With secret feedback polynomials, $2n$ bits are required (using the Berlekamp-Massey algorithm to find the tap positions). Wouldn't this be a simple way to make known-plaintext attacks harder?
Although I'm most curious about LFSRs, an answer describing NLFSRs would also be interesting.

I think the reason this is not so popular is a combination of the three reasons you surmised. It is quite difficult to control properties of such a generator. There was at least one paper (can't recall reference) where the suggestion was to use a secret key to make a choice out of a collection of primitive LFSR polynomials.

I do know of another unpublished example, but I need to find my hardcopy of the manuscript to give you the gist of the design, which may take a day or two. It was never submitted for publication, to the best of my knowledge.


Is it feasible to execute a range query over tokenized data? Suppose we have a DB with n records on it, one of the fields is numeric and considered sensitive (e.g. ID number).  If we use tokenization for said field, could we query all records between x and y?
So far the only option I have seen depicted was preserving head and tail as it is and just tokenizing the middle part. I am not so convinced by that approach since it feels like too much leakage might be going on.
As I understand it then, should we limit its usage to searching(since it is a 1:1 map)?

P.S: I got this question while reading the white paper The Cloud Encryption Handbook. Where it reads:

Data tokenization involves creating tokens for each plaintext, . . . searching for keywords and SORTING DATA on the server are possible.

The user @pg1989 has co-authored it, so maybe he has interesting inputs about it as well.

Since I was specifically mentioned in the question, I'll take a stab at answering it.

First, note that the whitepaper was ghostwritten by a couple of marketing people. These (talented and lovely) marketing folks changed and simplified some terminology to match what is used in other marketing materials the company uses. This is pretty standard in industry, but it does sometimes result in things getting confused.

Here, the confusion is that two different kinds of tokenization are both being called "data tokenization". Regular old tokenization can support search because it is deterministic, but to preserve sort order you need to use a different tokenization algorithm. If you're curious you can read the details in this patent. The algorithm is more or less an embellishment on the BCLO order-preserving encryption scheme, but uses some clever tricks (which exploit the fact that you have all plaintext/ciphertext mappings available in the token database) to make token generation very fast. Otherwise, it has all the properties of the BCLO OPE scheme, which means that you actually can perform range queries on tokens.

Note, though, that the BCLO scheme has some very serious security drawbacks. Following a lower bound in a follow-up paper written by some of the same authors, a couple of recent works have found that the attack implied by this lower bound is devastating for security in basically any practical setting people actually care about. Perhaps more worryingly, these papers found that all OPE schemes (not just BCLO) that are efficient enough to deploy are vulnerable to serious attacks in practical settings.

If all you want to do is range queries, "more secure" approaches exist. The phrase "more secure" is in quotes because the extent to which they actually resist determined attacks is an open question right now. We know they resist existing attacks on OPE, but we don't know much else.

For example, last year a paper was published which showed that given enough queries, an attacker that only observes the amount of communication between a client and server (and no other leakage whatsoever) can fully recover plaintexts from any system which enables range queries on encrypted data. This attack requires a huge number of queries and is therefore not very practical, but there is some (not yet published) follow-up work which extends the attack to work with a very small number of queries. In systems with high query volume, this improved attack could completely recover the data in a matter of hours.


Can you help with that definition for a CCA? The following is a definition taken from Introduction to Modern Cryptography by Katz and Lindell.

I'm having a hard time understanding some basic concepts! Can you please help me?
$\newcommand{\Gen}{\operatorname{Gen}}\newcommand{\Enc}{\operatorname{Enc}}
\newcommand{\Dec}{\operatorname{Dec}}$

  Consider the following experiment for any private-key encryption scheme
  $Π=(\Gen,\Enc,\Dec)$, adversary $A$, and value $n$ for the security parameter.
  The CCA indistinguishability experiment PrivK:Aan (n) is:

  A key $k$ is generated by running $\Gen (1^n)$.
  The adversary $A$ is given input $1^n$ and oracle access to $\Enc_k (·)$
  and $\Dec_k (·) $. It outputs a pair of messages $m_0, m_1$ of the
  same length.
  A random bit $b\in \{0,1\}$ is chosen, and then a ciphertext
  $c = \Enc_k(m_b)$ is computed and given to $A$. We call $c$ the
  challenge ciphertext.
  The adversary $A$ continues to have oracle access to $\Enc_k (·)$ and $\Dec_k (·)$,
  but is not allowed to query the latter on the challenge ciphertext itself.
  Eventually, $A$ outputs a bit $b'$.
  The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise.

In the second bullet point what does "It outputs a pair of messages" mean? Who and where does it output those messages? Does the adversary output the messages? The oracle?
What's the purpose of the random bit b?

In step 2, the adversary outputs two messages. One of these will be selected at random for encryption. You can think of the adversary sending these messages to a "challenger" that also has oracle access (or is the oracle itself). It doesn't really matter who is running the challenge since the challenger doesn't have any "intelligence." All the challenger does is flip a coin to choose a message and remember which message she chose, so she can determine if the adversary guesses correctly or not.

If you think of the adversary as an interactive Turing machine, then the values are put on its output tape (likely why it was phrased that way in the text).

The random bit is just a formalization of flipping an unbias coin. The challenger uses it to pick one of the two messages. If the ciphertext of a given plaintext is indistinguishable from any other ciphertext, then the adversary cannot know which one was chosen any better than predicating the value of the coin flip: which is one half. Therefore, if the adversary can demonstrate the ability to predict better than one half which message was encrypted, it must be the case that the encryption function causes the ciphertexts to leak information about the plaintexts (either by looking at the ciphertext or by submitting related ciphertexts for decryption). In this case, the system is not CCA-secure.


Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states:

Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-invariant is not supersingular and that $j\neq 0 $ or $1728$.
Then the modular polynomial $\Phi_l(j,T)$ has a zero  $\tilde{\jmath} \in \mathbb{F}_{p^r}$ if and only if the kernel $C$ of the corresponding isogeny $E \mapsto E/C$ is a one-dimensional eigenspace of $\phi^r_p$ in $E[l]$, with $\phi_p$ the Frobenius endomorphism of $E$.

From the proof:

If $\Phi_l(j,\tilde{\jmath} )=0$, then there exists a cyclic subgroup $C$ of $E[l]$ such that the $j$ invariant of $E/C$ is equal to $\tilde{\jmath}\in \mathbb{F}_{p^r} $. Let $E^1$ be an elliptic curve over $\mathbb{F}_{p^r}$ with $j$ invariant equal to $\tilde{\jmath}$. Let $E/C \mapsto E^1$ be an $\bar{\mathbb{F}}_p$ isomorphism and let $f: E \mapsto E/C \mapsto E^1$ be the composite isogeny. It has kernel $C$.

I can see $f$ is defined over $\mathbb{F}_{p^r}$, so this implies existence of an isogeny $E \mapsto E^1$ over $\mathbb{F}_{p^r}$.

How does this imply that $C$ is an eigenspace of $\phi^r_p$?

How does the statement "The Frobenius endomorphism over $\mathbb{F}_{p^r}$ satisfies the same characteristic equation" imply that $C$ is an eigenspace of $\phi^r_p$?

Please help me to understand this.

I have struggled with this proof, but here is how I tried to reason through it:

The Frobenius endomorphism can be represented by a $2 \times 2$ matrix over the torsion group $\mathbb{E}[\ell]$.  You may as well raise $\phi$ to some $r$ power, $\phi_q^r$, and get an eigenvalue equation for this matrix.

You get a subgroup $C$ of $\mathbb{E}[\ell]$ such that $\phi_q^r (P) = \kappa P$ if the characteristic equation has a root $\kappa$. From Vélu's formulas, we can build an isogeny from $\mathbb{E}$ to another elliptic curve $\mathbb{E}'$ such that the kernel of the isogeny is $C$. The Frobenius endomorphism only permutes the points in $C$, leaving the $j$-invariant of $\mathbb{E}'$, well...invariant.

So the $\phi_q^r$ define a subgroup / eigenspace that can, via Vélu, generate an isogeny where it's the kernel.

More discussion:

Are you familiar with Vélu's formulas? They may be the missing link for you. Basically: assume you have an elliptic curve $\mathbb{E}$ over some field $\bar{K}$, and let $C$ be a finite subgroup of  $\mathbb{E}(\bar{K})$. Then, Vélu tells you that there is another group $\mathbb{E}'$ and an isogeny $\chi:  \mathbb{E} \rightarrow \mathbb{E}'$ such that $C = \text{Ker}(\chi)$. They even explicitly give you a formula for the isogeny!
A homomorphism from  $\mathbb{E}[\ell] \rightarrow  \mathbb{E}[\ell]$ is represented as a $2 \times 2$ matrix (the points of $\mathbb{E}[\ell]$ are "$\ell$-torsion points") (page 233)
If the number points on a curve satisifies $ \#\mathbb{E}(\mathbb{F}_p) = p + 1 - a$, then the Frobenius endomorphism $\phi_q$ satisfies $\phi_q^2 - a \phi_q + q = 0$ (page 234).

So, the Frobenius endomorphism acting on the $\ell$-torsion, $\phi_{q;\ell}$ can be represented as a matrix:

$$ \phi_{q;\ell} = \begin{pmatrix}
\lambda & b \\
0 & \mu \\
\end{pmatrix}$$

Its characteristic polynomial is

$$ \begin{vmatrix}
\lambda - T & b \\
0 & \mu - T \\
\end{vmatrix} = (T-\mu)(T-\lambda) \equiv 0 \bmod \ell$$

So a root $\lambda$ here satisfies a subgroup of $\mathbb{E}[\ell]$, $C$, such that for all the points in $C$, $\phi(P) = \lambda P$. Raising $\phi_q$ to some $r$ power will just give you another eigenvalue equation, say $\phi_q^r(P) = \kappa P$. From Velu's formulas, we can define an isogeny such that $C$ is the kernel of the isogeny, and $\phi_q^r$ just permutes all the coordinates of points in $C$, leaving the parameters of the equation for $\mathbb{E}'$ alone. That means the $j$-invariant of $\mathbb{E}'$ is left alone too.


Hash coordinates (back-end) without the client (front-end) knowing the coordinates, but to be able to guess them So I have a set of coordinates and I will hash these with a random salt with SHA256.
Coordinate range is 0,100.
salt = abc
[1, 5] = "sZv6eqPT9bqGiXbjvO8yrb4wuFjl0Z1CwSHdnIgGqEI="
[3, 4] = "8XgDJ/rrDELExVflBfDOLjqV5SB//8urxN5I6hxK9Mo="
[6, 3] = "FTzCfctBaBKp/wmopgMw7YFRpo1z2p6/IdHVujFliGs="
[1, 6] = "t2WE+ba8pt0ZEo0uW3uQH9FpI94tPVaICbctcl0YPtU="
[6, 3] = "FTzCfctBaBKp/wmopgMw7YFRpo1z2p6/IdHVujFliGs="

Input format is "{x},{y}".
Pastebin with C# code I used to generate this example: https://pastebin.com/yyMiYApc

So we have a back-end where we generate a list of hashed coordinates using a salt that just got generated. The idea was to send the hashed coordinates and the salt to the front-end. So they can verify a right coordinate using the same algorithm. If the generated hash in the front-end is like any of the hashes from the back-end, the coordinate is right. They have 20 attempts to guess all coordinates from the front-end. The idea was that the front-end would call the back-end with their coordinate and their assumption, the back-end would then verify their assumption and save it in the database. If they give faulty input we would ban / strike a user because of cheating.
We are creating a competitive guess game and we can't have 500ms delay from the back-end be a problem, so that is why we are letting the front-end make an assumption and let the back-end make the actual decision. Basically to remove input lag in UI.
This was a solid plan until we forgot that any client can decide to not call the back-end after they've verified a coordinate on the front-end. Thus making the number of maximum attempts redundant.
For example any client could brute-force all 10,000 possible coordinates and check what 5 are the right coordinates. Then call the verify in the back-end 5x and win the game.
We have real prizes for this game and want to make cheating impossible and at the same time remove the delay of calling a back-end to verify your answer.
I am in no way a cryptography expert. Is there any way cryptography could help us? And if yes, could you point us in the right direction? If this problem can't be sealed completely how could we make it very hard for the client to cheat?
Feel free to edit this question so cryptography experts understand it better!

Edit 1:
The reason the send the salt right now to the front-end is because the front-end needs to know whenever they have a right coordinate. So, like I explained before. There is no time to wait for the back-end to give feedback, because that would be too much input lag.
Whenever someone guessed an coordinate they should know this instantly. And not at the end of the game.

You should not send salt to the front end. Send only the hash. After the "game" completed, e.g. after the front end has done 20 attempts you named, you should present the right answer and the salt. Thus every participant can check that the hash you presented at the beginning really matches the message and the salt.
And the cryptographic properties of SHA-256 guarantee that you cannot deny the right answer, because there is no easy way to find another message (coordinates in your case) and another salt, that produce the same hash. In your example, if you publish hash sZv6eqPT9bqGiXbjvO8yrb4wuFjl0Z1CwSHdnIgGqEI=, then everyone can be sure that you cannot find any other salt and any other message (coordinates) that produce the same hash.


Allow message inspection by proxy without ability to modify it My client creates a private/public key pair and sends it securely to a server (the "public" key is not really public, only the server is supposed to know it). The server then sends messages to the client, encrypted using the public key.

Now a customer wants to add a proxy that inspects these messages. Obviously the proxy cannot inspect the encrypted message, only the client. Can anyone think of a way to allow the proxy to verify that the encrypted message is what it is supposed to be, without being able to replace it with it's own encrypted message? We assume that traffic from server to proxy is secure (both are on the same machine).

(We are willing to modify what the server sends out. I am writing the client, and there's no way I'll hand the private key to anyone, and the server devs are very unwilling to pass the public key to anyone. Otherwise they could pass the public key and the plaintext message to the proxy and let it create the encrypted message itself).

Can anyone think of a way to allow the proxy to verify that the encrypted message is what it is supposed to be, without being able to replace it with it's own encrypted message?"

The standard solution is for the server to have its own public/private signature keypair.  The server's public key is given to the proxy and the client in some secure way (that is, in a way that the proxy knows that it is the correct key - we don't care about privacy here).  Then, when the server generates an encrypted message, the server signs it using his private key, and the proxy (who has the server's public key) verify the signature (using his copy of the public key).  Then, when the client gets the encrypted message, he also verifies the signature (to check that the proxy has not modified the message).

You may also need to include something to allow the client to detect if the proxy replaced an encrypted message with a previous encrypted signed message (which would pass the signature check); perhaps a time stamp or a sequence number that always increases.

Can this work in your scenario?


Getting a Keeloq manufacturer key I have seen a lot of articles and research papers about breaking the Keeloq algorithm. My understanding is that the hardest part is getting the 64 bit manufacturer key. Some methods use crypto-analysis and some use power analysis to get the key. Once the manufacturer - and other parameters - have been obtained it is trivial to create an arbitrary number of remotes to your garage, car, or whatever.

I have two questions about that :

Do manufacturers in general (cars or garages) still use Keeloq as their algorithm after these attacks and vulnerabilities have been exposed?
Or are other algorithms used, for instance manufacturer specific ones?
If the manufacturer key is not public and is stored in the receiver, how do some Chinese manufacturers sell some car remotes (specifically some older models)? Do the original manufacturers publish their keys after the car is out of production? Do the keys get leaked?

Because honestly I don't think Chinese mass production companies would go through all the trouble of breaking the cipher to get the key.

There have been several attacks against Keeloq.  I cannot speak to the specific algorithm changes through the years to make it stronger against brute force; however, I am knowledgable in the hardware changes as of discussions I was privy to in 2009.   The Keeloq ICs were changed shortly after the power attacks came out to make them immune from power attacks through the use of dual rail encoding.  At the time, the core of the Keeloq ICs are based on the PIC12, which are very simple and could allow power attacks if you could instruction step them. Through dual rail encoding, you use the same amount of power in all data cases, but not necessarily instruction cases.   Even though the PIC12s are only one-time-programmable, you can still hook them onto a debugger to single-step them.  If you are interested on how this could be done, see if you can get the course notes from Tom Collins for his lab.


Practical brute-force attack on 128 bit encryption In brute-force attack calculations cryptographers say we should assume an attacker will find the key after $2^{(n/2)}$ tries. If n=128, then n/2=64. We know that this is practical (A 64 bit key is already found via brute-force by distributed.net). Then why 128 bit encryption is considered practically secure at present?

BTW, is birthday attack somehow relevant here? I think it is believed that 128 bit hashes are really not secure enough because of the birthday attack. So isn't that fact extendable to encryption too?

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$).

It is required to only search half of the key space on average (if average is the correct term here, this is not something you are likely to repeat), but that means that the search should cover $2^{128}/2 = 2^{128-1} = 2^{127}$ on average.

So in the end it comes down to the difference between $2^{128/2}$ as used by the birthday attack (which is not applicable) and $2^{128} / 2$ which is the average amount of tries required by a brute force attack.

For an indication how the time scales with the number of bits, take a look at the stats of the RC5 72 bit challenge and compare it with the stats of the RC5 64 bit challenge that you probably referred to.

Birthday attacks are indeed not applicable to encryption. Collision finding - for which the Birthday attacks are used - are in itself not directly applicable to attacks on ciphers.


Time efficiency of Bitcoin Multi-signature Vs. threshold signature I read this paper (Securing Bitcoin wallets via a new DSA/ECDSA threshold signature scheme) that illustrated that threshold signature is the best solution to avoid single point of failure

but I think multi-sig is better than threshold signature in term of time  efficiency because it is non-interactive algorithm and each party can sign separately not like threshold

I am wondering if that correct inference or not ?

There are some possible advantages to threshold signing. First, it enables a more flexible setting where the key can be divided into $n$ parts and any subset of $t$ can be used to sign. Second, you can go from holding a single key in one place to distributing it and back without making any changes. Third, you can achieve a type of proactive security by generating a new resharing of the signing key at frequent intervals.

However, you are right that for the very basic usage, multi-sigs will be much simpler. (I don't think that efficiency is a huge issue here since you typically wouldn't be doing a huge number of transactions all the time. Bitcoin isn't good for many fast transactions.)


Recovery Passphrase Collission for BIP-39 and BIP-44 Referring to the standards of [BIP-39] and [BIP-44]: a 'master password' consisting of 12 words uniformly selected from a 2048-word dictionary corresponds to 128 bits of entropy, that is then used as a seed for the generation of keypairs in many wallet implementations.
While not contesting the sufficiency of the offered security, what stops an attacker from iterating over such seeds just to check balances on other's wallets? What would the threat scenario/attacker model be called?
Obligatory disclaimer: This question does not suggest, encourage or condone any illegal ulterior motive.

128-bit entropy simply means that we have $2^{128}$ different values to search, which is similar to 128-bit security. For a single target that is impossible since even the collaborative powers of Bitcoin Miners can reach $\approx 2^{92}$ in a year. Therefore one needs $2^{35}$ years to find the correct password. The iteration of PBKDF2 is 2048 so, we need to multiply $2^{35}$ with $2^{11}$ that makes $2^{46}$ years if we assume that SHA2d running time is equal to PBKDF2.
In the case of finding multi-password attack, with parallel versions of Oechslin's rainbow tables, the expected cost of finding a password from $t$ targets is $2^{128}/t$. Now assume that you have a billion of targets. Then, you will be able to find the first password much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This can be achievable with supercomputers.
Conclusion: Using 128-bit entropy is not secure in multi-target attack case. The users should concentrate on password settings with 256-bit entropy.

Note 1: The title includes the word collision, however, a collision has nothing to do with finding a password of a user. A collision is finding two pairs of passwords such that after PBKDF2 is applied the result will be the same. This has cost $2^{64}$ with 50% probability of success. The pre-image attack is the attack for passwords with a cost of $2^{128}$ is the setup of the question.
Note 2: A detailed entropy calculations of Bip39 in this answer.


How does the simulator of the special-honest verifier zero-knowledge property works? I’m a bit confused about what the simulator of the special-honest verifier zero-knowledge property of a $\Sigma$-protocol is supposed/allowed to do and how to prove that it is indeed efficient (i.e. it runs in a time polynomial in the security parameter).

A 3-move protocol between a prover $P$ and a verifier $V$ is said to be Honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on input $x$, it outputs an accepting conversation of the form $(a,e,z)$, with the same probability distribution as conversations between the honest $P, V$ on input $x$.

In order to prove this property, we need to define a simulator, which is usually given black-box access to a honest $V$ and has full control over all $V$'s input tapes (including its random tape). I've found in many papers the following sequence of steps:

 1. The simulator starts the verifier V: the verifier is given the common input x,
    some auxiliary input and also the random input bits.

 2. To simulate one iteration, the simulator executes the following loop:

  2a) Draws a uniformly random challenge e, uniformly random response z,
      then computes the commitment a (using e and z), and finally sends the commitment
      to the verifier V.

  2b) Gets the challenge e' from V. If e=e', then it outputs (a,e,z) and exits the loop.
      Otherwise, it resets V to its state right after step 1 and the simulator starts
      from step (2a) again.

It seems to me that the random bits of $V$ are chosen in step 1 and kept fixed for the rest of the simulation, so the verifier works deterministically and he will always send the same challenge $e^{\prime}$ after step 1.

If this is so, I wonder, in the case of a fail run, why is the simulator drawing a brand new challenge, response, etc. all over again in step (2a)? Isn't the simulator allowed to use the challenge it just saw coming from the verifier ($e^{\prime}$) as its own new guess of the verifier's challenge?

My second question is:
How do we proof now that the simulator is efficient, that is, that the simulator will only need to run a time polynomial in the security parameter before being able to produce an accepting transcript with the correct distribution? According to the above reasoning, and assuming that the simulator is indeed allowed to use the verifier's challenge $e^{\prime}$ as its new guess of the challenge, wouldn't the simulator always need two runs at most, to generate a valid simulated transcript?

I hope these questions make sense.

EDIT:

Some days after I first asked the question, and after having seen that I didn’t get any answer, I’ve noticed a problem with the question I had raised. The sequence of steps I described are not the ones that a simulator would do in order to prove the property of Special-honest verifier zero-knowledge (otherwise the simulator would receive a challenge as input), but to prove the Honest verifier zero-knowledge property (without the “special” part). Therefore, I've edited the question so as to talk about the property of Honest Verifier Zero-Knowledge.

Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property.

Your description of HVZK is essentially correct, but with the following clarifications:

  A 3-move protocol between a prover P and a verifier V for a language $L$ is said to be honest verifier zero-knowledge if there exists a polynomial-time simulator $M$, which on any input $x$ in the language $L$, outputs a transcript $(a,e,z)$ having the same probability distribution as a conversation between the honest $P,V$ on input $x$.

A key point here is that the simulator's transcript must look like a real conversation between the honest prover and verifier.  Typically, this makes simulation very straightforward, because in most protocols the honest verifier is defined to make a uniformly random challenge $e$ that is independent of the prover's initial message $a$.  So the simulator does not need "black box" access to $V$ or its random tape, nor does it need to rewind $V$, because we know exactly how the honest $V$ operates.  Instead, a typical simulator for proving HVZK will just first choose the challenge $e$ uniformly at random, then generate the prover's messages $a,z$ in a manner consistent with that challenge, and output the transcript straightaway (no rewinding).  It's usually easy to prove that $(a,e,z)$ has the appropriate distribution, thanks to the independence of $a$ and $e$ in the real protocol.

By contrast, the strategy presented in steps 1-2(b) represents a typical (black-box) simulator for proving plain-old ("possibly malicious verifier") ZK.  Here we don't know the verifier $V^*$'s strategy for choosing its challenge $e^*$; in particular, it might choose $e^*$ non-uniformly, or in a way that depends on the prover's first message.  So we usually define a simulator $M$ that first "guesses" an $e$ in advance and prepares $a,z$ to work for that value of $e$, then sends $a$ to $V^*$ to receive some $e^*$, and checks whether $e=e^*$.  If so, $M$ finishes the transcript successfully, otherwise it throws everything away and starts over.

To answer your first question, the reason $M$ starts over from scratch is that we don't know how $V^*$ chooses its $e^*$ -- maybe $e^*$ has some crazy dependence on the prover's first message $a$.  In such a case, changing $a$ could lead to an entirely different challenge $e^*$ (even if $V^*$'s coins remain fixed).

To answer your second question, one can typically design $M$ so that when $x \in L$, the value $a$ that $M$ gives to $V^*$ reveals no information about which challenge $M$ is prepared to answer.  So if, e.g., $e$ is a uniformly random bit, the probability that $e^*=e$ is exactly 1/2, and so $M$ succeeds after 2 attempts in expectation.  This means that its expected runtime is polynomial.  (Alternatively, one get a truly polynomial-time simulator that outputs a transcript that is statistically close to a real one between $P$ and $V^*$ -- the difference being that in the negligibly small chance that $M$ fails after many attempts, it just outputs a junk transcript.)


Is there any hardware available to calculate single sha256 hash? I'm looking for a hardware that can generate sha256 hash of the input.

Sure, designs for such chips are available on the internet (e.g. http://www.cast-inc.com/ip-cores/encryption/sha-256/cast_sha256.pdf) but you would probably have to integrate them yourself into a hardware module, which is going to be expensive and time-consuming. You will find those integrated in things like HSMs and cryptographic accelerators as well as mining modules (e.g. bitcoin miners), but it's unlikely you will find a fast, cheap, standalone IC specifically dedicated to computing SHA-256 hashes from an arbitrary input.

The reason is simple: bandwidth. Take bitcoin miners for instance, very little bandwidth is required, since the device can mine autonomously without a constant stream of data from the host (it's just searching for a block that hashes to a specific number of zeroes, so it can just hash an incrementing counter, for instance). But a general purpose SHA-256 hashing device would need to be fed data from the host, meaning it can only run as fast as the communication interface, which is necessarily going to be limited to a few gigabits per second, maybe a few tens of gigabits per second in the best case.

If this device is to communicate with a computer, USB is a no-go as it is too slow (it wouldn't be much faster, if at all, than just running SHA-256 on all cores of a modern CPU, for instance). Probably your best bet is to leverage PCI express 3, or maybe Thunderbolt, that would be fast enough to make it worth it. So you could make a "SHA-256 card" that is designed or at least programmed to compute SHA-256 hashes, and plug it into a PCI express port to start sending it data.

Guess what: such a device already exists, and is called a GPU. This is, by very, very far, the most cost effective hardware to perform SHA-256 hashes over arbitrary inputs, in terms of raw performance. It's also commodity hardware, which helps, and is quite straightforward to program for, as opposed to FPGAs. It's not designed only for hash calculations, but it's as close as you're going to get to that if you don't want to start doing some serious (and expensive) R&D with high-performance, expensive FPGAs and ASICs.


Choices of $q$ and $f$ for RLWE-based constructions I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE.
However, I have a series of questions about this setting.
First, Ring-LWE-based constructions consider the polynomial ring $R_q = \mathbb{Z}_q[x]/(f(x))$, for some polynomial $f$ and some integer $q$. I've seen the choice $f(x) =x^{2^m} + 1$ and $q$ a prime such that $q\equiv 1\bmod 2^{m+1}$.

  Why is this choice of parameters relevant?

I understand that arithmetic in this ring is cheaper because of NTT, but, how does the CRT fit into the picture? Does it help the fact that the ring splits completely?

Also, I have a vague memory of some text that said that CRT is useful because instead of working with large modulus one can work with multiple smaller modulus.
I also heard that CRT is useful since you can do "parallel" computations.

  How does CRT fit into the RLWE picture?

Finally,

  Why does $q$ need to be prime?

Are there some works that consider a composite $q$?

Thanks! Any pointers or comments are more than welcome.

Why use $f(x) = x^{2^n} + 1$?

This is a very special polynomial called a "cyclotomic" polynomial. Cyclotomic polynomials are very interesting, and I recommend reading up on them separately  (wikipedia). One very useful property is that the $m^{th}$ cyclotomic polynomial has roots that are all the $m^{th}$ primitive roots of unity. For any $n \geq 1$, the polynomial $f(x) = x^{2^n} + 1$ is the $(2^{n+1})^{th}$ cyclotomic. Power-of-two cyclotomics are even more convenient because they allow for much faster NTT algorithms (see Cooley-Turkey style optimizations, where having a power-of-two length is important for the recursive structure of the algorithm). Here is a nice paper on NTT optimizations.

Where does CRT come in?

This will also answer your third question, since $q$ need not be prime, and this is necessary to implement CRT optimizations. The problem that arises with RLWE-based secure computations is that the modulus $q$ must grow to be much larger than the typical machine word, which is usually 64 bits. Since $q$ need not be prime, we can use a modulus $q$ that is the product of many small primes $q = \prod_{i=0}^{\ell-1} q_i$. CRT makes use of the following isomorphism:
$$ \mathbb{Z}_q \cong \mathbb{Z}_{q_0} \otimes \mathbb{Z}_{q_1} \otimes \ldots \otimes \mathbb{Z}_{q_{\ell-1}} $$
This is what allows the implementations to work with each $q_i$ separately instead of the full $q$. This also allows for parallelization. For more information on this isomorphism and how it's useful in RLWE implementation, I recommend this paper.


How to evaluate the security of a certain encryption method? I've been slinging code for a while now, but relatively new to encryption/security. What should I look for when evaluating an encryption method in the wild?

For example, the Standard File protocol supports E2E encryption. It's implemented here: https://github.com/standardnotes/web/blob/6fd5719/app/assets/javascripts/app/services/encryption/crypto.js

To my untrained eyes, that looks reasonably secure. How could I spot red flags? For example, is splitting a key in thirds a good idea?

I'm not asking about evaluating this specific library, rather, patterns or resources I can use to determine security. One idea that comes to mind is placing a public bounty as a challenge to break the encryption. Telegram did this with a $300k bounty.

How could I spot red flags?

The red flag is actually the entire red zone (like trees in the forrest...). If there is code for encryption at all, you better throw it away unless it's some proper library from a source with good reputation for exactly this kind of thing.

It is something different, if they use a cryptographic library properly, that can be achieved by non-experts. But implementation of actual encryption ... the chances of a crucial error are immense.

  For example, the Standard File protocol supports E2E ...

If you look at the homepage, the section developers is only listed in the menu, there is no matching content. However, on the positive site they don't actually implement encryption, they use CryptoJS as library.

  For example, is splitting a key in thirds a good idea?

In general: Actually it doesn't make any sense, because you should create keys fitting to their task and why would someoen want to split a key in a meaningless way? If the goal was to split it securely in the sense of a secret sharing scheme (e.g. that you can only reassemble any information with both halves), that's something totally different.

  Telegram did this with a $300k bounty.

The Telegram "challenge" is bogus anyway. It is basically "I think of a number, give you no information, and if you can guess it, you win".

That is not how cryptanalysis works, that is not how security works. By doing that, they already proved that they don't understand much about these fields.

Here are a few articles about that:

Why You Should Stop Using Telegram Right Now
Related is this older article by Bruce Schneier on crypto contests


Discrete log analog of ECM factoring algorithm? Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.

Is there an analog of the elliptic curve (ECM) factoring algorithm, but for discrete logs?  Something that uses similar ideas, but can be used to compute discrete logs modulo $p$?

Similar algorithms for factoring and discrete log are limited to pollard rho and sieve methods using a factor base. There are other factoring methods such as square forms, p+1 and ECM which as far as I know don't have logarithm-in-$F_p$-finding analogues. The factoring methods rely (explicitly for rho and implicitly for sieve methods) on treating a ring like a field, trying to measure the order of elements and waiting for the process to break down. Calculating a discrete log is a very similar process but it works correctly.
The other way to answer your question is yes there is a logarithm-finding analogue of ECM but it finds elliptic-curve logarithms. Similarly,the logarithm-finding analogue of Williams' p+1 method finds logarithms in a quadratic field. Not what you had in mind I guess.


General-purpose non-interactive multi-party computation protocol Most of general purpose multi-party computation protocols are highly interactive.
Especially the ones with Shamir's secret scheme, as there is a degree reduction step in multiplication that needs the parties to interact with each other.

For example, say a client (trusted dealer) distributes the secret among several servers via secure channels, and the client also provides inputs to all the servers needed for secure function evaluation. Now the servers should evaluate a function on their own, they cannot talk to each other. At the end, the client receives all the partial results from different servers (via secure channels) and constructs the complete result locally.

There are non-interactive and robust threshold decryption protocols of RSA which are specialized multi party protocols. But are there any general-purpose non-interactive multi-party computation protocols? Or is it an open problem ?

It depends on what you mean by interaction.

Some protocols for secure multiparty computation, e.g. those based on Shamir secret sharings and the GMW protocol, require the servers to communicate a lot during the computation.

In other protocols, such as those based on Yao's garbled circuits (e.g. Fairplay MP), the interaction between servers is reduced in that the servers only need to communicate during a constant number of rounds, that is, a number of rounds that is independent of the size of the function they compute. But still, a lot of data traffic between the servers are needed during these rounds.

Some work has been done to further reduce the interaction required by secure multiparty computation. See for example this paper: Secure Computation on the Web: Computing without Simultaneous Interaction. This is in some sense non-interactive secure multiparty computation, but unfortunately the paper shows that it only works for a limited class of functions.


Discrete logarithm key sizes for very short term usage We have this special use case that our session typically only last for less than 30 minutes, no more than 1 hour at most, after the session finished, the information protected does not matter. Each time a new session start, a new group (p, q, g, k) choose randomly, where p=k*q + 1, g is the generator of subgroup q, p, q are both large prime, k and q coprime; I known if sizeof p = 1024, sizeof q = 160 is good enough, but it's a bit slow and consume too much power on smartphone, since our session only live very short term, I'd like to known if its safe to choose shorter group size, say p=512, q=160, or even shorter p=256, q=112?

any comments would be appreciated

If:

You're okay with the encrypted information being easily decrypted after the session
You have a guarantee that the session won't be very long
You use random and unpredictable safe primes $p$ every session

I think it should, theoretically, be okay to use slightly smaller bit lengths for $p$.

That said, in practice it is probably a bad idea, and it's better to use ECC as @CurveEnthusiast mentioned. Generating safe DH primes is non-trivial, judging by how many implementations screw it up. And in the case of smaller groups, it is absolutely crucial that you generate random and unpredictable safe primes for every session (otherwise, someone can simply do a large amount of precomputation on the group, and crack connections using that group very, very quickly -- see Logjam).

What is your threat model? How much computing power does your attacker have at his disposal?

For reference, the authors of the Logjam attack in 2015 cracked several 512 bit groups in a week. They estimated that this could be optimized by a factor of 3, and they deliberately spent more time on precomputation. How fast do you think a state actor could break a 512 bit key exchange? It's not inconceivable to think that with a huge amount of computation power, and some very clever optimizations, a state-level adversary could do it in a few hours.

In short, it's not worth the risk. You run a big risk of improperly generating the weaker DH groups. You run another big risk of reusing the weaker DH groups, or having them be predictable, thereby opening yourself up to precomputation attacks.

Try ECC curves instead, and see if they don't alleviate your time/power consumption issues.


Proving collision resistance of a hash function? Let $f$, $g$, and $h$ be hash functions that each map binary strings
  of length $2n$ to binary strings of length $n$. Suppose that $h(x) =
 f(g(x)||g(x))$.  Prove that if $f$ and $g$ are collision resistant
  then $h$ is also collision resistant.

This question was asked on an earlier assignment and my professor had taken it up in class using proof by contrapositive.  I am expecting a question like this to show up on our final but I have forgotten how he answered it.  Could anyone off some insight into how I can answer this?

Recall that randomly chosen functions, used to model good hash functions, are collision resistant if we need on the order of $2^{n/2}$ queries in order to discover a collision with success probability a constant bounded away from zero.

Proof by contrapositive:

Assume $h$ is NOT collision resistant. Then we can find such collisions much faster than specified above, i.e., we can find $x\neq x'$ $x,x' \in \{0,1\}^{2n}$ with $h(x)=h(x')$. There are two possibilites.

In the first case $g(x)=g(x')$, in which case any function $f$ would yield a collision in $h$.

If on the other hand, $g$ is collision resistant and thus $g(x)\neq g(x')$, we must now have  $f(g(x) || g(x)) = f(g(x') || g(x'))$ which implies that $f$ is not collision resistant since it is giving a collision to distinct inputs.


How many bits can be safely extracted from the BBS generator at each step? The Blum-Blum-Shub generator is a deterministic Pseudo-Random Bit Generator with security reducible to that of integer factorization.

Setup: Secretly chose random primes $P$, $Q$, with $P\equiv Q\equiv 3\pmod4$, and compute $N=P\cdot Q$. Secretly chose a random seed $x_0$ in $[1\dots n-1]$ with $\gcd(x_0,N)=1$.

Use: To generate the $i$-th bit, compute $x_i=x_{i-1}^2\bmod N$, and output the low-order bit of $x_i$.

In that definition, BBS produce 1 bit per iteration. For a given $N$, how much can this be improved while maintaining security demonstrably reducible to factorization of $N$ (or determining quadratic residuosity $\bmod N$)?

This is discussed in Vazirani & Vazirani: Efficient and Secure Pseudo-Random Number Generation, with proof that the low 2 bits can be safely extracted, and even (if I get it correctly) $\log n$ bits where $n=\lg_2 N$. However the authors "notice that in all the proofs, $\log n$ can be replaced by $c\cdot\log n$, for any constant $c$". Note 5.41 in the HAC gives it as $c\cdot\lg_2n$ bits and warns that "for a modulus $N$ of a fixed bitlength (eg. $n=$1024 bits), an explicit range of values of $c$ for which the resulting generator is cryptographically secure under the intractability assumption of the integer factorization problem has not been determined".

The direct answer to your question is in Koblitz and Menezes (Indocrypt 2006).
They pointed out that, for practical parameters, one can produce only $1$ bit per iteration if one wants provable security. See Section 6 of the paper for the detail.

Additional note:
if you can change the assumption from the hardness of integer factoring, then you can produce more and more.
I found an example in Steinfeld, Pieprzyk, and Wang “On the Provable Security of an Efficient RSA-Based Pseudorandom Generator” (ASIACRYPT 2006).


Does IND-CPA imply PRF? It is well-known that a pseudorandom function (PRF) can be used to build a CPA-secure symmetric cryptosystem. My question: is PRF necessary for this, i.e., can one show something like "If there exists an IND-CPA scheme then there exist PRF?"

If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence of articles have shown how to construct pseudorandom generators out of OWFs (culminating with this paper). By the GGM construction, pseudorandom generators can be used to construct PRFs. Therefore, IND-CPA symmetric encryption implies PRFs.


Given occasional LFSR samples can the next sample be computed? Suppose I have access to an LFSR generator output used in a radio communications system, with the LFSR being used to authenticate devices. The system cycles an internal unknown length LFSR (greater than 32 bits) an unknown but constant number of times and returns the truncated upper 32 bits, with the lower bits being unknown.

I do not know the starting condition or the polynomial, but I can read the truncated output from this system as it transmits. Using this data alone, can I predict the next output using an algorithm such as Berlekamp-Massey algorithm?

I know that Berlekamp-Massey can solve given 2n captured bits, but do these have to be completely consecutive, or can they be a scattered "picture" of the output? Do I need to know the size of the generator to use Berlekamp-Massey?

I'm thinking of implementing this in a communications system: power consumption and complexity is key here, and an LFSR uses considerably less power and flash memory than a full AES or SHA authentication system, but I'm not sure if it will be easy to predict. (The idea is the receiver will refuse to acknowledge packets an incorrect LFSR, preventing the device being "impersonated".)

It is very easy to predict and should not be used as a main cryptographic component on its own.

Firstly, many $k-$decimations $s_{kt}$ of LFSR sequences (those with $gcd(k,2^n-1)=1$) are shifted LFSR sequences themselves so this can be used for prediction.

If you can find a template $T=\{0,t_1,\ldots,t_{n-1}\}$ (with $0<t_1<t_2<\cdots<t_{n-1}$ such that the samples you have of the LFSR sequence $(s_t)$ cover $n+1$ shifts of this template you can set up a linear system and solve for the recurrence. In fact assuming $n=3$ one can (Berlekamp Massey is more efficient of course, this would need Gaussian elimination) set up the system

$$c_0 x_t + c_1 x_{t+1} + c_2 x_{t+2}=x_{t+3}\\
c_0 x_{t+1} + c_1 x_{t+2} + c_2 x_{t+3}=x_{t+4}\\
c_0 x_{t+2} + c_1 x_{t+3} + c_2 x_{t+4}=x_{t+5}$$

and solve for the LFSR coefficients $c_i$. For the template I mentioned, a similar system needs to be solved. This case is the template $T=\{0,1,2\}$ with shifts also $\{0,1,2\}.$


Estimating random number entropy for input into 256 bit hash Assuming a random number generation process outputs lots of numbers between 0-9. First I gathered up a bunch of the numbers, converted them to binary and created a bitmap.

Not so random as you can see! That must be why you shouldn't just use raw integers as random numbers in a computer program. Look what happens when the numbers are converted to binary:

0  00110000
1  00110001
2  00110010
3  00110011
4  00110100
5  00110101
6  00110110
7  00110111
8  00111000
9  00111001

As you can see the first 4 bits are always 0011 which is not very random. Even looking at the 5th bit that is not very random either. From 0-7 it is always a 0 bit and only for 8 and 9 is it a 1 bit.

What about the last 3 bits are they random?

0  000
1  001
2  010
3  011
4  100
5  101
6  110
7  111
8  000
9  001

It looks like there is all possible combinations of the 3 bits in the numbers 0-7 inclusive. However 8 and 9 bits are duplicates of 1 and 2. Does that matter? Should the numbers 8 and 9 be thrown away to remove bias?

I think the plan might be to run all these raw integers through a cryptographic hash such as SHA 256 then use that as a key. However what is the correct amount of raw integers to feed into the hash to get a quality 256 bit output? I assume I need 256 bits of input to get a good 256 bit output, yes?

If I do some back-of-the-envelope calculations I come up with:

3 bits of entropy per 8 bit (1 byte) number
256/3 = 85.33

This means I need to collect 85~ raw integers (682.67 bits) and feed them into the 256 bit hash. Does that sound about right?

Or would it be better to get the last 3 bits from each number until I have 256 bits of entropy, then convert that to hexadecimal and run that through the crypto hash? I think I've only seen a crypto hash algorithm take hexadecimal or text as input...

It is a little unclear, how you transformed all your numbers... e.g. how did you interpret your decimal numbers "as binary" and "create a bitmap"? Then you look at the binary representation and guess what.... and they are just the numbers 0-9 in binary and added on an static number (no idea where that came from).

Things to consider:

Of course the numbers 0-9 do not have an integer sized entropy, this range is not of the form $2^{x}$. Actually it is $3.3219...$
If your numbers are uniform distributed over 0-9, then evaluation of fixed bits will result in a loss of entropy or a loss of uniformity (or both).
What is your actual goal? In the beginning you mention "in a computer program" and then later on "use that as a key". Random numbers serve a lot of purposes, and different tasks require different properties (and thus different PRNGs).

How to solve your problem?

Let's assume  you want 256 bit of entropy and your RNG is good enough to create cryptographic keys (if you don't know the difference, read up on this).
If you do not want to "throw away" entropy, you can just calculate a large random number in the decimal system and use your RNG (let's call this $\Re$) for each digit. This way it is uniform distributed. You can do this e.g. by this formula: $r = \sum_{k=0}^{t}10^k\cdot\Re $. You have to choose $t$ large enough, that is covers at least the range from $0$ to $2^{256}-1$, which means $t \ge 77$. But now you $r$ is still uniform distributed in the "wrong range", because it can be greater than $2^{256}$.
Now you can decide if you want to start over if the result is higher than that, this will result in a uniform distribution in the "correct range" since you don't change the distribution by favoring some values over others... you just start fresh for the wrong results.
Or you can increase $t$ even more, and then calculate $r' = r \text{ mod }2^{256}$. This does not result in a perfect uniform distribution, but if the range for $r$ is a lot larger than $r'$, it is really close to uniform.
Otherwise, you can also do the rejection sampling at the bit level (That's throwing away some results, so that others are still uniform to each other): Draw a number from 0 to 9 and if it is 8 or 9, ignore it and draw again. Now you can use the binary representation of the numbers 0-7 as 3 bit for the long binary result. Repeat this and concatenate the 3-bit blocks.

You can even combine these techniques to optimize the number of rejected results, but that's probably going too far, these simple solutions should work.

PS: Concerning your first conclusion

  That must be why you shouldn't just use raw integers as random numbers in a computer program.

That statement is just not true. RNGs usually run on integers, and there are different RNGs for different tasks. What else should you use as random numbers? Floating point numbers are much worse to handle than integers, and even harder to actually proof statistical properties Therefore, RNGs use integers, because they are better than anything else, but the properties depend on the actual RNG. For example linear congruential generators and similar constructions are REALLY fast and have a long period, but their randomness has poor quality due to a large correlation of sequential elements. Linear feedback shift registers offer randomness of higher quality, but it is also possible to predict the stream from a short sequence of outputs. For statistical purposes the Mersenne Twister offers probably the best performance and high quality randomness.

But for cryptography, you need other properties (check the first link in this post). For actual computer programs: You should use the implementations in the standard libraries for secure PRNGs, e.g. SecureRandom in java.

Anyway, hashing is usually done to have the one-way property, s.t. you can not compute back to the original message/object/input/... E.g. if you have hashed values, you can compare if two items are the same, but nothing else. If you have to guess this item, you can't.


Where does one store 3rd-party Public Keys So, I've just started looking at the subject of Cryptography and am working through Stephen Haunt's Practical Cryptography course on PluralSight but have a question that doesn't appear to be covered.

In the course, the Window's Key Container is used for encrypting and decrypting a message.

Now if I'm sending messages to myself, that's fine, but generally, if I talk to myself, the voices and I don't bother encrypting our messages.

If I'm sending messages to someone else then I need to encrypt the message using their Public Key, yes? So, assuming that they have sent it to me, where do I store it? Can I put it in a key store? Do I store it as a String of some kind? and if I do, am I supposed to keep it in a DB? The file system?

I've looked on here for answers to this question, but maybe it is so trivial that no one has thought to write down the answer for those of us who are hard of Thinking.

From a security point of view, you can store the public key wherever you want, as by definition it is public. This doesn't hold for the private key, which has to be store securely, as the security depends on it.
As pointed out by @fgrieu (in the comment below), the integrity of both public and private keys should be ensured. In other words, it should be ensured that no adversary can change the public keys. Therefore, you might consider also storing the public keys in a key store which should make it a lot harder for an adversary to tamper with it.

From an efficiency point of view, it really depends on what platform you are using. Of course you can store the public keys also in a key store (as a key store most likely offers some other useful functions). However, you can also just store the public keys in a database or the file system. Regarding the encoding (storing them as plaintext strings, hex strings or any other encoding) it again depends on your platform. You might have a look at this link.


Why is it not ideal to rely on interactive assumption to build PRF? I understood the meaning of interactive assumption from
What is the notion of an interactive assumption?
.
However, I am not sure why there exists a research field of constructing PRF
 from standard assumption.

What is the advantage of standard assumption over interactive model in general and especially for PRF?

The advantage of a non-interactive assumption is that you prove something in general . In contrast in an interactive assumption you prove a specific instantiation of the problem. Think a variety of DL problems like DDH. The game starts with the challenger choosing the challenge. The challenge is given to the adversary and then the later is trying to solve it. That means for any instance of the problem. In contrast in an interactive assumption there is a learning phase like in CPA proof whereby the adversary is learning: is asking queries to the encryption oracle. That being said the proof is specific for that interaction. In some sense it is weaker because you cannot predict if there is a craft query that will break the system.


Would this image steganography technique be effective at avoiding detection? I've observed that when you view only the LSB of an image it is typically random looking, but often has areas that correlate with the over all structure of the image. It's common for there to be large sections of the image that are solid 1s or 0s. There are often blocky patterns. Complete randomness of the LSB would therefor be a potential indicator that steganography is present.
I am considering a simple block based technique. Consider a grayscale image. Divide the image into 2x2 pixel blocks, LSB only. There are 16 possible permutations, which are grouped into sets of twos. Blocks that match the first set (four white pixels, or four black pixels) are ignored. Blocks that match the other seven sets will encode our ciphertext. One of two possible patterns is chosen based on the bit of the ciphertext we are storing. Optionally, we may look at neighboring blocks (up, down, left, right) and if they are of the four solid pixel variety then we also ignore this block. For color images you could do this separately for each color channel.
This would essentially only store bits of ciphertext in parts of the image that appear random. Every block that stores a bit of ciphertext is only ever replaced with a block that is a flipped version of itself, so the number of 1s and 0s always remains the same.
Can someone more mathematically inclined and familiar with steganography weigh in on how effective this approach might be?

On the one hand, I think that this could be considered a first step into the direction of adaptive steganography, because you do not use some blocks that you think that are easy to detect. In adaptive steganography we modify only the pixels of the image that are more difficult to model statistically and, consequently make the detection harder.
On the other hand, you use a $2\times 2$ block for hiding one bit so you are reducing the capacity. And for doing this, in some cases you need to make two changes! Two changes for hiding a bit is far from being optimal.
Currently steganography is much more advanced than this. You have cost functions that tell you which are appropriate zones of the image to hide information (the state of the art in spatial domain is the HILL [1] cost function), and matrix embedding techniques [4] that allows you to hide a lot of information modifying very few pixels. There is also a field that deals with Wet Paper Codes[2, 3], that makes possible reading a message without knowing which pixels have been modified. This gives you a lot of flexibility for building systems where you don't want to modify some kind of pixels.
[1]. A new cost function for spatial image steganography. Bin Li; Ming Wang; Jiwu Huang; Xiaolong Li. 2014 IEEE International Conference on Image Processing (ICIP), Paris, 2014, pp. 4206-4210.
https://projet.liris.cnrs.fr/imagine/pub/proceedings/ICIP-2014/Papers/1569891955.pdf
[2]. Writing on Wet Paper, J. Fridrich, M. Goljan, P. Lisonek, and D. Soukal, IEEE Trans. on Sig. Proc., Special Issue on Media Security, Eds. T. Kalker and P. Moulin, vol. 53, pp. 3923-3935, October 2005.
http://www.ws.binghamton.edu/fridrich/Research/WPC_TransactionsJournal1.pdf
[3]. Minimizing Embedding Impact in Steganography Using Trellis-Coded Quantization, J. Fridrich, T. Filler and J. Judas, Proc. SPIE, Electronic Imaging, Media Forensics and Security XII, San Jose, CA, January 17–21, pp. 05-01 - 05-14, 2010.
http://www.ws.binghamton.edu/fridrich/Research/tcq_v3.pdf
[4]. Steganography in Digital Media (Principles, Algorithms, and Applications). Cambridge University Press. 2009. ISBN: 9781139192903.


Are there any crypography schemes which rely on Graph Isomorphism not being in P? Are there any cryptography schemes having correctness relying on Graph Isomorphism not being in P?  If I should ask this question in the CS Theory area, I will migrate it.

Thanks.

There is an elegant example of zero knowledge proof for graph isomorphism. The prover sends a randomly relabled graph and the verifier requests mapping to one of the originals. It is a very simple to understand and prove zero knowledge proof. However I don't believe anyone ever used this for authentication or such.
Obviously we now know graph isomorphism isn't hard after all making all these not very useful.


Determining interval(s) containing the smallest prime $p$ of an RSA modulus? Are there any results that have determined interval(s) $$b\sqrt{n}<p\leq a\sqrt{n},$$ where $0<b<1$, $0<a\le 1$, and $p<q$ are primes such that $n=pq$,

thus allowing us to narrow the search for $p$?

Any such nontrivial intervals would be entirely up to the implementation generating the RSA key.  For example, when generating a 2048 bit RSA key, an implementation could generate a 512 bit $p$ and a 1536 bit $q$; such a modulus would work just as well in RSA as any other modulus; this gives us an $a \approx 2^{512}$.

However, while an implementation could do that, they never do; instead, they generally aim to keep $p$ and $q$ balanced; one advantage this has is that it allows the maximum speed-up by the CRT algorithm.

I've seen two different strategies in common use; if we assume $n$ is even, then to generate an $n$-bit RSA modulus, we often either:

Generate two random $n/2$ bit primes with the two high bits set (which ensures that, when $p$ and $q$ are multiplied together, yield a $n$-bit modulus, and not an $n-1$ bit.
Generate two random primes both from the range $(2^{(n-1)/2}, 2^{n/2})$, which yields the same effect, albeit in a slightly more mathematical way.

With the first strategy, we have $\sqrt{3/4}\sqrt{n} < p < \sqrt{n}$; in the second strategy, we have $\sqrt[4]{1/2}\sqrt{n} < p < \sqrt{n}$ (a slightly wider interval).

As I mentioned earlier, there's no requirement that any specific RSA implementation uses either strategy (unless they claim FIPS compliance; FIPS insists on the second strategy).

In addition, you appear to be interested in this to help in searching for factors of RSA modulii; for any RSA modulii that's even slightly secure, the interval is far too wide to make any such simple-minded search for factors feasible.


In elliptic curve cryptography, how is "A dot A" computed? I was just reading Ars Technica's primer on ECC. Somewhere near the middle of the second page, the author introduces the "dot" operation that takes an elliptic curve and two other known points, giving a third unique point.

However, the author then claims that A dot A equals B. That is, if the two first points are the same, it's possible to come up with a unique third intersecting point. How is this possible? Intuition tells me that there is an infinite number of possible intersections if the two first points are the same.

You are correct that a line through a single point can intersect the curve in many other points. But you don't choose just any line. You choose the tangent through $A$. And that line will intersect the curve in exactly one point (which usually isn't, but may actually be $A$).

It is an interesting and useful exercise to actually do these computations with the formulae. Choose an elliptic curve, choose a point (not with $y$-coordinate $0$), find the curve's tangent line, then compute the remaining intersection point. (This is easy. You have two equations $Y^2 = X^3 + aX + B$ and $Y=\alpha X + \beta$. Eliminating $Y$, you get a cubic equation in $X$ and you know a double zero, namely the $x$-coordinate of the point you are trying to double.)


How were the constants chosen in round 2 and 3 in MD4? Just reading Ron Rivest's explanation of MD4 the hash uses two round constants one $ \text{5A827999}$ on round $2$ and the other $\text{6ED9EBA1}$ on round $3$.
I think they are supposed to be hex representation of square root of $2$ and $3$. But $\sqrt{2} = 1.\text{6A09E667F} $ and
$\sqrt{3} = 1.\text{BB67AE858}$
which are very different from the the values given. Any ideas?

I've got the solution myself in here

It says

  SHA-1 was designed by NSA and uses the constants 5a827999, 6ed9eba1, 8f1bbcdc, and ca62c1d6. In case you haven't already noticed, these are hex representations of $2^{30}$ times the square roots of 2, 3, 5 and 10.


Secret Sharing Domain Questions all,
I have a very fundamental question on Secret Sharing schemes such as SPDZ families.
As far as I can see for now, SS schemes always assume a certain variable range. For example, suppose the bit length of the variable is $k=32$ and its underlying operational domain is in $p$ ($p$'s bit length is $l=128$), then, all secret values $x$ are shared within $[-2^{31},2^{31}-1]$.
But, when it comes to generate random numbers, I am a little confused. Say, I am trying to generate a Beaver's Triple, should I have $c=a\cdot b$, where all these numbers are shared within $[-2^{31},2^{31}-1]$, or should I have all these numbers shared under $p$. From the original paper itself, I cannot find the answer. Therefore, I want to ask here for some help and the insight why it should be this case. And should it be with the same case as ABY or any other frameworks?
Thanks for help and suggestions!

A secret-sharing scheme allows you to distribute a secret message among multiple parties. However, a fundamental question is how this message is represented. In many SS schemes, this message is an integer between $0$ and some maximum value $M-1$ (for unsigned values), and whenever you add secret-shared values, the addition happens modulo $M$.
Addition modulo a number is not very useful in applications, so one typically considers secret to be much smaller than the modulus in the scheme so that wrap-arounds do not occur. This is what happens in your example when you propose a large prime modulus and a much smaller size for the actual data.
However, what you have to understand here is that this difference in the sizes of the data and the modulus exists only to enable some applications, but the actual MPC protocol doesn't care about the sizes of the underlying data: It just assumes it is smaller than the modulus. This is very similar to programming: If you use data types that are 64-bits long, any wrap-around modulo $2^{64}$ when adding variables is the programmer's fault, since the program doesn't really care about this.
Given this, and to answer your concrete question, protocols usually consider the computation to be defined over certain domain, like integers modulo a prime $p$, and they don't really care about what data is fed to them. In particular, whenever you see something like "sample a random value", it typically means random in the whole domain, that is, random between $0$ and $p-1$ (for unsigned, although this is irrelevant). For the case of triples, this has to be the case, since these random values are used to mask the inputs to the multiplication gates, so they have to be chosen uniformly at random in the whole domain so that the reconstructed value leaks nothing about the sensitive inputs.


What are the rules for using AES-GCM correctly? When using AES-GCM I know that I am supposed to use a new initialization vector every time I call the AES-GCM algorithm with the same key. What are other rules must be followed to use AES-GCM correctly?
I am looking for a bullet point checklist with advice that I can follow as a  developer, and the consequence of ignoring the advice.
I am using the Java implementation of AES-GCM.

Rules or your obligations

Key generation: select a key uniform randomly, and keep it secret.

(Key,IV) Resue: An $(IV,Key)$ pair must never be used again.

Maximum file size: The recommended IV is 96 bits so 32 bit counter left. This means that the counter can count at most $2^{32}$. the first two are used so there is at most $2^{32}-2$ calls of CTR encryption. Therefore for an IV, one can encryption at most $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits. This is around $\approx 68$ gigabytes. You should stop way before, see more in advices section.

Check the authentication tag before decryption. If there is a mismatch, throw an error.

Tag size: use the recommended tag size 128-bit. You should not trim the tag size too much. For the full details of the tag security, see this nice posts;

Does GCM (or GHASH) only provide 64-bit security against forgeries?

GMAC vs HMAC in message forgery and bandwidth

Key size: Prefer 256 bit, though 128 bit AES is secure. In AES one will slow around %40 if uses 256 bit AES instead of 128-bit AES.

IV size: One can provide an IV longer than 96 bits, however, that will cause an additional GHASH call to convert into 96-bits.
$$\textbf{if } \operatorname{len}(IV) = 96 \textbf{ then } Y_0 = IV \mathbin\| 0^{31}1 \textbf{ else } Y_0 = \operatorname{GHASH}(H, \{\}, IV)$$
With larger One lost the counter/LFSR's deterministic IV generation. Stick to use 96 bits.

Advices

For IV generation, NIST suggests two types 800-38D

Deterministic Construction In a short manner use counter/LFSR to prevent IV reuse under the same key. One needs to store the last counter/stage to advance. During system failures, these values may not be recovered correctly, A combined mode half random, half counter/LFSR can eliminate this or start with a fresh key.
This counter should not be confused with the internal counter used in the CTR encryption.
The deterministic IV generation with an LFSR recommendation of the NIST is very effective in the case of a hardware implementation of the AES-GCM as pointed in this answer

RBG-based Construction RGB is a Random Bit Generator. In short from the NIST: The random field shall either consist of

an output string of r(i) bits from an approved RBG with a sufficient security strength, or
the result of applying the $r(i)$–bit incrementing function to the random field of the preceding IV for the given key

Random IV vs Sequential IV
AES-GCM best works 96 bit IV and when the IV is generated sequentially. If you choose random IV then due to the IV collisions under the same key, then the limit on the number of messages to encrypt under the same key is much smaller than sequential 96-bit IV.

Limit the message size gainst forgery: Put a limit to message size to eliminate the adversary's forgery advantage. It is linear in the maximum message size (not, e.g., the average): merely sending a single $2^{36}$-byte message makes the adversary's task four million times easier than if you limit all your messages to $2^{14}$

Limit the message size gainst DOS attack: Put a limit to message size to prevent Denial-of-Service by selecting the amount as the size of memory can an adversary reject before rejecting for forgery.

If you need to use AES-128; during the negotiation for the key agreement, it is better if the pair not only agrees on a key but also on a random initial counter. Then increment on it with a counter/LFSR.

Little deeper

(IV,key) reuse: This can lead to lost of confidentiality since the underlying encryption is performed by the CTR mode.
A CTR mode converts a block cipher into a stream cipher. Like all stream ciphers, if the keystream is reused crib-dragging technique can reveal the messages. Once the messages are removed the keystream is also revealed. However, this doesn't mean that AES is broken here. One still needs to execute a KPA attack and AES has known to be secure.
Reuse can also have catastrophic result of forgery.

Thanks to SqueamishOssifrage's comments and suggestions on the chat.


Is it not secure if we use weak passwords to protect exported PKCS #12 files with private keys? Consider a practical scenario as described in Microsoft's Expand Export a Certificate with the Private Key. We can see a certificate with private key can be exported as a PKCS #12 file, where the private key can be protected by a password (in Step 7).

Questions:

If one day this PKCS #12 file is stolen by a hacker, then, can he perform an offline dictioary attack to this file?
Step 5 in that article reads:

  In the Certificate Export Wizard, click Yes, export the private key. (This option will appear only if the private key is marked as exportable and you have access to the private key.)

How does this mechanism works? Is the (un-)exportability guaranteed by a cryptography algorithm (so that no one can change the property), or only by a software method (so that hackers can change the property)?

If one day this PKCS #12 file is stolen by a hacker, then, can he perform an offline dictioary attack to this file?

Yes, that's possible. The password is simply used to directly derive a symmetric key, which is used in turn to encrypt the private key.

  Is the (un-)exportability guaranteed by a cryptography algorithm (so that no one can change the property), or only by a software method (so that hackers can change the property)?

Generally it is just a bit set to 0 or 1 somewhere. Where and how it is stored depends on the Cryptographic Service Provider (CSP) and the implementation of the key container that contains the private key. If it and the private key are stored in a HSM or Smart Card, it may be tricky to change it.


Can we parallelize the Feistel Networks? Classic Feistel Networks and various types of FN's are sequential in nature. [1]has a good overview of different types. But is there a way we can do Feistel Networks in parallel and achieve good security bounds ?

Hoang, Viet Tung, and Phillip Rogaway. "On generalized Feistel
networks." Advances in Cryptology–CRYPTO 2010. Springer Berlin
Heidelberg, 2010. 613-630.

The standard way to make best advantage of parallelism is to use a parallelizable mode of operation.  For instance, counter mode (CTR mode) is highly parallelizable.  Parallelism at the level of the mode of operation is typically more effective and easier to implement than parallelism inside the block cipher.

The Feistel network approach to block ciphers is inherently sequential, so not a good candidate for parallelization.  If you wanted to do fine-grained parallelism inside the block cipher, you'd probably design your block cipher differently (e.g., a la Serpent and bitslice ciphers) -- but doing parallelism at the level of the mode of operation is typically even more effective.


RSA with modulus product of many primes I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $p$ and $q$ large prime numbers.
I guess the modulus $n=p_{1}p_{2}...p_{L}$ will be not a good idea, because one can use the Chinese Remainder Theorem to decrypt easily the message?

Can anybody explain how we deal with such moduli products of many primes?

Having more than two prime factors is supported by the PKCS#1 standard. This is called a "multi-prime" key.

On the plus side, this may offer some performance improvement. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes). For instance, if you have a 1536-bit modulus which is the product of three 512-bit primes, then the CRT replaces one 1536-bit exponentiation with three 512-bit exponentiations which are, individually, 27 times faster (assuming a classic cubic modular exponentiation algorithm), for a total speedup of 9, compared to the usual 4 with two factors. More generally, with $k$ factors, the expected CRT speedup is in about $k^2$.

On the negative side, using too small factors may weaken the modulus. The best known factorization algorithms have a cost which depends on the modulus size, not on the size of the individual factors, so using more smaller factors should have no impact... unless the factors are small enough to enter the range of the feasible with ECM: that algorithm has a cost which depends (mostly) on the size of the smallest factor. For normal, bi-prime RSA modulus, ECM is not competitive with GNFS; but if you make your factors too small, this can lower your security.

Bottom-line is that, for usual sizes, three or four primes should be tolerable and offer a nice performance boost, but don't go beyond that. Public-key operations are not impacted in any way. Note also that other somewhat related cryptosystems (e.g. Rabin) might not accept a multi-prime modulus.


Is there an AES identity key? The following questions are of pure theoretical nature. I don't have an application in mind.

Is there a key that makes AES the identity function?
Is there a key that makes AES the identity function for certain
inputs?
Is it known whether such keys might exist?
Are such keys known for other ciphers?

For example, I want to encrypt "Hello StackExchg" with AES with said key and the ciphertext should be again "Hello StackExchg".

When I encrypt "Hello StackExchg" with the perfect cipher one-time-pad, there is a possibility that the resulting ciphertext is again "Hello StackExchg". This possibility must exist (though it is unrealistically small), otherwise, the ciphertext would not be perfectly random but depending on the plaintext. The corresponding key for one-time-pad would be all zeros.

In the "ideal cipher" model, the block cipher is a permutation of the space of input blocks, chosen uniformly among all such permutations. A plaintext that gets encrypted to itself is a fixed point for the permutation; it is expected that about 63.21% of all permutations have at least one fixed point (a permutation with no fixed point is called a derangement).
Thus, assuming that AES is an ideal cipher, then it is expected that for about two thirds of possible keys, there will be at least one plaintext block that is encrypted to itself.
Now, finding that fixed point is quite another thing; we in fact expect not to be able to easily find that fixed point or even ascertain whether it exists or not -- the "moral" reason is that finding a fixed point on a random permutation requires hitting it exactly, which is akin to a brute force on the whole input space, of size 2128 in the case of AES. In other words, if we could find fixed points or even prove (non-constructively) their existence or non-existence for any specific key, then this would mean that we could differentiate AES from the ideal cipher model, and that would be worrying.
(See also that answer on crypto.SE.)
Note: while a majority of AES keys should have at least one fixed point, it is strongly expected that there is no key that turns AES into an identity function (i.e. all plaintexts being fixed points): there are 2128! ≈ 22135 possible permutations, a number waaaay larger than the 2256+2192+2128 possible AES keys, thus the identity permutation is very unlikely to correspond to a key. But then again, we don't expect to be able to prove it.


Pseudorandom functions The usual case to distinguish a pseudorandom function from a random function is to assume that the adversary can choose the plaintext blocks. Is there another case (game) in which the adversary can not choose the plaintext blocks ?

There are various adversary models, in fact it is typical to test our schemes against multiple adversaries to prove various nuances of security.

The most intuitive of all is an adversary that can produce the plaintext (or a part of it) given only the ciphertext. An extension to this model, stronger than the other, is the one you mentioned, letting the adversary select a number of plaintexts $n$ (which could be infinite), give him the ciphertexts and some random data and let him decide which is which.

In general we require the adversary to produce a result in polynomial time because while many of the primitives can in theory be broken, the probability of this happening in polynomial time is considered negligible.


How do I calculate the private key in RSA? Given $n=pq$ for $p,q$ known, I can calculate $\phi(n)$.

$e$ is selected such that $\gcd (e,\phi(n)) = 1$.

Using this, how do I calculate the RSA private key?

Example:

  I have $n = 35$, with $(p,q)=(5,7)$.
  I have also computed $\phi(n)=24$, and selected $e$ such that $\gcd (e,\phi(n)) = 1$ by taking $e=23$.

  Calculate the private key.

The private key $d$ of RSA algorithm with public parameters $(N,e)$ is such that:

$ed \equiv 1\mod{\phi(N)}$. Since by definition $e$ and $\phi(N)$ are coprime then with extended euclidean algorithm you can find such $d$: $ed +k\phi(N)=1$

Consider that to compute $\phi(N)$ you should know how to factor $N$ since $\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$

To see why this is correct imagine an encryption of the message $m$ to be $c=m^e\mod{N}$.
Then to decrypt you compute $c^d=m^{ed}\mod{N}=m \mod{N}$


AES-CTR authentication salt+HMAC(ciphertext) OR HMAC(salt+ciphertext) Which one of these functions are preferred for authenticating AES-CTR?

function encrypt(msg, key) {
    encryptionKey, encryptionSalt = newPBKDF2(key)
    hmacKey, hmacSalt = newPBKDF2(key)
    ciphertext = aesCTR(msg, encryptionKey)
    hmac = generateHMAC(ciphertext, hmacKey)
    salt = encryptionSalt + hmacSalt
    return hmac + salt + ciphertext
}

VS

function encrypt(msg, key) {
    encryptionKey, encryptionSalt = newPBKDF2(key)
    hmacKey, hmacSalt = newPBKDF2(key)
    ciphertext = aesCTR(msg, encryptionKey)
    salt = encryptionSalt + hmacSalt
    hmac = generateHMAC(salt + ciphertext, hmacKey)
    return hmac + salt + ciphertext
}

None of them. PBKDF2 should not be used multiple times or for large output. I would recommend to use an additional KBKDF such as HKDF.

function encrypt(msg, passphrase, iterationCount) {
    sessionKey, salt = newPBKDF2(passphrase, iterationCount)
    encryptionKey = HKDF(sessionKey, 'ENC')
    encryptionIV = HKDF(sessionKey, 'IV')
    hmacKey = HKDF(sessionKey, 'MAC')
    ciphertext = aesCTR(msg, encryptionKey, encryptionIV)
    authTag = generateHMAC(ciphertext, hmacKey)
    return salt + ciphertext + authTag
}

Iteration count should be set to high for passphrases. A good passphrase is still required.

As encryption already should be randomised to achieve CPA security there is no need for a salt input to HMAC. Note that replay attacks may still work if you reuse the passphrase, of course. You need to take care of that in the protocol definition.


How well is it understood mathematically why encryption schemes are hard to crack? I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure.

I know that encryption is all based on two principles of "confusion" and "diffusion", but these are very general, handwavey principles. I have not read anything like a formal definition of these two principles, and some kind of proof that if an algorithm satisfies them, it is secure by some formally defined metric.

Moreover, I know that it is currently an open problem whether one-way functions exist or not.

I therefore get the impression that there is not really a very formal mathematical underpinning for our trust in the security of encryption schemes, but that may be taking it too far.

So that's why I'm wondering: what is our current formal mathematical understanding of what makes encryption schemes secure?

Is there a mathematical theory of "hardness of cracking encryption", with something like a formal definition of hardness and proofs that xertain encryption schemes are hard to crack?

Are ther partial theories, that formally capture aspects of encryption security but not others?

...I know that encryption is all based on two principles of "confusion" and "diffusion"

Symmetric algorithms such as block ciphers, hash functions, and stream ciphers are based on these principles. One Time Pads are not. And asymmetric algorithms are not built from these principles, though they may end up possessing them anyways.

  ... but these are very general, handwavey principles

Actually, diffusion is pretty well defined. There is the avalanche effect, which says that flipping one input bit should result in approximately one-half of the output bits being flipped. There is also the notion of branch number.

"Confusion" is a bit more nebulously defined, although there do exist s-boxes that are known to provide optimal stats against known cryptanalytic techniques.

  So that's why I'm wondering: what is our current formal mathematical understanding of what makes encryption schemes secure?

You'll have three different answers, depending on whether or not you're talking about One Time Pads, symmetric ciphers, or public-key encryption.

One Time Pads

One Time Pads are information-theoretically secure, which means that no computational algorithm operating on the ciphertext can help you to learn anything more about the plaintext than what you already know, irrespective of advances in computational power or clever algorithms

Unfortunately, they are too cumbersome to use in practice

Symmetric ciphers

A good symmetric cipher is designed to resist all known attacks, such as linear and differential cryptanalysis.

However, "all known" attacks is certainly not a formal proof that no (publicly) unknown attacks exist that could break a given algorithm.

Proving that an algorithm is computationally secure means a proof that breaking the algorithm implies the ability to break a problem that is known to be hard. No typical block ciphers carry proofs of this sort.

That does not mean they carry no proofs at all. For example, AES has proofs for resistance against known attacks.

Asymmetric algorithms

Asymmetric algorithms are built from problems that are assumed to be hard.

"Assumed to be" might seem unsatisfactory; Unfortunately, that's the best anyone can do until the $\text{P}$ versus $\text{NP}$ debate is proven one way or the other.

This is a major open problem in the world of computer science: If you solve it, you can claim a $1,000,000 prize (and most likely a place as a legend in the history of science and mathematics too).

If $\text{P} \neq \text{NP}$, which is what many people believe to be the case, then cryptosystems built from problems in NP would be secure.

If $\text{P} = \text{NP}$, then it is not necessarily the case that all cryptosystems would be insecure in practice. Such a proof might:

Only prove the relationship between the problem classes, without actually constructing an algorithm that solves $\text{NP}$ problems in polynomial time.
Even if such a proof were constructive and included such a polynomial time algorithm, the running time of that algorithm could still be something like $O(n^{1000})$, which would be unhelpful for solving such problems in the real world.

Impagliazzo's Five Worlds

For more on how things would be depending on the $\text{P}$ versus $\text{NP}$ question, you might check out Impagliazzo's Five Worlds. It details what type of world we would live in depending on which relationship is true.