What is encrypted with the key to give the keystream in CTR mode exactly? I'm learning how CTR mode and there is something I have trouble understanding. If I understood correctly, two components are encrypted with the key, a nonce and a counter concatenated, and it looks like for example a5b1fe9ac36701ba0000000000000003 : 8 bytes of nonce and 8 bytes of the counter padded with zeros. However, I also read that reusing the nonce produce the same keystream and must be avoided. Why is that, since the counter will differ each time ?

The counter is increased for each block in a message. However, it is restarted at zero for the next message. That way only the nonce is required to be different. If you can synchronize the counter over multiple messages then yes, just increasing the counter is secure. However, you would loose the ability to encrypt messages in parallel, and you would somehow need to keep track of the counter when finishing encrypting a message.
Note that the 8 byte nonce and 8 byte counter is just one way to create a unique input for the block cipher. Other schemes / sizes are certainly possible. For instance, you could use the ID of an entity in there to separate those for the same key (a bit for a client & one for the server). Generally however, we keep to a nonce and counter in that order. Domain separation is often performed by using different keys for different purposes.
Beware that it is often up to the user to make sure that the counter doesn't overflow into the nonce. Furthermore, if the nonce is randomized then you should take note of the birthday paradox; it might be a good idea to increase the nonce size compared to the message size. E.g. a 32 bit counter would still leave you with $16 \cdot 2^{32} = 64\ \text{GiB}$  message size. That should even be enough for most high bitrate movies, and it would leave you with a full 96 bits for the nonce. The authenticated cipher mode GCM - which uses CTR mode internally - does exactly specify 64 GiB - 32 bytes as maximum message size, so you can guess the nonce and counter size by that alone.


decrypt numbers multiplied by a certain floating point number A friend has about 10K numbers in a an excel sheet. He wanted to encrypt these numbers in order to share the file with a 3rd party that will help him reorganize the tables. What he did, to hide the numbers, is to multiply all the numbers by a floating point number.

Based on my limited knowledge of encryption I argued that this method seems fairly weak (compared to other methods of encryption). My question is - Am I right in my argument or is it really difficult to decipher this sort of encryption.

There is a line between encryption and obfuscation, I would say this is on the latter side.

If someone knows the method, and is able to correctly guess even 1 of the original values, simple math will reveal all the original values. Additionally, depending on the type of data in the field, guessing the floating point number may only take seconds even with no 'plaintext' guess, and you have thousands of values to test it on.

Most encryption is based on some kind of permutation and is reversible, floating point values have a maximum level of precision, and can cause the original value to be lost in some cases. Rounding may be able to recover them, but if the original values also have a certain level of precision, there may be no way to recover them, assuming you are not recovering from a backup, but rather trying to decode in Excel.

Examples
Here is an example of an information disclosure that recovers the key.

Say 2 of the encoded values are $388874698.219672$ and $293536403.581274$. If a strong assumption can be made by the table format or header names that these are relatively small integers, say dollar values, you can multiply the ratio by successive values until you find another value with the same relative rounding error. Lets assume they are prices under $1000:

$R = 388874698.219672/ 293536403.581274$

$R = 1.32479206488609$

Multiply $R$ by an incrementing integer counter and round to 6 decimal places till we get an integer. We can even implement the attack in Excel and visually compare, say on the victim's laptop. Extend the following down 100000 rows:

A1 = ROUND(ROW(A1)*1.32479206488609,6)

Then page down till you see an integer. We run into one at row 19357, with a value of 25644. It can be reasonably assumed these translate to 193.57 and 256.44. A little bit of math recovers the 'key' used hide them, which will probably have rounding errors. Testing this against more values and averaging out some more guesses will narrow down which digits of the key are significant and verify if it is correct. An automated attack will take a fraction of a second, even with much larger values.

Since the ratio of values is preserved when using multiplication, guesses can be made about the nature of the data, and information can be exposed even without knowing the real value. mikeazo's example regarding salary information will expose if someone makes more or less, and by what percentage that difference is.


How is a group element converted into a key? I've only just started research on cryptography so I apologize if this is a basic question or I'm getting terms confused.

I'm researching braid group cryptography and currently looking at the Anshel-Anshel-Goldfeld key exchange protocol applied to braid groups via the colored Burau representation. Both parties have a shared secret commutator, an element in the braid group $B_n$, and then calculate it's colored Burau representation which is a pair (M, $\pi$) where $\pi$ is a permutation and M is a matrix with entries in $\mathbb{Z}[t_1,t_1^{-1},...,t_n,t_n^{-1}]$. We then apparently reduce M modulo some prime $p$, and "plug in the result to a key
hash function". I have a few questions about this last statement:

What is the point in reducing the matrix M?
Is using a hash function the standard way to convert an abstract group element into a usable key? If so, is there as standard hash function for each particular type of group?
Is the hash function a 'key derivation function' or a 'key extractor'?

I don't know the protocol, so I'm not sure.
It is a standard way of converting group elements (e.g. the shared value $g^{ab}$ you get after Diffie-Hellman) to keys. You don't need to worry about the specifics of the group when choosing a hash function, just use a cryptographic hash like SHA256.
It's hard to know what the difference between those two is without more context. You are certainly using the hash function to derive a key, but not all hash functions are also key derivation functions. Usually you talk about 'extractors' in the context of extracting entropy from a value, so in a sense the hash function is also an 'extractor' in that the hash is (probably) shorter than the value being hashed but contains (roughly) the same amount of entropy.


How to do unmasked addition on SSS masked shares? I'm trying to understand how Shamir's Secret Sharing algorithm is applied to AES when doing threshold masking.
I understand how the secrets are created  and the secret is calculated and I'm now trying to figure out how the math operations (that are  needed for AES) work when you have the shares. To do that I'm reading this source: Goubin et al, Protecting AES with Shamir's Secret Sharing Scheme. (pages 79-94 in isbn 978-3-642-23951-9)
It says: addition of shares with an unmasked value: $$\{(x_i', y_i') \leftarrow (x_i,y_i \oplus u) | \forall (x_i, y_i) \in shares\}$$
Where $u$ is the to be added value and $(x_i, y_i)$ is an original share. Addition results in a new $(x_i', y_i')$ share.
I've implemented this in python (not in a finite field) in this way:
def add_unmasked(self, shares, value):
    return [{'x': share['x'], 'y': share['y'] ^ value} for share in shares]

However I don't see the correct results, if I have a secret of 20 being shared and unshared results it in 20, but if I add 1, I get the wrong result 80% of the time.
For completeness sake my code:
def create_shares(self, to_create):
    if to_create < self.degree + 1:
        raise Exception('shares don\'t cover the order')

    coefficients = self.generate_polynomial(self.degree, self.secret)

    points = random.sample(range(self.finite_field), to_create)
    shares = [{'x': point, 'y': sum(coefficient * point ** n for n, coefficient in enumerate(coefficients))} for
              point in points]

    return shares

def tell_secret(self, shares):
    # doing a polynomial interpolation using the basic definition. sum y * l where l is the product of x - xi / xm - xi. x is 0 in our case
    xs = [share['x'] for share in shares]

    y = 0
    for share in shares:
        l = 1
        for x in xs:
            if x != share['x']:
                l *= (- x) / (share['x'] - x)
        y += share['y'] * l
    return int(round(y))

edit:
Reading wikipedia about the definitions of operators in a finite field, I've found this:

A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND.

AES uses a $GF(2)$ finite field, the Galois field $GF(2^8)$
So when my paper says: $\oplus$ they mean the addition operator for the finite field GF(2). This is confirmed by my test when doing an addition in my non finite field program.

edit 2:

As such I read this as doing a $GF(2^8)$ addition to all the shares. It is using the word XOR and I've read that it should be XOR in the finite field but when I do this in my testing program, I don't get the correct result. This seems to be because of at least one share having an y value which overflows with the addition.

edit 3:
So I've found the following lines in the referenced paper:

Our scheme maintains the same compatibility as Boolean masking with the linear transformations of the algorithm

So it seems that the paper proposes some kind of SSS mixed with boolean masking on an AES implementation. I still don't get it completely but I'm moving on and maybe if I come back to it later my understanding will have improved.

It seems that the question you're asking is about how to add a public (unmasked?) value to a secret-shared value. I suggest you edit the question a bit to clarify that this is not related to AES directly.
With that aside, adding a public value to a secret-shared value depends heavily on what secret-sharing scheme you're using, and also the algebraic structure where you're doing it, of course.
To secret-share a  single bit $b$ using additive secret sharing, you sample random bits $b_1$ and $b_2$ constrained to $b=b_1\oplus b_2$. The pair of shares is then $(b_1,b_2)$. To add a publicly known bit $u$, you only need to add it to one of the shares, say to $b_2$, so the new shares are $(b_1, b_2\oplus u)$. You can check that if you add (i.e. XOR) these together then you get $b\oplus u$, so you effectively added $u$ to the secret.
If you're additively secret-sharing elements of $\mathsf{GF}(2^8)$ instead of single bits the principle is the same, except that XOR is replaced with addition in $\mathsf{GF}(2^8)$. Quite coincidentally though, addition in $\mathsf{GF}(2^8)$ is precisely component-wise XOR, but this didn't need to be the case, specially if you used instead, say, $\mathsf{GF}(3^8)$.
Now, all of this was for additive secret-sharing, but this is not how Shamir secret-sharing works. In this scheme, secret-sharing a value $s$ among $n$ parties with threshold $t$ consists of sampling a random polynomial $f(\mathtt{X})$ of degree at most $t$, constrained to $f(0)=s$, and letting the $i$-th share be $s_i=f(i)$.¹ With this secret-sharing scheme, adding a public value $u$ is done by letting each party (not only one) add this value to its share, getting $(f(1)+u,\ldots,f(n)+u)$ as the vector of shares. I encourage you to check why this is a valid Shamir sharing of $s+u$.
To sum up from the discussion above, I think you are mixing additive with Shamir secret-sharing. The method you described and implemented is for adding a public value to an additive sharing, yet you mention in the title and the text Shamir secret-sharing.

¹ Here, the "numbers" $0,1,\ldots,n$ that we are evaluating into the polynomial are simply symbols to represent different elements of the field you're considering, e.g. $\mathsf{GF}(2^8)$.


Is it just as difficult to find a desired output in a hash digest, for MSB vs LSB? This question comes to mind after seeing "custom" Bitcoin addresses with some special string at the beginning of the address. They are generated in the same way Bitcoins are "mined", continually hashing with a nonce + password to get some desired output.

My question is, is it just as hard to find [HLOWRLD]M9VveeBLcY4UC4vjpPs6rZtFBQE as it is to find 1FpUYCpM9V[HLOWRLD]4UC4vjpPs6rZtFBQE as it is to find 1FpUYCpM9VveeBLcY4UC4vjpPs6[HLOWRLD]? *Note the values in the digest not in brackets can be any value

The reverse to the question, given you have some insane computer, would it be easier to try to find the input for [HLOWRLD]M9VveeBLcY4UC4vjpPs6rZtFBQE versus 1FpUYCpM9V[HLOWRLD]4UC4vjpPs6rZtFBQE versus 1FpUYCpM9VveeBLcY4UC4vjpPs6[HLOWRLD]?

As the other answers point out, output bits of a good hash function are uniformly distributed, so your substring has equal chance to appear in any part of the hash digest.

However, in the case of Bitcoin, the address is not a random string. Not only it starts with a predefined number (1 or 3), but the string is the result of the Base58-conversion, which may (I did not check) produce biased outputs. The addresses may even be of different lengths.


What are the fundamental roots of modern symmetric encryption? In academic pursuits, we often have people (and their ideas) who are considered fundamental to the subject, such as Bayes and probability.
In cryptography, it's obvious to see that the Diffie-Hellman problem is fundamental to modern key exchange algorithms.
Can modern day symmetric encryption methods be similarly traced back to particular fundamental roots or building-blocks? If so, what are they?
Is there a common grandparent (or few) that most modern symmetric crypto such as AES or ChaCha can be undeniability related to?

There are a few here.

Block ciphers like DES and its modes are based of Feistel Cipher, AES is based on Rijndael.

Others like FOX64 based on Lai-Massey scheme.

Other are are stream ciphers like RC4.

So, These are some of the schemes which are used in todays symmetric key ciphers.


RC4 key schedule and algorithm design I've looked up RC4 algorithm and it's seems easy enough but some parts of it seem random to me.
In the key schedule part take for example the following part :

j = (j + S[i] + key[i % keylen]) % 256

I can understand most of it:

the key[i % keylen] is padding in-case that the key is shorter than 256 bytes, and
the % 256 is to ensure that j will be in the range of 0-255 when performing the swap.

But why do we need the j = j + S[i]?

Is there a mathematical explanation to this or is it just to add some randomness? Also regarding to the pseudo random generator part: can someone point me to a reference which offers an explanation for the not so obvious operations?

I've looked for explanations on the internet but couldn't really find anywhere that explain those bits.

The correction question you should ask about why various operations in RC4 (or, for that matter, any other cipher) are there would be "if I were to remove that, what would the impact be?  Would this weaken the cipher in some way?"

At your current state of knowledge, that may be a rather imponderable question, but it is still the correct one.  I can try to give you a simple example: if you remove the $S[i]$ from the update of $j$, leaving

j = (j + key[i % keylen]) % 256

Then $j$ will follow a much simpler trajectory through the array as we run the key setup routine.  In particular, if the key bytes just happen to sum to a multiple of 256 (which will happen 1/256 of the time for a random key), then $j$ will visit only (at most) keylen bytes of the array; all the other elements of the array will participate in one swap.  Now, it's not immediately clear how a bias like this might influence the cipher; however it is quite plausible that it wouldn't be good.


Question about why RSA is hard to attack I think I understand why RSA is hard to attack but I'd like to get clarification if I actually do.

Assume there are two people, Alice and Bob, who are attempting to communicate privately but that we can listen to all of their messages to each other.  Assume we know they're attempting to communicate using RSA and that Alice has sent $n$ and $e$ to Bob and Bob has sent $c$ to Alice.  Because we know they're using RSA, we also know that $n$ is the product of some primes $p$ and $q$, that $e\in\mathbb{N}$ with $1<e<\phi\left(n\right)$ (notice that $\phi\left(n\right)$ is hard to calculate because we do not know $p$ and $q$, but this has no significance in terms of the bounds of $e$ since we know $e$ explicitely), and that $e$ is relatively prime (aka coprime) to n (i.e. $\text{gcd}\left(e,n\right)=1$).

We know that Bob's message to Alice can be expressed in terms of $n$, $e$, $c$, and Bob's intended message, $m$ given by $c\equiv m^{e}\bmod{n}$.  For the sake of thoroughness, we also know $m<n$.

I hope this is right so far.

Tactic 1

As an attacker, we want to find $m$, and since we have an equation including it, one way to go about finding it is to re-express said equation.

$c\equiv m^{e}\bmod{n}$

implies

$\exists k\in\mathbb{N}:m^{e}=c+kn$

implies

$\exists k\in\mathbb{N}:m=\left(c+kn\right)^{\frac{1}{e}}$

Now comes my question!  As the attacker, in order to find $m$, we'd have to try all $k$'s in the natural numbers until we found an $m$ that looked like a message--and even then, even if it's intelligible, it's possible what we've found is still actually not Bob's intended message.  Is this a correct assertion?  Is this a possible yet obviously futile attack?  (Further questions: Is it possible for the attacker to verify if the $m$ computed via the above method is equivalent to Bob's $m$ using the assumptions above?  If yes, if someone were to execute this attack, how long on average would it take to find the correct $m$ given $m$ is random?)

Tactic 2

Another tactic we might take would be to compute Alice's secret key, $d$, such that $ed\equiv1\bmod{\phi\left(n\right)}$ (i.e. $d$ is the multiplicative inverse of $e\bmod{\phi\left(n\right)}$).  We can, again, re-express this.

$ed\equiv1\bmod{\phi\left(n\right)}$

implies

$\exists j\in\mathbb{N}:1=ed+j\phi\left(n\right)$

implies

$\exists j\in\mathbb{N}:d=\frac{1-j\phi\left(n\right)}{e}$

Now the second question!  As the attacker, calculating $\phi\left(n\right)$ is hard. This is because there are two ways we could calculate this: 1) by the definition, i.e. the cardinality of the set of relatively prime numbers to $n$ (which would take at most $\sqrt{n}$ steps, right?) or 2) since we know $n$ is the product of 2 relatively prime numbers, attempt to find $p$ and $q$ and then $\phi\left(n\right)=\left(p-1\right)\left(q-1\right)$.  This is hard to do for large $n$.  Is this correct assertion?

Actually, wait, I've caught myself.  Because even after calculating $\phi\left(n\right)$, we'd still have to find $j$, no?

Could someone answer these questions and possibly answer succinctly way attacking RSA is hard?  I feel like I'm so close and just need a little help-nudge.

There are a number of small mistakes in the question. Let's clean up that first.

$\gcd(e,n)=1$ is likely, but neither necessary nor sufficient for RSA to work; the right condition is $\gcd(e,p-1)=\gcd(e,q-1)=1$. Notice this implies $e$ odd for any non-trivial choice of $p$ and $q$.

Even in textbook RSA, the right equation is not $c\equiv m^e \bmod n$, but $c=m^e\bmod n$. The first can be understood as $c\equiv m^e \pmod n$, and only the second implies that $0\le c<n$. The distinction is important: $c'=m^e$ satisfies the first, but (for most $m$) not the second, and would make RSA both unsafe and (except for small $e$ like $e=3$) extremely impractical as an encryption method.

Although that is not directly relevant to the questions, RSA as practiced is PKCS#1. A number of things change. The most important is that $m$ is not the message, but rather a randomized and reversible function of the message. Also, it is used $p≠q$, $1<e<n$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ where the question and the original RSA article uses $\phi(n)=(p-1)⋅(q-1)$, for determining the private exponent $d$ such that $e\cdot d\equiv1\pmod{\lambda(n)}$ and $1<d<n$.

Coming to the question about tactic 1:

An attacker Eve has the choice of means; she do not have to try a particular strategy, as in "in order to find $m$, we'd have to try all $k$'s in the natural numbers.."; she could try that strategy.

If she elected to follow the proposed strategy, try some $k$'s in the natural numbers and compute $m=(c+k\cdot n)^{1/e}$, she'd have a much better option than trying to guess if the resulting $m$ looks like a message; she can conclusively rule out a guess of $k$ when the resulting $m$ is not an integer, which occurs for the overwhelming majority of $k$. And also, she can decide if an integer $m$ in range $[0\dots n-1]$ is the right message by computing $m^e\bmod n$ and comparing that to $c$; they are equal if and only if she guessed the right $k$, and/or otherwise recovered $m$.

Tactic 1 is of course futile because they are too many $k$ to test.

Concerning tactic 2: the assertion is correct, for some loose use of "This is because"; exposing two methods to find $\phi(n)$ does not implies that they are the best ones, much less the only ones.

Notice that if an attacker Eve knew $\phi(n)=(p-1)\cdot(q-1)$, she's done: she can then compute an $f$ such that $f\cdot e\equiv 1\pmod{\phi(n)}$ and that let her decipher using that $m=c^f\bmod n$. Although her $f$ might not be the $d$ used by the legitimate key holder, which is any $d$ such that $d\equiv f\pmod{\lambda(n)}$, she does not care.

Attacking RSA encryption is believed hard when $n$ and $e$ have been properly chosen, and the message $m$ is a random integer in the set $[0\dots n-1]$, and all else that's known about $m$ is $c=m^e\bmod n$, because the best methods we have to solve that problem are of cost as high as factoring $n$, and the best general method known for that is GNFS, and the expected cost for that is prohibitive by definition of "$n$ has been properly chosen". This is circular, loose, and not a mathematical proof that RSA or factoring is hard. Neither is known with certainty. Notably, the definition of "$n$ has been properly chosen" has changed drastically since that original RSA article. That "RSA hard" implies "factoring hard" is obvious, but the converse is an open problem.


How to map output of hash algorithm to a finite field I would like to know an algorithm hash to a finite field.
I have an $l$ bit prime number $q$. I want setup a hash function $H: \{0,1\}^* \to \mathbb F_q$ but I do not know how I can do it.
I use a library for a hash with C++, this is cryptopp.
I find an answer at  Right way to hash elliptic curve points into finite field but I don't understand.
Does anyone help me know what to do?

To hash from $\{0,1\}^*$ (or other large domain) into the integers in $[0,q)$ or any set with a natural mapping¹ to that interval, pick a $b$-bit security margin, a hash $H$ at least $h=\lceil b/2+\log_2q\rceil$-bit and unrelated to others used in the cryptosystem, and define the hash of bitstring $M$ as $H(M)\bmod q$, with $H(M)$ considered an integer in $[0,2^h)$ per e.g. big-endian convention.
When $M$ is random and $H(M)$ has at least $b$-bit security against distinguishing attacks, this has at least in the order of $b$-bit security against distinguishing attacks. When $q>2^b$, this has at least in the order  of $b$-bit preimage resistance. When $q>2^{2b}$, this has at least in the order of $b$-bit collision resistance.
E.g. for $q$ up to 400 bits, $\text{SHA–512}(M)\bmod q$ will do if nothing in the system uses SHA–512 (nor something built using the same constants).
If ones needs several independent such hash functions, one should use several independent $H_i$ to start with. That can be constructed from a single hash $H$, e.g. as $H(M\mathbin\|i)\bmod q$.

¹ The mapping between the destination set and $[0,q)$ must be efficiently computable in both directions. Therefore the set can be the finite field $\mathbb F_q$ when $q$ is a prime or a prime power, or the ring $\mathbb Z_q$ (aka $\mathbb Z/q\mathbb Z$). We need a different construction for an Elliptic Curve (sub)group of order $q$ if we posit it's one where the Discrete Logarithm problem is hard.


Why does DSS have such formulas? I've learnt the formulas needed for the DSA (http://en.wikipedia.org/wiki/Digital_Signature_Algorithm).

But most importantly, I don't quite understand what represents those formulas and why they are the way they are. For example, why if v = r then the signature is verified, why do r and s have such formulas etc.? RSA digital signature is so much simpler.

The fundamental difference between RSA-groups and prime order groups is that in RSA groups the multiplicative order of the group is unknown (without knowledge of the factorization). This allows much easier constructions for unforgeable signatures (although hashing and padding are required to ensure existential unforgeability).

With knowledge of the group order, a forger has more possibilities to calculate "useful" group elements. This results in the DSA formulas (and the related ElGamals signatures) to be more complex.

Let's have a look at what these formulas actually calculate, and for simplification I'll leave out all the modulo operations (they are applied in the correct way). The goal is to get expressions which only depend on the hash $H$, the signing key $x$, and the (random) blinding value $k$.

The signature is:
$$r=g^k$$
$$s=k^{-1}(H+xr) = k^{-1}(H+xg^k)$$

Let's look at the verification algorithm backwards:
$$v=g^{u_1}y^{u_2} = g^{Hs^{-1}}g^{x \cdot r s^{-1}}$$
$$=g^{s^{-1} (H+xr)}$$

Here is the interresting part: A valid signature will solve like this:
$$= g^{(k^{-1}(H+xg^k))^{-1} (H+xg^k)}= g^k = r$$

For a forger, this is differently: He can choose $r$ and $s$ arbitrarily, but he does not know $x$ but only $y=g^x$. To forge a valid signature, it has to fulfill this equation:
$$g^{s^{-1}H}y^{s^{-1}r} = r$$
However, we can not solve this equation without calculating some discrete logarithms.


Question about the definition of a perfect cipher I need to prove that the following encryption scheme is a perfect cipher:

Let $p$ be a prime. The secret key is a pair $(a,b)$ sampled uniformly at random from $\mathbb{Z}_p^* \times \mathbb{Z}_p$. An encryption of a message $M \in \mathbb{Z}_p$ is defined as:

$E_{a,b}(M) = aM + b \mod p$

The problem is that I don't understand what do I need show formally. What I could find regarding the definition of a perfect cipher is that knowing the ciphertext gives absolutely no information towards knowing the plaintext, or in a probabilistic language:

$\mathbb P(plaintext = P|C) = \mathbb P(plaintext = P)$, where $C$ is ciphertext.

Needless to say that it doesn't help me at all...

Since this is homework, I'm not going to give the answer, but will hopefully point you in the right direction.

You are correct when you say for a perfect cipher, the probability should hold that $\mathbb{P}(P=m|C=c)=\mathbb{P}(P=m)$. In words, this means that given that you see the ciphertext is $c$ what is the probability of the plaintext being $m$ (note, I'm using $P$ for the plaintext space and $C$ for the ciphertext space). If being given the ciphertext does not help the adversary at all (i.e., the probability of any plaintext does not change at all given the ciphertext), then the cipher is said to be perfect. Almost all modern ciphers that we use today we cannot prove this property. For the cipher you are studying, however, it is possible.

By applying bayes rule, we get
$\mathbb{P}(P=m|C=c)=\frac{\mathbb{P}(C=c|P=m)\mathbb{P}(P=m)}{\mathbb{P}(C=c)}$ and we want to show that this equals $\mathbb{P}(P=m)$. Therefore, if the other term on top cancels out the term on bottom, we would get what we want.

To help a little more, think about what the two terms are. On bottom we have $\mathbb{P}(C=c)$. In other words, what is the probability of each ciphertext (independent of plaintext). The ciphertext space is $\mathbb{Z}_p$ so the size of it is $p$.

The other term is $\mathbb{P}(C=c|P=m)$, meaning, given a plaintext message $m$, what is the probability that the ciphertext is some $c$. So, given a plaintext $m$ if all ciphertexts in $C$ are produced by the same number of keys, then $\mathbb{P}(C=c|P=m)$ would simply be $\mathbb{P}(C=c)$ in which case the two terms would cancel as we want.

I'll leave that up to you to show.


Rueppel's example of self-clocking LFSR Consider the following excerpt from Rueppels paper, titled When Shift Registers Clock Themselves:

His example includes $C(D) = 1 + D + D^2 + D^3 + D^4 + D^5$ as a primitive connection polynomial. However, this polynomial is not irreducible, let alone primitive, since it can be factored as $(1+D)(1+D+D^2)^2$ over $\text{GF}(2)$.

What am I missing?

There is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$

The easiest way to see that there is a mistake or not is coding!
There is an almost good pylfsr library. This library also lists primitive polynomials in their format.
L.get_fpolyList(m=5)

[5, 2]
[5, 4, 2, 1]
[5, 4, 3, 2]

The list verified, too.

$x^5 + x^2 + 1$
$x^5 + x^4 + x^2 + x^1 + 1$
$x^5 + x^4 + x^3 + x^2 + 1$

I've created a python program to test these. Luckily I've found it on the first try!
import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
    print(L.state[-1], end=",")
    if L.outbit == 0:
        L.next()
    else :
        L.next()
        L.next()
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1")

It produces the output
5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
 State        :  [1 1 1 1 1]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1
 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

Thanks to Nikesh Bajaj to indicate better usage of the library ( See in the other library).
Therefore there is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$


Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack The curve $E(\mathbb{F}_{47}):y^2=x^3+x+38$ has order $61$ and $61|47^3-1$ so the embedding degree of $E$ is $3$ and therefore the MOV attack, presumably using some sort of distortion map and a suitable pairing can be used to find discrete logarithms. Exactly how is this done in this case?
If a larger example would better illustrate the power of the technique then $E(\mathbb{F}_{8111}):y^2=x^3+x+300$ has order $8269$ and $8269|8111^3-1$

Let's take your latter example. We will use the Weil pairing here, since that was the original MOV approach. Let's pick some arbitrary points in your curve:

$$
\begin{eqnarray}
P &=& (6116 : 2715) \\
Q &=& (3034 : 462)
\end{eqnarray}
$$

From now on, we'll actually work in an extension field of $\mathbb{F}_{8111}$, namely $\mathbb{F}_{8111^3}$. For concreteness, we choose the polynomial $x^3 + 4x - 11$ to define the extension field.

Now we need to find some arbitrary point that has order $8269$ but is not a multiple of $P$. We know that the group structure of the points of order $n$ in a pairing-friendly curve is $E(F_q)[n] = \mathbb{Z}_n \oplus \mathbb{Z}_n$, so there are definitely such points out there. An example point would be

$$
R = (3515x^2 + 7098x + 2717 : 3745x^2 + 7258x + 4072).
$$

Now all it's left is to apply the Weil pairing to both points:

$$
\begin{eqnarray}
w_1 &=& e(P, R) \in \mathbb{F}_{8111^3} \\
w_2 &=& e(Q, R) = e(uP, R) = e(P, R)^u \in \mathbb{F}_{8111^3}
\end{eqnarray}
$$

Now we can solve the log of $w_1 = 7474x^2 + 74x + 6953$ and $w_2 = 2625x^2 + 6673x + 243$ over $\mathbb{F}_{8111^3}$. It's $2634$, and it's easy to see that $2634\cdot P = Q$. For large fields, it is considerably faster to find $\log_{w1} w2$ via the number or function field sieve ($L[1/3; c]$) than the elliptic curve discrete log $\log_P Q$ via Pollard's rho ($O(n^{1/2}))$.


Showing that security of a elgamal invariant is insecure Original Elgamal signature is defined
$S(m, \alpha) = (r, s)$, where

$$r = g^k \bmod p$$

$$s = (m – r\cdotα)k^{-1} \bmod (p – 1)$$

more information on Elgamal signature can be found here.

Variant of a Elgamal signature scheme is defined as

$$s = (r\cdot\alpha + k)m^{-1} \bmod (p-1) $$

I was stuck in the question that:
"Show that attacker Eve who has observed the signature of a message m can obtain the signature of any message she likes."

You have just to look at the signing/verification relation.

Just write it as $$m\cdot s \equiv r\cdot \alpha + k \bmod (p-1)$$

And the verification relation should be $$g^{s\cdot m}\stackrel{?}{\equiv} y^r\cdot r \bmod p$$
where $y=g^\alpha$ is the public key and you eavesdrop a signature $(r,s)$ for $m$.

Observe that you can take any multiplicative decomposition of the left hand side of the verification relation that yields the value $$m\cdot s \bmod (p-1)$$  to compute a signature for an arbitrary message $m'$ (I let the details to you, this should be easy to figure out). Let $r$ be identical to the eavesdropped signature and just adjust your new $s'$ to the chosen $m'$ and
you will have a valid signature $(r,s')$ for any message $m'$ of your choice.


Can you hash an ssh key to generate a symmetric password? Let's say you need a 256 bit password but all you have is an SSH key.  Can you securely transform the SSH key into a symmetric password via a hashing function?  What would be a good choice for a hash function?

Yes... Assuming:

That they were generated using enough entropy (probably yes if they were generated securely)
That they are only used for this purpose (I'd guess you can hash private key, but then as soon as it is compromised, your key is too)
It isn't done using public key, if that key is then published

As for hash function, any hash that isn't broken will do.


Why is variable rotation uncommon in cryptographic primitives? Most cryptographic primitives I've seen rotate by a constant. RC5 did something different though:

For a word size $w=2^n$, you can take the last $n$ bits of a value as a rotation amount. There's more sophisticated variants like that used in RC6.

To give these values a name: $A \lll B$.

Some good things:

Rotations are fast
Provides some diffusion
Has some nonlinear properties
Can be strong when combined with other operations

Some bad things:

Parity of $A$ is preserved
Differences in $A$ are preserved
Only a few bits in $B$ are used
Differences in $B$ may not have an effect (or have little effect)
Less differences if $A$ is mostly (or all) 0s or 1s
Less differences with alignment in $A$
Multiple variable rotations are not proportionally better

There's probably some more subtle weaknesses that make it more susceptible to differential cryptanalysis, but nothing that totally breaks it I think, or RC5 would be unusable.

One issue is that data-dependent rotations (such as you describe) is patented by RSA data security (or, at least, was, the patent may have expired).  RC5 and RC6 was created by the holder of this patent, however such a patent could be enforced against someone else, and so people have shied away from it.

More minor issues would include:

It is likely to take variable time on lower-end CPUs, and hence potentially vulnerable to time-based side channel attacks.
Such variable rotates are moderately expensive in hardware (when they need to be implemented in constant time); yes, you can construct a barrel shifter, but that takes a number of gates and interconnects.


Finding AES ciphertext stealing test vectors? I am unable to find any test vector document for AES CTS (ciphertext stealing).

Can you help me to find some by pointing me into the right direction or at an according reference? Do they exist at all?

Depends on what exactly you need.

Some test vectors can be found in the document "RFC 3962 - AES Encryption for Kerberos 5". If you take a look at page 11, you'll find some test vectors for CBC with ciphertext stealing, using an initial vector of all-zero.

Also, there are test vectors to be found at more exotic places like mozilla.org test vectors for AES CTS. They took the original test vectors for AES CTS-3 (Kerberos) and modified them for AES CTS-1 (NIST).

I'm sure that you favorite search engine will help you pinpoint the rest.


How did the power measurements translate to AES Key? A side channel attack is described here.
I did not quite get , how the power measurements are used to get the
decryption key , can any body explain it?

I am not familiar with your side channel attack "here", but it looks like what I have read about before in those that monitor the processor to determine calculations.  "The trick is based on the fact that the “ground” electrical potential in many computers fluctuates according to the computation that is being performed by its processor—including the computations that take place when cryptographic software operates to decrypt data using a secret key."  Researchers using signals from grounding the computer through touch.[1]

"Traditional power analysis would measure power consumption at a frequency comparable to the CPU's clockrate (a few GHz), and is foiled by dampening emanations at these frequencies. Our attack extracts the key using much lower bandwidth (a few kHz to a few MHz, depending on settings and duration). Our attack is also more resilient to filtering and noise." [2]  Look at "Q14: How do you extract the secret key bits?" in this article.  They find the secret key bits one by one sequentially by teasing out processor signals and what they represent.  They go through some technical steps to get their timing correct, not like they walked by a computer in a coffee shop and happened to crack it.

[1]http://www.technologyreview.com/news/530251/how-to-break-cryptography-with-your-bare-hands/
[2]http://www.cs.tau.ac.il/~tromer/handsoff/


Creating serial key generator using ECDSA, how to get signature short enough? I've written some questions in this stackoverflow and got great responses but now I'm trying to wrap it all together.

I have for the last couple of weeks been building a serial key generator project in C# to use in my own software. The goal is to be able to generate serial keys for customers of my software. To stop people from creating key generators I've been looking into elliptical curves and digital signatures using these.

So far I've been able to implement ECDSA using a secp256k1 curve. However one big question remains, how do I keep the signature, which will be made up of two points, short enough to be usable as a serial key? I do not wish to use a license file etc.

Unless I'm doing something wrong I get a signature made up of two points, each point containing a 32 byte BigInteger. This means the total byte count for the signature becomes 128 bytes. Encoding this to hex would yield 256 charactes, way too long to use for a serial key.

Now I've found this sample page:
http://kjur.github.io/jsrsasign/sample-ecdsa.html

Using this page for a secp256k1 curve the signature value in hex becomes much shorter than 256 characters. How do they get such a short signature?

I've also found a commercial solution called ellipter (ellipter.com), they get their key length down to 31 characters for a 128 bit "key strength", how is this even possible? What curves are used for 128 bit security?

Thank you!

Restricting to Elliptic Curve Digital Signature Algorithm and curves as in FIPS 186-4 appendix D:

an $m$-bit curve, that is one over field $GF(2^m)$ with $m$ prime, or over field $GF(p)$ with $\log_2(p)\approx m$ and $p$ prime (and possibly of some special form), allows schemes with $m/2$-bit security (at most, but for well-chosen curves we can largely ignore that as far a we know).
Challenges at the level $m=109$ have been publicly solved circa 2002. I'm not aware of security authorities ever vetting anything less than $m=163$ for any use, but it is technically sound to use $\log_2(p)\approx128$ as in curve secp128k1 for copy-protection (which can likely be broken by other ways than forging a signature).
An ECDSA signature normally contains two components $r$ and $s$ of $m$ bits each (ignoring the overheads of ASN.1 formatting).
It is possible to trim a few bits (say $e=8$) by omitting them from the signature, and compensating for their lack by repeating the signature generation process (with a new random seed) until hitting a signature where these $e$ bits are all zero. That increases the cost of signature generation by a factor of $2^e$ on average, which for small $e$ is often acceptable when a predictable maximum signature generation time is not essential (the distribution of the signature generation time becomes geometric/exponential; the number of attempts to generate a batch of signatures remains quite predictable). There is no loss of security except possibly from side-channel attacks (that we know; for extra confidence we can make the trimmed bits a hash of the others, rather than zero).
It is possible to trim a few more bits (say $f=8$) again by omitting them from the signature, and compensating for their lack by repeating the signature verification process, enumerating the $2^f$ possible values of the missing bits, until a valid signature is found. That increases the cost of signature verification by a factor of at most $2^f$, which for small $f$ is often acceptable (verification time has predictable maximum, and uniform distribution). There is no practical loss of security (private key recovery from the public key still remains the best known mean to forge a signature).
If a signature is keyed-in (rather than copy-pasted), one wants to re-encode the corresponding bitstring as symbols chosen to minimize the risk that a keying mistake renders the signature invalid. The problem is different depending on if you have control of the font used to render the string keyed-in, or not. In the later (worst) case, as a courtesy to the user, we should restrict to decimal digits and roman letters without accents, ignoring case, grouping symbols into equivalence classes based on visual similarity, such as $\{\text{0},\text{O},\text{o}\}\;$, $\{\text{1},\text{l},\text{I},\text{i},\text{L}\}\;$, $\{\text{2},\text{Z},\text{z}\}\;$, $\{\text{3}\}\;$, $\{\text{4}\}\;$, $\{\text{5},\text{S},\text{s}\}\;$,... We end up with perhaps $n\approx28$ of these classes, which could be stretched to $n=32=2^5$ with some extras like $\{\text{-},\text{_}\}\;$ and $\{\text{+}\}\;$ (when $n$ is a power of two, the re-encoding is slightly simplified).

Thus $\lceil(2m-e-f)/\log_2(n)\rceil$ symbols among $n$ allow to encode a signature if we are willing to spent the effort to try an average of $2^e$ signatures for generation and a maximum of $2^f$ for verification.

For secp128k1, 7RPGE 10GVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF could be a signature coded as $50$ symbols among $n=28$, $e=9.64$ (an average of 794 signatures computed for each acceptable one) and $f=6$ (64 attempts before concluding that a signature is invalid).

An extra complication of the signature generator is that it might be required to avoid signatures containing politically incorrect text, but it will only moderately complicate the generation.


What are the methods to construct a primitive binary nonlinear feedback shift register (NLFSR)? Given a binary shift register of $n$ bits, a primitive binary nonlinear feedback shift register will generate a sequence with a period of $2^n - 1$.

While I am unable to find a paper which directly describes the methods, the paper A List of Maximum Period NLFSRs has just came up on eprint, which lists all NLFRSs with a period of $2^n - 1$, for $n < 25$.

Does anyone have links to papers describing the construction methods for such primitive binary nonlinear feedback shift registers?

Update: A general method is given by Elena Dubrova: A Scalable Method for Constructing Galois NLFSRs with Period $2^n-1$ using Cross-Join Pairs, in IEEE Transactions on Information Theory, Volume 59, Issue 1 (alternate link). It gives an extensive bibliography of earlier constructs.

These constructions reorder a small number of fragments of the output sequence of a maximum-length LFSR. It does not achieve (or aim at) cryptographic security: it remains trivial to reconstruct the state of the generator from its output, from any unbroken fragment of at least $n$ bits. With slightly more bits, it is possible even if details (like $n$ and the polynomial) are unknown, using an appropriate variant of the Berlekamp-Massey algorithm.

Other than tweaking a LFSR to reorder fragments of its output sequence, I know no general method to construct Non-Linear Feeback Shift Registers with $n$ bits and period $2^n-1$, beside basically trying one by simulating the NLFSR for that number of steps, with cost $O(2^n)$ when done naively.

Large speedups are possible depending on the construct; in particular, if it is possible to explicitly compute the states that could reach the original state within $s$ steps, and performs $s$ steps as fast as one step, we can save a factor of $s$. But still the cost of establishing that a NLFSR with $n$ bits is near-maximal-period would be, it seems, at least $O(2^{n/2})$ steps with $O(2^{n/2})$ memory. However it is clearly easy to go much further that $n=25$ bits. Caveat: this is out of my head, I have no reference to quote.

In practice, it seems open cryptography seldom use maximal-length NLFSR; they could however make some sense in a cascaded construct, similar to the Alternating Step Generator or Shrinking Generator.

Also: There is simple method to construct a NLFSR with period $2^n$ using a binary shift register of $n$ bits. We start from a maximal-length LFSR with period $2^n-1$ constructed from a degree $n$ primitive polynomial over $GF(2)$, and tweak it into a binary De Bruijn sequence by inserting a single $0$ bit at the point in the sequence where $n-1$ consecutive $0$ occur. For a LFSR implemented as a shift register with a feedback term the XOR of some state bits, that's simply adding an additional XOR term with the NOR of the $n-1$ bits in the shift register that are closest to the feedback term. As a bonus, we can now start the generator in any state, including all-zero. See this related answer for details. Of course, that's not cryptographically secure.


Secure function evaluation Consider 3 parties, Alice, Bob and Charlie. Suppose
  each party has a bit as input, i.e. Alice, Bob and Charlie hold $a, b, c \in \{0, 1\}$ respectively.
  Show how construct a scheme with which they can compute the function $f (a, b, c) = a \oplus b \oplus c$
  such that the following are satisfied:

  (1) All parties learn $f(a, b, c)$ at the end.

  (2) No party can learn more about the other party's input than what they can infer from $f(a, b, c)$ and choosing their own input wisely.

My attempt: A chooses $r_1,r_2\in\{0,1\}$, B chooses $s_1,s_2,\in\{0,1\}$, and C chooses $t_1,t_2\in\{0,1\}$ randomly. Then dealer of respective secrets (bold) distribute 3 shares to each party in the following manner.

$A: \it{\bf{a\oplus r_1 \oplus r_2}}, s_1, t_1$

$B: r_1, \it{\bf{b\oplus s_1 \oplus s_2}}, t_2$

$C: r_2, s_2, \it{\bf{c\oplus t_1 \oplus t_2}}$.

To reconstruct the secret $a\oplus b\oplus c$, they can compute their sum of shares,

$A: (a\oplus r_1 \oplus r_2)\oplus s_1\oplus t_1$

$B: r_1\oplus( b\oplus s_1 \oplus s_2)\oplus t_2$

$C: r_2\oplus s_2\oplus( c\oplus t_1 \oplus t_2)$.

Your protocol is good (assuming an honest-but-curious adversary model). As DrLecter pointed out, each party will need to publish their sum of shares. To recover the answer, each party then simply xors all published values.


Can I safely replace XOR with ADD in a stream cipher? In a stream cipher, the bytes of the plaintext are usually XORed with the keystream to produce the ciphertext. Would there be anything wrong with adding the bytes instead (with overflow), if adding happened to be faster than XORing on a particular system?

On software platforms, bytewise adding will not be faster than bitwise XORing. It may be a bit slower, though, also this will be negligible with regards to the process which generated the stream (and, for that matter, will probably also be negligible with regards to the memory bandwidth).

On hardware platforms (FPGA, dedicated ASIC), addition is slower than XOR because of the need to propagate carries. A XOR is a simple layer of XOR gates, so it has minimal depth and minimal area; an addition requires more gates (so more area) and carry propagation over $n$-bit words requires a circuit of depth at least $\log n$, so the addition will induce more latency as well. The overhead will be probably limited for mere bytes, but it will never be as efficient as a XOR.

The only kind of architecture where adding would be somewhat faster than XORing would be an architecture which offers addition/subtraction primitives, but not XOR, or not as efficiently. This may be the case for some DSP, or possibly for some Javascript interpreters (in Javascript, numbers are thinly-disguised IEEE 754 floating-point values, and bitwise operations entail conversions to and from integer types). I still think that for most platforms (including recent JIT-able Javascript interpreters), the XOR will not be slower than bytewise addition.

As for security, bytewise addition is as good as XOR. Indeed, XOR is bitwise addition (XOR is the addition in $\mathbb{Z}_2$).


Count elements with a given order in the multiplicative group $n=pq$ (RSA) We know that the order of an element $a$ in the group $\mathbb Z_n^*$ is $k$ where $k|lcm(p-1,q-1)$ where p,q are distinct primes.

Something else i think we know is that the elements that have order $lcm(p-1,q-1)$ will generate exactly $\frac{φ(n)}{lcm(p-1,q-1)}$ different subgroups which may have common elements (in order to jointly generate all the elements of the group). Based on that, if the n was prime, we could easily count the elements of each order by doing $φ(order)$. (if it is prime, one element could generate all the others)

Is it possible to count how many elements have a given order?

For example: $n=5*7$

How many elements have order 6? (I know it's 6, but is there a generic way to find it?)

CRT could give an approximation in this case but you should still filter out the elements that may have smaller order that divides in this case 6 (1,2,3).

Here are the subgroups with order 12:

2,4,8,16,32,29,23,11,22,9,18,1
3,9,27,11,33,29,17,16,13,4,12,1
12,4,13,16,17,29,33,11,27,9,3,1
17,9,13,11,12,29,3,16,27,4,33,1
18,9,22,11,23,29,32,16,8,4,2,1
23,4,22,16,18,29,2,11,8,9,32,1
32,9,8,11,2,29,18,16,22,4,23,1
33,4,27,16,3,29,12,11,13,9,17,1

One interesting detail is that the generators for each group are present to exactly three other subgroups. For example, 33 is inside 3,12,17 subgroups. (each contains the other elements in positions m where $gcd(m, 12)=1$ so we have 4 permutations of each of the two subgroups)

With order 6:

4,16,29,11,9,1
9,11,29,16,4,1
19,11(-24),34,16,24,1
24,16(-19),34,11,19,1
26(-9),11,6,16,31,1
31(-4),16,6,11,26,1

Here, each generator is present in another subgroup

EDIT:

My second theorem seems to be little flawed:
I assumed that combining all the subgroups of order $lcm(p-1,q-1)$ would generate all the elements of the multiplicative group n. But as we can see from my example, they do not since they don't generate the elements 6,19,24,26,31,34.

Here are some good resources that could be useful mult. groups mod n and carmichael function.

It's not hard to compute, the number of elements with order precisely $r$ is:
$$F_{p-1, q-1}( \phi(r))$$
where $F$ is this function:
If the prime factorization of $r = r_1^{e_1} r_2^{e_2} ... r_n^{e_n}$ then
$$F_{p-1, q-1}(r) = F_{p-1, q-1}(r_1^{e_1}) \cdot F_{p-1, q-1}(r_2^{e_2}) \cdot ... \cdot F_{p-1, q-1}(r_n^{e_n})$$
If $s$ is prime and $e>0$, then $F_{p-1, q-1}(s^e)$ depends on $\gcd( s^e, p-1) = s^a$ and $\gcd( s^e, q-1) = s^b$
If $a, b < e$, then $F_{p-1, q-1}(s^e) = 0$ (i.e. there are no elements with that order)
If $a=e, b < e$, then $F_{p-1, q-1}(s^e) = s^b$
If $b=e, a< e$, then $F_{p-1, q-1}(s^e) = s^a$
If $a=b=e$, then $F_{p-1, q-1}(s^e) = s^e + s^{e-1}$
This allows us to compute the number of elements in all cases.


AES: Guess Password using the unencrypted text? I am using the same password for some encrypted files currently (I know this is bad practice, though), and I wonder whether an attacker could decrypt if one decrypted file fell into his hands.

Any good software should use PBKDF (a password based key derivation function) that uses a random salt. This salt is stored with the ciphertext and should be different for each ciphertext. As long as this is the case they key will be different for each ciphertext.

The best way an attacker can then attack your ciphertext (when stored on disk) is to iterate over the most likely passwords and perform the PBKDF. So the password and PBKDF together will provide the barrier that the attacker has to take. That is, if there are no other vulnerabilities to the crypto system, this is about the general case.

If you don't want to type a (different) password for each encrypt and if you want to use the same password each time, you might be better off using PGP encryption/decryption with a public / private key pair. PGP directly uses a public key for encryption and will request the same password each time to decrypt the private key, which decrypts the session key, which decrypts the data.


meaning of Reduce f modulo the order of the base point G I am trying to perform some math operations related to Elliptic curve cryptography, and came across this sentence: Reduce f modulo the order of the base point G. What does it mean?

First a preliminary: a base point $G$ on an elliptic curve generates a group of points on the curve such that every point in that group can be written as $dG$ ($d$ times $G$) where $d$ is an integer. This group is also cyclic in that for a certain value $q > 1$ we have that $qG = \mathcal{O}$, where $\mathcal{O}$ is the identity element, known as the point at infinity. This value $q$ is known as the group order. Reducing $f$ modulo $q$ is equivalent to calculating the remainder of dividing $f$ by $q$.

For standardized elliptic curves you won't need to calculate the group order yourself, it's usually included with the rest of the curve parameters.


Is it safe to use a secret salted hash of a public id for client to prove ownership of id to a server that knows salt but does not store ids? I am writing a peering server - the server assigns randomly generated public IDs to users, and I want users to be able to reclaim their ids in the future, but only to be able to claim ids that they have been assigned, not arbitrary ids or ids belonging to other users.

I also want to avoid storing any information on the server after its connection to a user closes.

I have limited knowledge of cryptography, but am thinking that the server can give the users their public ID and a secret produced by salting and hashing the id. To reclaim the id, the user would pass the server both the id and secret, the server would re salt and hash the id and ensure that it matches the provided secret.

Is this safe?  If so what hash function is appropriate, and if not is there a better approach?

Thanks!

You could do something fairly simple, such as

$UserSecret = Random()$
$UserID = HMAC(ServerSecret, UserSecret)$

Send the user the two values.  When he reconnects, he sends the two values back.  If re-calculating $UserID$ with the user's $UserSecret$ gives the same $UserID$ then that proves (to a high degree of certainty) that it's the same person that was given that ID before (assuming the $ServerSecret$ is still secret and the same value as it was originally).

The size of the ID value will need to be sufficiently large that the same ID is unlikely to be handed out to more than one person, since you're not keeping track of which ones have been used previously.

Using HMAC-SHA256 would give large enough values.  See the wikipedia entry for HMAC for an explanation of how it works.

You could also use an SRP-style verifier, which could then be used to do an authenticated key exchange as well.

User generates a random value $x$, and sends the server

$Verifier = g^x mod N$

(see SRP for more details on $g$ and $N$)

Establish a secure session using SRP with $x$ and $Verifier$ to generate a key. The server then calculates $UserID = HMAC(ServerSecret, Verifier)$ and sends that to the user.  The user saves the $UserID$ and $x$.

Later connections, do the same thing using the saved $x$, but server sends a hash (e.g. SHA256) of $UserID$ to the user.  The user verifies that the hash is correct (which authenticates the server), then sends $UserID$ (that it originally got) back to the server to prove it also knows it.


Very simple and minimal replay prevention scheme Suppose a desktop client communicates with an internet server program via HTTP requests.

I have a symmetric secret key shared between them used for encrypting/securing communication between them.

I also mention that communication is almost one-way i.e almost always it is the client that sends some data to the server and server returns no data to the client except reporting unexpected errors like decryption failures. In my program the responses of the server aren't even (still) encrypted (although i can implement it relatively easily if really necessary - tell me the reason to do so) because the client makes no important action/decision upon receiving thease error responses (any response other than empty string is regarded as an error and is just ignored (at most printed/logged)).

My app is not very serious/security critical. It is just a little private program (and somewhat experimental/educational and I don't want to go further from a point in its security because I don't have enough reason/priority/time for implementing more details). So please don't be stringent about non-critical details. for example I know that the shared/master key shouldn't be used directly and each time a new session key should be generated somehow, but nonetheless i am using the master key directly for every encryption forever. My intended security is the bare minimum that is absolutely necessary so that ordinary hackers cannot misuse it or read my private data in transit, assuming the client and server environments are out of their reach.

So far i have implemented encryption (AES128(CBC)+HMAC-SHA256), but it seems to me that replay prevention is almost necessary too (and implementing it isn't much work and doesn't need much modifications to my existing codes). So i want to add replay prevention too, but in the most simple way possible for my app and its minimal security requirements.

I thought of a scheme like this:

Client stores a counter initially at 0
With each request this counter is incremented by one and sent along other data (counter is encrypted too or at least authenticated by MAC)
Obviously, server stores the last counter value(plus 1) it received and rejects every later request with a smaller counter value.
When client counter resets to zero again, e.g because of a reinstallation, thus it sends a request with an invalid counter to the server, server rejects and responds with an error message to the client and tells in this response the minimum counter value expected.
Client then sets the counter to the value reported by the server and sends the request again (Seems to me that the error response/counter value returned by the server doesn't even need to be encrypted/authenticated, because any other counter value will be rejected by the server again).

And, yes I am aware of the problem of counter variable reaching the end of its range (maximum) and reseting to 0. I will take care of it later (seems a simple problem to sovle)

Is this scheme correct in your opinion?

The main part of the scheme works, but your reset mechanism in the client has a potential weakness:

First, the attacker can easily get the information about what is the next expected counter, by simply replaying any old message and inercepting the answer.
Then, at some counter $c$, the attacker intercepts the message $m$, and saves it. If your answers are just unencrypted and not signed, he can easily send your client a fake-reply.
All subsequent messages are also intercepted, until the client is shut down.

And now the client is restarted, and does the "ask for the correct counter" by sending a message with counter 0. The return value will be something smaller than $c$, because the server never received that value or anything higher. At this point, the attacker could switch the new data for the old data instead. That isn't a replay attack, but the client might think he send something different than what was received at the server.

More complex, the server could actually keep track of the counter, especially if it is always increased by 1. And then replace new information with old ones.

The problem with your idea is, that the counter only changes after receiving a message. But if no message is delivered, the sender might send several messages with that same expected value in the counter. And then the attacker can choose which one he wants to deliver to the server.

A common mechanism to counter replay attacks is to have a challenge-response mechanism: The client sends a hello-message to the server, the server replies with a random challenge, and then you use that number in the response.


Zero knowledge proofs for a Merkle Tree Say I have a publicly available Merkle tree, and I want to prove the existence of a leaf (containing a number, maybe) in the tree.
I could give the path along with the siblings, for a normal Merkle proof, but this reveals the leaf itself.

How can I do this in zero knowledge, i.e., proving that the leaf exists, but not revealing which leaf?

The "path" is only a witness for your proof; you don't actually want to give the path to the verifier. Turns out that going from a NP-problem with witness to an actual zero-knowledge proof is not that trivial.

What you could do: one of your leaves $L_1, \dots, L_{n}$ has the value of your commitment $x$. You might write something like

$$\bigvee^{n}_{i=1}\left(L_i=x\right).$$

This is a satisfaction problem, so it's suited to be fed in a bunch of ZK libraries.

Lately, I've been playing with rank-1 constraint systems (r1cs), such as provided by libsnark or in a little time by dalek's ``bulletproof'' library. These provide non-interactive, fast, compact zero-knowledge proves.

You said your leaves could contain numbers. This translates very nicely in a r1cs system!

$$\prod^n_{i=1}(L_i-x)=0$$

You simply prove that one of the roots of the above polynomial equals zero, which is true when $x$ represents a leaf.


Is the IEEE 1363.1 standard of NTRU post-quantum secure? I have a question regarding the IEEE 1363.1 standard for NTRU with padding, which offers CCA security. Does the IEEE standardized implementation offer post-quantum security as well?

Also, what are the major differences between the IEEE 1363.1 NTRU standard vs. the NTRUEncrypt NIST PQ submission here: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

Or, is the NTRUEncrypt submission to the NIST PQ competition exactly the same as in the IEEE 1363.1 standard? Is there a difference in the parameter sets to enable PQ security vs. the parameters in IEEE 1363.1?

Is it correct to claim that the IEEE 1363.1 is PQ secure as well?

Thank you!

what are the major differences between the IEEE 1363.1 NTRU standard vs. the NTRUEncrypt NIST PQ submission

The only differences would be the parameters that are standardized. This answer gives one parameter set, specifically EES1087EP2. Unfortunately, the IEEE Std 1363.1-2008 document itself is behind a paywall, so I am unable to view the other parameter sets. It seems like at least some of the parameters are the same. In particular, NTRU-743 from the design document submitted to NIST has $N = 743, q = 2048, p = 3, d = 247$ (see table 1), which is the same parameter set as one standardized in 1363.1, according to an analysis of parameter sets (see table 3).

On the upside, there are public implementations which use the standardized parameters, so those can be consulted. It looks like the version of NTRU submitted to the competition comes with only a few parameter sets for evaluation, which may change later on in the contest. The IEEE, on the other hand, standardizes a large number of parameter sets for NTRU.

  Is there a difference in the parameter sets to enable PQ security vs. the parameters in IEEE 1363.1?

The parameter sets are chosen to maximize security, not to maximize post-quantum security in particular. Secure parameters will be secure against both classic and quantum algorithms. I do not believe you can construct parameters for NTRU that are secure against classical computers, but insecure against hypothetical cryptoanalytic quantum computers.

Table 5 in the above-linked design document compares the lattice strength for various parameter sets under the best known classical and quantum sieving algorithms.

  Is it correct to claim that the IEEE 1363.1 is PQ secure as well?

Yes. All unbroken versions of NTRU use lattice-based cryptography, which involves mathematical problems that are not known to be solvable using a quantum computer. If the IEEE version is PQ secure, then the NIST PQ submission should be as well, and vice versa.


FIPS 140-2 Compliance Testing Is there any tool which can be used to test that implementations follow  FIPS 140-2 Compliance ?

No, there isn't. There are too many different systems out there to make a generic tool.


Ballot box with multiple parties. All can read it, or none can read it I am trying to create a decentralized moderation system for the game Diplomacy, a game for seven players. In each round of a face-to-face game, each player writes their moves on paper then puts it in a box; all moves are read at once. The game was popular as play-by-mail: you mail your moves to a magazine publisher, who aggregates all moves and publishes game updates to everyone. In each round of an online game, each player sends their moves to a third-party "moderator", who then aggregates the moves and relays all moves to all players. The players must agree beforehand to a third-party moderator.

I would like to create a decentralized system without the need for a moderator. Each player can run a web-accessible server. Each round, each player will broadcast their moves (encrypted somehow) to all other players. When all players have broadcasted their moves, only then can all players read the other players' moves.

Initially, I thought of using something like the Three-pass Protocol: Player A writes a message, puts it in a box with Padlock A, and sends it to Player B. Player B puts Padlock B on the box and returns it to Player A. Player A removes Padlock A and returns the box to Player B. Player B can now remove Padlock B and read the message.

The players would be arranged in a ring: Player A always passes messages to Player B, Player B always passes messages to Player C, etc. So each message ends up in a box with seven padlocks on it. Only when it has gone around the entire ring can all the players read the messages.

But this doesn't solve the problem of noncooperation: On the sixth pass, Player D can stop sending messages to Player E, read everyone else's moves, and not cooperate further.

Player D and Player F can also choose to cooperate with eachother, and keep Player E out of the loop. That would be bad for Player E.

In a game like Diplomacy, it is not acceptable to allow one player to read any other player's moves without all players reading all moves.

Another thought is for each player to privately send their moves, locked in a box, to each other player (via private-public keys). When a player receives the box, then that player broadcasts to everyone, "hey everyone, player X sent me a box which hashes to abc123!". When everyone finds that everyone else has received all other boxes, then they can swap them back. This allows some player to lie to everyone else, but the downside is "nobody gets anything".

I think I'm on the right track here, but I'm not sure. Is this a correct way of thinking about the problem? Has this already been done (I can't find another solution already)?

See malleability and commitment schemes.

You are apparently looking for a collusion-preserving implementation of simultaneous broadcast.

By letting each processor control at least one player and directing each processor to choose a random bit for each of its players and outputting the xor of all players' random bits, the resulting coin-flipping protocol is as fair as the system. $\:$ Thus, one smacks straight into this paper's impossibility result.

The ways I know of to get around that impossibility result are:

$\;$ time-lock puzzles, with which the amount of work needed for cooperating players

$\;$ to read the messages is "not too much more" than the amount of work needed for

$\;$ adversarial players to read the messages, and in both cases; the relevant work only

$\;$ needs a small amount of memory and is not (known to be feasibly) parallelizable

$\;$ partial fairness, so that when more than 1/3 of the players are cooperating

$\;$ (in particular, when there are only 2 players) and the number of possible messages is small,

$\;$ cooperating players get "not much less" information than adversarial players get

$\;$ having lots of moderators that only need to be contacted if a player stops participating

$\;$ before or during a reveal phase, each of whom is assigned a small positive integer weight

$\;$ (presumably less than the threshold I'll mention later in this text-block, otherwise there's no point

$\;$ in using more than one moderator), so that if [the sum of the weights assigned to adversarial

$\;$ moderators] is less than [the threshold chosen before the reveal phase begins] is less than or

$\;$ equal to [the sum of the weights assigned to the moderators who appear to be cooperating]]

$\;$ then the "All can read it, or none can read it" property holds

.
(A moderator that merely cannot be contacted or has lost its private key

is neither adversarial nor one who appears to be cooperating.)

To emphasize, even if all moderators are adversarial, the only thing they can do is let players

who stop participating violate the desired "All can read it, or none can read it" property.

In particular, each message must still be chosen independently of the other messages.

It may be that there are other ways around that impossibility result; in particular,

I don't see a reason why the 1/3 threshold should be critical for partial fairness.

Even if there aren't, it appears to me that one could combine the "partial fairness" option with the

"lots of moderators" option in a way that is at least as good as the latter but also provides partial fairness when the latter's inequalities are not too far off and the number of possible messages is small.

Note that I have no idea which of the three options I

described are compatible with being collusion-preserving.


Possible to detect if a message is PGP encrypted/signed (ciphertext) Let's say I have a text field somewhere (i.e. an interactive user submitted text field on a PHP script, or a console application. Basically anything that accepts user input.)

How can I detect if said text field contains only a PGP encrypted/signed message? I could just fingerprint the BEGIN PGP ENCRYPTED MESSAGE header/footer but I was hoping there was a more accurate solution.

I wouldn't need to decrypt said message as I wouldn't control the private key, I just need to check if the message is a PGP encrypted message in the proper format, so to speak.

The only possible answer to this is to check out the OpenPGP format and see if the message adheres to that format. You may need to build in some mechanisms to filter out tiny mistakes or extensions in the message though.

As Open PGP is, well, open, there should be plenty libraries that perform this parsing for you. Library recommendations are off topic here but you should be able to find one to your liking using a search engine.


What are some good examples of modifying crypto where flaws are not really obvious? I run into some developers from time to time who sometimes try to modify crypto which I end up saying along the lines of "Don't modify crypto." Usually, the question I get is - "OK, tell me why is this bad? How can this be broken?"

My rule of thumb is usually that cryptographic primitives are supposed to be used they way they are told. A slight modification in those primitives or assumptions can break cryptography in a way that cannot be foreseen. However, I am not that really good with spotting flaws on spot. Plus, finding flaws every time I face such modifications is time consuming. I generally like to explain this to people using examples. How can I explain people that they should not modify cryptographic primitives?

One of the best examples that I know of is "chained CBC" as used in SSL. This looks exactly like regular CBC. The only difference is that instead of sending a new IV with every message, the IV is taken to be the last ciphertext block of the previous message. This is much more efficient since for small packets you don't need to send a large IV each time. In addition, you don't need to generate new randomness for every message (and rely on the randomness on the machine). This looks just like CBC since a single long message exactly has the "chain" effect.

However, this minor modification (and major optimization) is not secure, and resulted finally in the BEAST attack on SSL.


random access stream cipher Some time ago I was working in a pet project for a type of database engine. And I thought about securing the data in disk with encryption.. and since the main code was already developed.. I had a few requirements..

a simple stream class that I could hook instead of my file stream had
to support random access (both read/write at random positions)
be able to work at any byte position (since the data might not be aligned)
encrypt/decrypt only the requested data, not the all file,(because the file maybe several MB)
fast encryption/decryption, since this was for a database system

nowhere on the web I found information about this, or implementation of such code.
Normal stream ciphers don't support random access/lookup, and block ciphers require the data to be aligned and in fixed blocks..
So I thought about developing my own. I do know that developing your own encryption is always a bad choice.. but this was kind of theoretical exercise..

So I would like to present you the code.. just to see how far of I am from a security point of view

First the stream is initialized with a password.. but that password is not used for the encryption itself.. it is used as a seed to scramble an array of 256 values in hope of of increasing the key space

public CipherStream(String sKey,Stream oStream)
{
    _oStream = oStream;
    //initialize key space
    _oVector = new byte[256];
    for(int i = 0; i <= 255; i++)
    _oVector[i] = (byte)i;
    //shuffle the keyspace
    for (int i = 0; i <= 255; i++)//shuffle the box
    {
        //shuffle this item with other
        //other is chosen by char(i) of password
        //and the currently shuffling vector(I)
        // this means that even repeating passwords 'aaaaaa' will produce random results
        int j = ((sKey[i % sKey.Length]) + _oVector[i]) % 256;
        byte cTemp = _oVector[i];
        _oVector[i] = _oVector[j];
        _oVector[j] = cTemp;
    }
}

after this all we have to do is choose the cipher byte for the position we are trying to read/write from.. in my implementation I used xor, witch I know is not the most safe.. but that is can be changed and is not the core of the algorithm..

public override void Write(byte[] buffer, int offset, int count)
{
    long nPosition = this.Position;
    for (int i = offset; i < count; i++)
    {
        byte oPlain = buffer[i];
        byte nKey = GetKey(nPosition);
        byte oCypher = (byte)(oPlain ^ nKey);

        buffer[i] = oCypher;

        nPosition++;
    }
    _oStream.Write(buffer, offset, count);
}

the 'key' to the byte is chosen from the key vector dependently from the position we are trying to access.. calculations are done so that there are no repetitions and the chosen value is as random as possible

private byte GetKey(long nPosition)
{
    byte nOffset = _oVector[nPosition % _oVector.Length];
    byte nOffset2 = _oVector[(nPosition / (nOffset + 1)) % _oVector.Length];

    int nDif = nOffset - nOffset2;
    if (nDif < 0)
        nDif += 255;
    byte nKey = (Byte)(nDif % 256);

    return nKey;
}

I did try to render the stream as a bitmap.. just so make sure no patterns where obvious.. and did some fine tunning there.. and it seemed ok..

the best I can describe this algorithm is a 'deterministic predictable pseudo-random generator'
where I can just ask 'give me the nth random number', and the seed is a 2048 bit vector
that is initialized randomly with a password..

how far am I from a solution? Is this completely insecure? or there is not even point of trying because there is no solution for this 'random access stream'  problem?

The idea

  'deterministic predictable pseudo-random generator' where I can just ask 'give me the nth random number'

is already known, and there are some stream ciphers that work like this (like CTR mode of a block cipher, or the Salsa/ChaCha family of stream ciphers).
Usually they don't produce a single byte, but some larger block of consecutive key stream bytes, which is more efficient if you don't have single bytes to encrypt, and (as mentioned by user4982's answer) doesn't restrict you, as you don't have to use all these key stream bytes to encrypt/decrypt your piece of data.

I won't look at your specific cipher (it is too much on the code level for me), but it is probably not a secure one.

The idea itself (even when implemented with an perfectly secure stream cipher) has a problem when used for random access file encryption: You will be having (at several points of time) different pieces of data encrypted with the same piece of keystream, which then leads to the two-times-pad problem, if a potential attacker could look at your encrypted file at different points in time.

You'll need to reencrypt larger blocks with a new initialization vector to avoid this.


Is using Ed25519 parameters in ECDSA safe? I recently discovered the Curve25519 key exchange lib and the Ed25519 signature lib. Due to the speculations about NIST-designed curves, there is a chance that I ditch them and use the curves above instead.

If I take the curve parameters from these two libs and use them in ECDH/ECIES and ECDSA respectively, will it be safe? If yes, is it as safe as if I used Ed25519 directly?

ECDH is the same as what Curve25519 uses mathematically. The issue is that converting Curve25519 into Weierstrauß form is a bad idea, because it introduces issues relating to the potential failure of the addition law, which are difficult to address well. Keeping the curve in Montgomery or twisted Edwards form finesses these difficulties.

ECDSA has issues related to randomness and is slow. It will be secure, but Ed25519 has many advantages; especially with batch verification.


Is SHA-1 safe for signing ECDHE parameters? Is using the SHA-1 algorithm insecure for hashing the ephemeral ECDH public key in the signed_params structure?

There are some worrying articles about using SHA-1:

Phasing Out Certificates with SHA-1 based Signature Algorithms
Gradually sunsetting SHA-1

My server sends the following Server Key Exchange message for TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (0xc02b).

TLSv1.2 Record Layer: Handshake Protocol: Server Key Exchange
    Content Type: Handshake (22)
    Version: TLS 1.2 (0x0303)
    Length: 148
    Handshake Protocol: Server Key Exchange
        Handshake Type: Server Key Exchange (12)
        Length: 144
        EC Diffie-Hellman Server Params
            Curve Type: named_curve (0x03)
            Named Curve: secp256r1 (0x0017)
            Pubkey Length: 65
            Pubkey: 0...
            Signature Hash Algorithm: 0x0203
                Signature Hash Algorithm Hash: SHA1 (2)  <<<=============
                Signature Hash Algorithm Signature: ECDSA (3)
            Signature Length: 71
            Signature: 3...

Should I change it to use SHA256 like server certificate? Or is it safe since it is used to sign the ephemeral key?

SHA-1 is still thought to be secure whenever collision resistance isn't required.

The hash is both used for signing certificates and ECDHE public keys. There's however a difference with regard to collision attacks. It is possible for an attacker to attack the collision resistance with certificates by getting their own certificate signed by a CA. In ECDHE however the attacker shouldn't be able to control the ECDHE public key parameters that are signed.

So, while I wouldn't recommend using SHA-1 in new applications if you can just as well use another hash, TLS is what it is and this kind of a cipher suite is still thought to be secure.


Does it matter if I publish only publish good or bad MD5 hashes after recovering from a hack? (This question is a follow-up from another question I asked about MD5, which is why I'm insisting on using MD5 in this question as well)

My imaginary Linux distribution, Sushi Linux has had a big incident.  Hackers gained access to the website and replaced the download link with a link to an infected ISO file.  The website was taken down, and a backup was restored, after making sure that this cannot happen again of course.

Still, my logs show that the infected ISO file was downloaded by a lot of people.  I want to give them easy instructions to check whether or not they are infected.

Both the infected and the uninfected ISO file have the same size, but they have different MD5 sums.  My religion does not recognize any other hashing algorithm than MD5, so that's what I'll use in 2019.  I know about the weaknesses but since no other hashing algorithm exists I'll use it anyway.

My users are afraid that they installed Sushi Linux using an infected ISO and they ask me how they can check.  The ISO file they can download from my website today is the uninfected one, and I've fixed the problem the hackers used to get in last time, they're not getting in a second time.  However, my users want a way of verifying their local file without downloading a new one (most Sushi Linux users are on 56K modems so they don't want to download it again).

I've considered publishing the MD5-sum of the infected ISO, so that users can identify their local ISO as being the infected one, and I've considered publishing the MD5-sum of the correct ISO, so that users can identify their local ISO as being the uninfected one.  My webmaster is hourly, so I can only publish one hash.  Does it matter which hash I publish for users to be able to check if they have the infected file or the real file?

Does it matter?  Yes: there's a qualitative difference in the types of attacks that would break your system.  The elephant in the room, of course, is MD5, but let's examine the qualitative difference between the attacks first.

It is almost useless to publish the bad hashes, because as an adversary I could just distribute different versions to everyone.  A million downloads?  A million different ISO images, uniquely tailored with a special brand of malice.

What about publishing the good hashes?  This is what you should do anyway, but you're restricted to MD5.  How can I break this?

I'm an evil developer, and I play the long game.

I make three versions of a software package:

the good one does what it is advertised to do which is something useful
the bad one does something harmful noisily, like uploading credit card data to a bad place
the sneaky one does something harmful quietly, like slowly making your screen look blurrier and blurrier over the course of a month, or silently disabling disk encryption

There's a sneaky catch: the good one and the sneaky one collide under MD5, but the bad one does not.
I publish the good package under my name, and the curators closely scrutinize it to audit the code and confirm it does what it claims.  (Yeah, right!)
I hire someone, who lives in a closet under the stairs in the Ecuadorian embassy with nothing but his cat and his colossal narcissism to entertain himself, to break into the package servers and upload the bad package on one distribution server, and the sneaky package on all the other ones.
Someone notices the network traffic from credit card uploads and raises an alarm.  The curators publish the good package's hash for everyone to verify their systems.
Everyone freaks out and stampedes to upgrade the software simultaneously.

Now everyone has the sneaky software, and if they check the MD5 hash they will rest assured that it's the good package's hash.

You could say this is convoluted.  True, it is convoluted: I wouldn't try to pull this plan off, but that's in part because I'm not really evil.  Evil people who are dedicated will use a convoluted plan if it works.  A single NUL byte buffer overflow can, through a convoluted series of steps, be turned into remote code execution.

So what do you do?  In your rush to rectify the poisoned ISO image, you could commission a careful multinational study of the technical capabilities of everyone on the planet who might be your adversary, and determine their risk aversion, technical sophistication, logistical planning, and chutzpah to see whether they would be capable of pulling off any attack in this class.

But that might cost a pretty penny and it might take a bit of time.

Fortunately, there's a much cheaper way to get a high degree of confidence that you thwart any plan of this sort, without having to study how convoluted the adversary's actions might have to be and whether that level of convolution is feasible.

Don't do something stupid like using MD5.  Use a modern collision-resistant hash that isn't broken instead, like SHA-256, or SHAKE128, or BLAKE2b.

If you absolutely must use MD5 and MD5 alone, you could publish $(r, \operatorname{MD5}(r \mathbin\| n \mathbin\| m))$ where $r$ is chosen uniformly at random independently for each file (maybe as the HMAC-MD5 of $m$ under a secret key), $n$ is the name of the file including the version (encoded prefix-free, maybe with a length delimiter), and $m$ is the content of the file.  (Of course, if the adversary knows or can predict $r$ before they choose $m$, then it's back to the same issue as standard MD5.)  But chances are, it'll be much easier for you and your users if you just use a non-broken hash.  SHA-256 has been available for a decade and a half.


Which attacker model is weaker? IND-CPA or OW-CCA? I know that IND-CPA is a security goal, which is defined as the inability of an attacker to distinguish two ciphertext of some arbitrary chosen plaintexts.
Unfortunately i havent found a good definition of OW-CCA, but i assume it has something to do with an Oracle and Chosen Ciphertexts. So in my understanding OW-CCA is defined as the inability of an attacker to find out the key by chosing an arbitrary number of Ciphertexts and letting the Oracle decrypt these.
In IND-CPA the Attacker has the ability encrypt chosen plaintexts, which basically anyone can do. In OW-CCA, the Attacker can reverse the ciphertexts to plaintexts and is dependant on the oracle
Since the attacker has less power in IND-CPA the security goal is more easily achieved, which makes the attacker model weaker.
Is that correct?

It is not difficult to build examples to show that the two notions are incomparable, in the sense that there exist schemes that are IND-CPA but not OW-CCA, and there exist schemes that are OW-CCA and not IND-CPA.
For example, take any public-key IND-CPA scheme, and modify it so that ${\sf Enc}_{pk}(sk) = pk$, implying that ${\sf Dec}_{sk}(pk)=sk$. I argue that this scheme is still IND-CPA, since it only reveals $sk$ in the case that a decryption query of $pk$ can be issued. Since there is no decryption oracle, this is safe. However, this is clearly not OW-CCA for any definition, since given a CCA oracle, it is possible to obtain the private key $sk$.
Next, take any OW-CCA scheme with deterministic encryption. (For my answer to be complete, I need to argue that such a scheme exists, but I'll leave that to you.) It is clear that this scheme is not IND-CPA since if you encrypt the same message twice, you get the same ciphertext.


Does repeated xoring of the (same) key K lower the entropy of K? If a symmetric encryption key $K$ has been generated by some recommended (NIST for example) RBG then we should have a key with high entropy.

But if we xor other bit-strings (e.g. IVs, other keys, etc.) to $K$, how does this affect the level of the entropy of the resulting bit-string?

Specifically, how is the level of entropy affected if we apply:

$K \oplus K^*$, where $K^*$ has the same/similar level of entropy as $K$.
$K \oplus IV$, where $IV$ has a much lower entropy than $K$.
$K \oplus C$, where $C$ is some ciphertext output that is (repeatedly) fed back into the cipher to begin a new round.

In short, I am interested in the effects of entropy levels when a 'strong entropy' bit string is xored with a 'weak entropy' bit string or another 'strong entropy' bit string.

Related to Q3, I wonder how many times an output can be xored with the same key before entropy is lowered (assuming that happens at all). We assume the output $C$ is different each time.

It seems this cannot happen because the output $C$ of a cipher should necessarily be unpredictable, but that is on the assumption that xoring two high entropy bit strings will always retain a high entropy.

Is there a simple mathematical way to show entropy is retained or lost when two bit strings are xored?

If I take a strong key K of length $n$ taken from a good source of randomness, it will have $n$ bits of entropy and will be independent of anything else (not derived from it).

If we later Xor it with a weak password K* for instance or something else we still have the same $n$ bits of entropy.

Each bit is still uniformly random and independent of each other. Even if K* bits were biased and correlated.

It is easy to see with an example. If we Xor a random key with all zeros, we get the same; if some bits are 1, it's just a negation, and negating a uniformly random bit is still uniformly random. Also, correlated bits won't make a difference. If I negate every other bit, or follow some other pattern, it makes no difference.

However if you XOR with something dependent on the key, all bets are off, and you could end up with 0 entropy, for instance, by Xoring with itself.


Can an RSA public key be generated without ever knowing the factors? Context: http://blog.cryptographyengineering.com/2013/12/a-few-more-notes-on-nsa-random-number.html

Assume I wanted to use RSA as the basis for a hash function or DRBG. Also assume that my construct would be insecure if someone were to have the private key. Is there any way generate the a usable public key to be used such that it is provably just as hard for me to generate the private key as it would be for anyone to do so?

I'm willing to take for granted:

the existence of a suitable source of nothing-up-my-sleeve numbers
the availability of significant computational resources.

The best idea I've come up with would depend on the ability to prove a lower bound the the size of the smallest factor in a number (e.g.: an $N$-bit number where all factors are at least of size $N*0.49$-bits) with significantly less work than it takes to actually factor it. (That and the ability to find such numbers.)

Unless you relax the restriction to allow for multi-party key generation where, if all the generating parties collude, the key can be recovered, no.

You can create something that operates like an RSA modulus. This was first proposed for use in cryptographic accumulators by Sander in "Efficient Accumulators without Trapdoor Extended Abstract".  The idea is to create a number that has at least two large prime factors that are unknown to anyone. It's known as an RSA unfactorable object (RSA UFO) and as far as I know, it's security for use in encryption or signing hasn't been thoroughly examined.

Those issues aside, the problem is the solution is by no means practical. For something with the security of a 1024 bit RSA modulus/key, you would need a 40,000 bit RSA UFO.


if a hash is difference-unpredictable, will it keep unpredictable given an offset? Let $H(k,m)$ an universal hash function that is difference-unpredictable.

Let $\mathcal{A}$ be an attacker who sends tuples $(m_0, m_1, \delta)$, and $\mathcal{A}$ wins the game if one of the tuples satisfy $H(k,m_1) -H(k,m_0) = \delta$.

$H$ will be difference-unpredictable when the chance of $\mathcal{A}$ win is negligible.

Suppose $H$ is difference-unpredictable, how can I show that the function $H'((k,x),m) = H(k,m) + x$ will also be?

Both functions' image is all naturals smaller than a given prime $p$, one can think of the functions like $H(k,m) = (...)\bmod p$.

I think the proof remains on this argument:

the attacker chooses $(m_0, m_1, \delta)$
let $H(k, m_0) = h_0$ and $H(k, m_1) = h_1$
let $d$ be the "wrapping" distance from $h_0$ to $h_1$, that is:

$d = h_1 - h_0\;$ if $\;h_0 \leq h_1$
$d = p - h_0 + h_1\;$ if $\;h_0 > h_1$

If $H'$ only offsets $h_0$ and $h_1$ by $x$, the "wrapping" distance will be the same and it will give no better chance for the attacker to guess a difference change in the results and his chance will remain negligible.


Has anyone seen a stream cipher being used for FDE So I am a newbie to this. Has anyone experimented implementing a stream cipher for full disk encryption?

EDIT

With the caveats that come with using a stream cipher over a block cipher of course! I am thinking in the context of mobile storage. I keep reading about these block ciphers but never stream ciphers.

The problem with full-disk encryption is that you don't want to "waste" space on authentication tags (because it would result in odd sector sizes or in a large latency / overhead on-disk).

So we can't have tags, but also don't want to completely give up on the nice features authentication offers, especially the fact that you can detect manipulation. With stream ciphers this is about impossible, because an attacker can change data at bit-level granularity and eg surgically implement a virus on the drive if he knows a file that gets automatically executed at system launch.

Now block-ciphers could make this much harder if you used modes which effectively turn whole disk sectors into blocks which where one bit-flip would destroy (i.e. randomize) the entire plaintext. Unfortunately these modes have computational overhead and thus aren't used.

What we actually do is encrypt each block individually with a specific "tweak"-value for this block which gains us these three properties that we wouldn't have with stream ciphers:

If you change a bit in the ciphertext, 128 bits of plaintext get changed
No matter how much you know about the underlying plaintext, changing bits in the ciphertext will result in different, unpredictable gibberish plaintext each time
You don't have to worry about IV/Nonce management which would be a major headache, because you'd have to change the IV for each sector update and storing the IV has the same problems as with tags, generating it from the sector index has the problem of IV re-use which usually leaks a lot of plaintext-information and incorporating a usage counter has the overhead of having to try different values or storing a counter which is back at the first problem


Which multiplicatively homomorphic encryption scheme supports encryption of 0? I want a multiplicatively homomorphic encryption scheme that supports encryption of 0 (e.g. Elgamal doesn't support).

I also want the multiplication to be operated on the ciphertext of 0, i.e., if one of the ciphertexts is encryption of zero, the product is also encryption of 0.

Gentry's recent work highlights both FHE and SHE with and without bootstrapping easily found on Google Scholar. The open source code on Github is getting closer to reducing the associated complexity. IMB and Microsoft have a myriad of code and papers on the subject.

Having said that what you are proposing has never been done before, but here is one helpful papers that may assist you depending on your commitment:

http://eprint.iacr.org/2011/607.pdf

It does not solve your issue but it does present some helpful side points that may assist you if you read it enough.