How to encrypt a string and decrypt a string but public can never figure out how to encrypt/decrypt a string On my website I display an image. To generate this image, it require a string parameters. For example the string 1234,2423,1231 as the parameter.
Anyone can use my API (no authentication required). For example example.com/generate?param=1234,2423,1231. That is how my API works right now. To generate a different image, all you have to do is provide different numbers and different amount of numbers, like 2342,2423,234.
However, I do not want people to be able to keep generating images by themselves by simply changing the numbers. So if I encrpyt the parameter and then let the user load the image, they would never know how to generate an image themselves. So an example of an encrypted API request would be example.com/generate?param=s97dgfubYVd80fzhgdfufg0894rf which would correspond to example.com/generate?param=1234,2423,1231.
The add on to this problem is, I tell the user "we are going to generate an image with the parameters 1234,2423,1231. Here is the API link to generate this image: example.com/generate?param=s97dgfubYVd80fzhgdfufg0894rf".
So what encryption method can I use.

If I understand your question correctly, I (the user) know the image s97dgfubYVd80fzhgdfufg0894rf was generated from the string 1234,2423,1231, but I should not be able to craft another valid parameter.
On the server side, you need to turn the parameter back into 1234,2423,1231.
You have two basic options (and likely more):

with a database available on the backend: just generate a UUID and have a database entry matching 1234,2423,1231 with the image UUID.
without per-image DB entries: encrypt the string with authenticated encryption to provide privacy and data integrity

The former is simple but at the cost of storage. The second means being very careful with how you handle the keys, IVs, and authentication tag sizes.
One algorithm you can use is AES-GCM which provides the following:

given a string, the user cannot generate the corresponding parameter (that's the AES part)
the user cannot generate a random parameter and have it decrypt into a valid string (that's the GCM part)

You seem to only be asking for the first part but the second part is equally important or users could be DOSing your service by submitting random parameters.
It doesn't have to be AES, any modern authenticated encryption mechanism that works for the data sizes you are talking about will be acceptable.


On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the multiplicative group of a finite field ($F^*$) is cyclic so there is a generator of this cyclic group, call $g$ and we write $\langle g \rangle = F^*$. Now every element of $F^*$ can be written as powers of the generator as $x = g^i \in F$ for some positive integer $i$. The identity is $g^0$. In this way, the multiplication is easy
$$\text{let } a,b\in F, \text{ and } a = g^x, b = g^y \text{ then } a\cdot b = g^{x+y}.$$ The bonus is the fact that the discrete log is easy since we tack the elements by the generator's power but the addition seems hard. $$a +b = g^x + g^y = g^z, \quad z =?$$ Questions;

How hard the addition?
Are there any cryptographic scheme that uses this hardness?

The term used for the function $Z(\cdot)$ defined by
$$
g^{x}+g^{y}=g^{x}(1+g^{y-x})=g^x g^{Z(y-x)},
$$
in coding theory literature is Zech's logarithm. So for your formulation $$z=x+Z(y-x)=y+Z(x-y).$$
It is no more than the DL of $(1+g^{x-y})$ and is believed to be as hard as DL.
In coding theory it is normally considered for even characteristic groups $G=GF(2^m)^\ast$ in which case it is actually just the DL composed with a permutation $\pi$ of order 2 in the additive exponent group $\mathbb{Z}_{2^m-1}.$
I seem to recall Odlyzko mentioning it in a survey on DL in early 1990's. In any case, I don't know of it being directly used in cryptographic schemes, but others might.


Text encrypted with key1, key1 encrypted with key2, meaningful? Simplified Question
Does it make sense from a security / cryptographic standpoint to encrypt a text in the following way:

create only one AES key K_Azure
create new random key K_Text1
encrypt Text1 with K_Text1
encrypt K_Text1 with K_Azure
store [ E(K_Text1), E(Text1) ] in the same storage
store K_Auzre somewhere else

Context
The DataProtection in asp.net core provides a mechanism to encrypt and decrypt some data.
The keys are stored in a key-value-pair format of (KeyId, XML), where XML provides some metadata and the actual encryption key itself.
The part of the XML where the key is stored can be encrypted using various providers, my question is about the ProtectKeysWithAzureKeyVault (link) implemented here.
Protecting the keys
With ProtectKeysWithAzureKeyVault a data encyption key (let's call it TEXT, because in our case this will be just a text) is encrypted using a random new generated key (let's call it K_Text). K_Text will be encrypted using a single key in the AzureKeyVault (let's call it K_Azure).
The encrypted TEXT and encrypted  K_Text are saved in the same store (in the same XML which is saved in in a SQL or file or we...).
To summarize
+------------------------------------ --------+          +---------+
| Database                                    |          | Azure   |
| ----------------------------------- --------|          | --------|
| Id1, E(K_Azure, K_Text1), E(K_Text1, TEXT1) |          | K_Azure |
| Id2, E(K_Azure, K_Text2), E(K_Text2, TEXT2) |          + --------+
+ ------------------------------------ -------+

E (KEY, TEXT) = encript TEXT with KEY

My question
Is there any reason why it does not encrypt the TEXT directly with K_Auzre?
Notes

AES is used to encrypt everything as far as I know in this context

Update
I think Elias is right, K_Azure is kept in separate hardware and you can not get it.

Just two ideas:

If you have some kind of hardware security module (HSM) to protect your K_Azure you might want to avoid using that HSM to encrypt large volumes of data. But since you cannot get the K_Azure out you generate a new key and use that.
If you don't have other randomization in your AES mode you will leak equality information if you use the same key for the same data.


Multiplicative inverse in ${GF}(2^4)$ I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$
(NOTE: the values in the table need to be in hexadecimal format, hence I'll be using both polynomial and hexadecimal notations in the question henceforth).
Now, I was able to compute multiplicative inverse for the first row of the matrix i.e. (00,01,02,03). The inverse of 03 or $(x+1)$ comes out to be 0E or $(x^3+x^2+x)$.
However, when I try to compute the inverse of 10 or $x^4$, it again comes out to be 0E or $(x^3+x^2+x)$. Is it possible that two polynomials have exactly the same inverse? If not, I'm unable to figure out where I'm going wrong. Please help.

The Galois Field $\operatorname{GF}(2^4)$ (also represented $\mathbb{F_{2^4}}$) contains $16 = 2 ^4$ elements. The formal definition is;
$\mathbb{F_{2^4}}$ is the quotient ring $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ of the polynomial ring $\mathbb{F_{2}}[X]$ by the ideal generated by $(x^4 = x + 1)$ is a field of order $2^4$.
We can list the elements of $\operatorname{GF}(2^4)$ on the polynomial representation with the defining primitive polynomial, namely $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ where $a_i \in \operatorname{GF}(2)$ for $i=0,1,2,3$.
$\operatorname{GF}(2^4)$ is a Field therefore every element has a unique multiplicative inverse, except the zero.
$x^4$, as we can see, is not an element of the field, however, we can reduce it with the help of the defining polynomial's equation $x^4 = x + 1$. Therefore it has the same representation with $x+1$ in the field, so the inverse is the same.
Also, the multiplication inverse table has $2\times 16$ size, so there is only one row (or column ) to calculate.
\begin{array}{|c|c|}\hline
p(x) \in GF(2^4) & inverse \\ \hline
1  &  1  \\\hline
x  &  x^3 + 1  \\\hline
x + 1  &  x^3 + x^2 + x  \\\hline
x^2  &  x^3 + x^2 + 1  \\\hline
x^2 + 1  &  x^3 + x + 1  \\\hline
x^2 + x  &  x^2 + x + 1  \\\hline
x^2 + x + 1  &  x^2 + x  \\\hline
x^3  &  x^3 + x^2 + x + 1  \\\hline
x^3 + 1  &  x  \\\hline
x^3 + x  &  x^3 + x^2  \\\hline
x^3 + x + 1  &  x^2 + 1  \\\hline
x^3 + x^2  &  x^3 + x  \\\hline
x^3 + x^2 + 1  &  x^2  \\\hline
x^3 + x^2 + x  &  x + 1  \\\hline
x^3 + x^2 + x + 1  &  x^3  \\\hline
\end{array}
The non-zero elements of the field, usually represented by adding a star on the upper right $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ form a multiplicative cyclic group. $\mathbb{F}^*_{2^4}$ can be generated by $x$, i.e. $\mathbb{F}^*_{2^4} = \langle x \rangle$. The powers of the generator;
\begin{array}{|c|c|}\hline
i & x^i \\ \hline
x^ 1  &  x  \\ \hline
x^{ 2 } &  x^2  \\ \hline
x^{ 3 } &  x^3  \\ \hline
x^{ 4 } &  x + 1  \\ \hline
x^{ 5 } &  x^2 + x  \\ \hline
x^{ 6 } &  x^3 + x^2  \\ \hline
x^{ 7 } &  x^3 + x + 1  \\ \hline
x^{ 8 } &  x^2 + 1  \\ \hline
x^{ 9 } &  x^3 + x  \\ \hline
x^{ 10 } &  x^2 + x + 1  \\ \hline
x^{ 11 } &  x^3 + x^2 + x  \\ \hline
x^{ 12 } &  x^3 + x^2 + x + 1  \\ \hline
x^{ 13 } &  x^3 + x^2 + 1  \\ \hline
x^{ 14 } &  x^3 + 1  \\ \hline
x^{ 15 } &  1  \\ \hline
x^{ 16 } &  x  \\ \hline
\end{array}
$p(x) = 0$ is not included since it has no multiplicative inverse.

Below is the SageMath code used in this answer.
#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^4+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

for p in S:
    if ( p != 0 ):
        print( p, " - ", 1/p )


What is meant by $\tilde\Omega(\lambda^4)$? I'm currently reading the paper (Leveled) fully homomorphic encryption without bootstrapping , and the following paragraph was near the start:

What is meant by the symbol used? Is it merely to represent polynomial time or something else entirely?

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound.

Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial in the logarithm of the argument.

So in your quotation, $\tilde\Omega(\lambda^4)$ refers to a function $f(\lambda)$ which is asymptotically lower bounded by something of the form $K \log(\lambda)^c \lambda^4$, where $K$ and $c$ are some non-specified constants. [I am ignoring the absolute value of $f$ from the definition, since it clear in your context that $f$ takes positive values.]


IV larger than block size of cipher? Is there any advantage to using an IV larger than a cipher's block size?

Say I'm using AES-256 in Galois Counter Mode (GCM). My file format looks like this:

[IV] [Ciphertext]

Normally, the IV will be 256 bits, or 32 bytes, if the block size is 256 bits.

Is there any advantage at all in using an IV larger than this, and just splitting it and encrypting it as future blocks in the file?

ie:

# python pseudocode
iv = read(64) # read 64 bytes
cipher = AESGCM256(iv[0:32])
cipher.encrypt(iv[32:64])

block = None

while ((block = read(32) is not None):
    cipher.encrypt(block)

Since the IV is a known value, is there any benefit to having a longer IV and splitting it in this regard? Conversely, is there any flaw in doing it this way?

No, not as described in the question.

Putting aside the block size confusion that Richie Frame mentions in a comment (AES block size is always 128), there is no advantage to encrypting a second half of an IV in GCM mode in particular, and rarely in other modes.

In GCM mode the actual IV is used to derive a nonce for CTR mode encryption. By adding a block of data in front of the message you only shift the message forward by one block. An attacker can just ignore that block in any attacks they might have on the encryption layer. The extra block also affects authentication, but it should not make the attacker's job any harder since GCM authenticates the ciphertext, which just becomes longer.

Note that GCM actually allows arbitrary length IVs directly. There is, however, not really a benefit to using an IV longer than 128 bits unless it is more convenient for the application in question (it is hashed down to 128 bits anyway). In fact, 96-bit nonces are most efficient (avoiding the hashing step), if you can make sure they are unique.

With e.g. CBC mode the encryption of later blocks depends on the plaintext, so it may seem like encrypting a random block would help. However, the attacker is still faced with an equally difficult problem as the first block of ciphertext effectively becomes the IV: $IV' = E_k(IV_1 \oplus IV_2)$. Here there is some advantage, since predictable (but unique) $IV_1 \oplus IV_2$ would result in an unpredictable $IV'$, and CBC requires unpredictable IVs. However, it would be better to just use an encrypted counter if you do not have a good source of random IVs.


Can a Cramer-Shoup public key have two different private keys? Since I am new to the Cramer-Shoup algorithm, I would like to know: Is it possible to have two different private keys for a public key due the key pair generation algorithm that Cramer-Shoup uses? I know that in public key algorithms, this is not possible in all cases, but I want to make sure what the answer is for Cramer-Shoup.

Yes, this is possible.

One possible argument is of algebraic nature, using the fact that there is some $a\in\{0,\dots,q-1\}$ with $g_2=g_1^a$ and rewriting the public key's defining equations using this relation.

However, there's a much simpler justification: A Cramer-Shoup public key consists of five elements $g_1,g_2,c,d,h$ of a group of order $q$, hence there are at most $q^5$ possible public keys. However, a private key consists of two freely chosen elements $g_1,g_2$ and five freely chosen integers $x_1,x_2,y_1,y_2,z$ between $0$ and $q-1$, yielding $q^7$ possible private keys. Therefore, there exist (on average) at least $q^2$ private keys mapping to a single public key.

(In fact, the algebraic argument mentioned above shows that there are exactly $q^5$ public keys, each of which corresponds to exactly $q^2$ private keys.)


Why are key lengths in asymmetric algorithms typically longer than key lengths in symmetric algorithms? Apologies if this is a duplicate question.  I did search prior to posting :-) I think it may be somewhat related to my other question here but I think it's different enough to warrant a separate question page.

Symmetric algorithm key lengths seem typically smaller to me:

AES uses keys sizes of 128 bits, 192, or 256 bits.
Triple DES uses 168-bit keys
Etc etc. etc.

Conversely, assymetric algorithms seem to require much larger keys:

RSA uses variable length keys between 1024 and 4096 bits.

Why is this?  What about asymmetric cryptography requires the significant jump in key sizes?

Let's consider a cryptographic algorithm (e.g. encryption) that uses a key. The key is part of a space of possible keys; e.g. the space of all sequences of 128 bits, for AES.

There is a conceptual attack known as brute force in which the attacker simply tries all possible keys until a match is found. This attack "works" for all algorithms, so, in order to achieve security, the key space must be large enough to make the cost of brute force ludicrous. Traditionally, we prefer it when the space of keys has size 2128 or more (in practice, 2100 would already be way beyond the technologically feasible, but cryptographers just love powers of two).

Symmetric algorithm usually accept keys as sequences of bits, where any possible sequence is a valid key. Thus, they can achieve the minimal key space requirement with a minimal number of bits: with keys of 128 bits, you can have 2128 keys, and they are all fine.

Asymmetric cryptography, on the other hand, tries to achieve something "magic". Symmetric algorithms are just mangling bits together in a kind of complicated knot; for asymmetric encryption or signatures, the only known methods involve mathematical structures. A consequence is that if keys for an asymmetric algorithm have a length of k bits, then not all sequences of k bits are valid keys.

Furthermore, the strength of the asymmetric algorithm relies on the intractability of the unraveling of the internal mathematical structure; for instance, in RSA, the public key is (mostly) a big composite integer, and the internal mathematical structure is the factorization of that integer into its prime factors. Attackers then usually have much better attack methods than simply trying out all possible private keys. For instance, a very primitive attack on RSA would enumerate possible divisors for the modulus, one at a time: for an integer n, the largest non-trivial divisor must of no greater than the square root of n, meaning that the basic "trial division" factorization algorithm will factor a 256-bit modulus in time 2128, not 2256. And we know of much better factorization algorithms.

The raw consequence is that asymmetric keys usually need more bits to express themselves: due to the internal structure, not all sequences of bits can be valid keys, and since there is an internal structure, attackers have better attack methods than brute force, thereby needing larger things.

Notwithstanding, most of the "key size" business is traditional. For instance, in the case of RSA, we say "RSA-2048" to mean "2048 bits", but that's just the size of the modulus, which is only one of the elements of the public key. The complete public key is a bit larger (to give room for the public exponent, which is usually short). The private key itself can be reduced to about half the size of the modulus (in that case 1024 bits), since if you know the public key (modulus n and public exponent e) and a non-trivial factor of n, then you can rebuild all the elements of the private key. However, it is traditional (and actually standard) to save private RSA keys as a bunch of integers that, for RSA-2048, would amount to more than 9000 bits, not counting encoding overhead.

Thus, the notion of "key size" for a cryptographic algorithm does not necessarily correspond to the actual encoded size of either the public or the private key, and it is always delicate to compare key sizes between different algorithms. For instance, "256-bit ECDSA" is usually considered to be stronger than "2048-bit RSA", even though:

256 is lower than 2048;
RSA-2048 public keys will have size closer to 2100 bits, and private keys will be encoded over more than 9000 bits;
256-bit ECDSA public keys are normally encoded over 520 bits.

(Though a 256-bit ECDSA private key happens to be indeed a 256-bit integer — but with a strength somewhat equivalent to a 128-bit symmetric key, not a 256-bit, because of the internal mathematical structure.)


Proof of non-knowledge I pretty recently understood the concept of zero-knowledge proof (on a purely logical level, not mathematically speaking, thanks to this article). Despite being a very counter-intuitive principle, it turned out to be an actual and applicable system.
I am now wondering if another counter intuitive problem is solvable: is it possible to prove that we don't (or are unable to) know an information? Or to rephrase it in a more formal way, is it possible to prove that such a system is impossible to create?
Regards

Yes.  Just prove that such information doesn't exist.

(For example, that can be used to prove that one

doesn't know a boolean value x such that  x and not x .)

For P/poly provers, if such proofs exist then UNSAT has a usually-correct promiseMA protocol.

However, if public-coin collision-resistant hash families exist, then

a common random string is enough for arguments of non-knowledge.

For example, to argue that one does not know a string

such that  Hcommon_random_string(0||x) = y ,  argue that one

does know a string x such that  Hcommon_random_string(1||x) = y .


Group Encryption or Multi-Party Encryption I came accross a privacy and cofidentiality problem in medical field where patients medical record is available to certain doctors in full, but researchers/pharmacutical companies can only view the test reports but not the identity of the patient like name and social security number etc.

I know this can be implemented by some programming checks in application, but how to achieve this functionality using cryptography?
Where an encrypted record is partially decryptable by one party but fully decryptable by other.

Any guidance/reference to already published or in use scheme will be helpful.

This kind of thing would typically be done via role based accessed control (RBAC), not encryption.  To do something like this strictly with encryption if you could assign identities upfront then you could use hybrid encryption to achieve this (though it seems a bit clumsy).  A public/private key pair is assigned to each role.  Data is encrypted with a randomly generated symmetric key and that key is then encrypted with the private key of the role(s) that access the data.  Each user has a role and therefore a set of public keys associated with that role.  If the user has a public key that can decrypt the symmetric key they can then decrypt the data and view it.

RBAC is a better solution.


Existence of PRF $\implies$ existence of PRG Let $F:\{0,1\}^n\times \{0,1\}^m \to \{0,1\}^l$ be a PRF.
  I want to show that $G(-)=F(-,x_0)$ is a PRG for every $x_0\in \{0,1\}^m$.

Proof attempt:

Let $D$ be an efficient distinguisher against $G$ in the PRG experiment (see below). We aim to show that $D$ has negligible advantage.

Consider the following efficient distinguisher $D'$ in the PRF experiment. Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

My questions:

Is the proof correct?
Is the level of rigor sufficient?

Additional information:
Here are the two experiments I was referring to (taken from Katz/Lindell).

Your proof did not convince me at first.

  Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

The word "then" threw me off. The output of $D'$ is not a consequence of the first clause. I'd reword this to explicitly state that we're constructing a $D'$ that uses $D$ in a particular way. This may seem silly, but this did make me do a double take.

  By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

The first sentence isn't true. In the PRG game, sometimes $D$ will actually be given a random string instead of $G(s)$, and in those cases, $D$ should reject the input, not accept it, to win. Perhaps you mean $D'$ wins if and only if $D$ wins?

Furthermore, there isn't really a justification (even a sketch of one) given. The reader needs to work out the details of $\mathcal{O}(x_0)$ on his own to even understand the argument; that's its failing. A proof's correctness is only half the battle: it must also convince the reader of its correctness, which can be far harder.

Why is it the case that $D' = D(\mathcal{O}(x_0))$ is a distinguisher for $F$, and thus must have negligible advantage? That is the meat of the proof -- which you've omitted.

I think a proof by contradiction is easier to understand. Let's also try to be explicit in our reasoning.

We're given a PRF $F_k$ and we want to show $G(s) = F_s(x_0)$, where $x_0$ is a fixed constant in $\{0,1\}^m$, is a PRG.

Assume (toward a contradiction) that $G$ is not a PRG, so there exists an efficient distinguisher $D$ with non-negligible advantage in the PRG indistinguishability game for $G$.

We will build an efficient distinguisher $D'$ in the PRF experiment using $D$. In that experiment, $D'$ will be given either:

a uniform function $\mathcal{O} \in \mathsf{Func}_m$, or
the function $\mathcal{O}(x) = F_k(x)$ where $k$ is a uniform string in $\{0,1\}^n$

Conveniently, if we evaluate $\mathcal{O}(x_0)$, we get either

a uniform value in $\{0,1\}^m$, by definition of $\mathcal{O} \in \mathsf{Func}_m$, or
the value $F_k(x_0) = G(k)$

Notice that the possible values of $\mathcal{O}(x_0)$ exactly match the parameters of the PRG indistinguishability game for $G$. As a result, $D$ can distinguish between the two above situations with non-negligible advantage, since we assumed $G$ is not a PRG.

Therefore, if we let the output of $D'$ be the output of $D$, then $D'$ has non-negligible advantage in the PRF game for $F_k$. This violates our assumption that $F_k$ is a PRF. Therefore, our original assumption that $G$ is not a PRG must be false, i.e., $G$ must be a PRG.

The above proof may not be as rigorous as some would like, but I think it's acceptable enough as a brief sketch (and could be filled-in with real mathematical details if necessary).

Notice that I did not really say anything different than your post -- I was just more explicit. I did switch to a proof by contradiction, but that's because when I went to state the conclusion, it ended up sounding like a proof by contradiction anyway.


Time Capsule cryptography? Does there exist any cryptographic algorithm which encrypts data in such a way that it can only be decrypted after a certain period of time?

The only idea that I can think of, is something like this: Seed a PRNG with a public value. Run the PRNG for a week and use the final value it produces to encrypt the message. Now anyone who runs that PRNG for a week starting from the seed value you made public can decrypt the message. Obviously this breaks down since they could use more computational power than you; if the time span was years then Moore's Law would apply, etc.

Is there anything like this other than physically burying a private key on a USB stick in a literal time capsule?

Yes.

There has been a lot of work on "proof of work" protocols or "time-lock puzzles." Typically in cryptography, functions are either easy to compute or intractable. These protocols look at functions that are moderately hard to compute.

To do time-release encryption, you need a puzzle with the following properties:

Difficulty of the puzzle can be monotonically increased according to some difficulty parameter
Best algorithm to solve it is intrinsically sequential (parallel computing doesn't help)
Amortized cost of solving a group of puzzles is the same as a single puzzle
There is a trapdoor (shortcut) that allows efficient evaluation of the puzzle

With time-release crypto, the idea is to generate a puzzle that will take a certain amount of time to solve based on an estimate of a person's computational power and how it will grow in the future (e.g., Moore's law). As you can tell, it only gives you a fuzzy indication of how long it will stay secret (see below for a real world example). Property 2 is very important because adding parallel computation is easy and it is hard to estimate how much parallelization is possible.

Note that most proof of work protocols do not care about property 2 because they are used in different ways. These might be based on finding partial collisions/preimages in hash functions or exhaustive search of a small space (e.g., bitcoin), however speedups with parallel computing is trivial in these examples. There are also a number of memory-based puzzles that require lots (more than can be cached) of memory accesses, which is a more predictable measure of time on computers.

Back to time-release crypto. The idea is to instantiate a puzzle $p$ with difficulty $d$: $p=\mathsf{Puzzle}(d)$. A trapdoor $t$ for efficiently solving it is known to the person who generates the puzzle. This person then encrypts her message under key $k$ with a normal encryption function: $c_1=\mathsf{Enc}_k(m)$. She then release an "encryption" of the key she used by combining the key with the solution to the puzzle. Note that she can efficiently solve the puzzle with trapdoor $t$ but the recipient can't. She computes: $c_2=k \oplus \mathsf{Solve}_t(p)$. The ciphertext is $c_1,c_2$ plus a description of the puzzle.

To decrypt, the recipient computes $s=\mathsf{Solve}(p)$, which should take a moderate amount of time. He then recovers the key by $k=c_2\oplus s$, and can then decrypt $c_1$.

The disadvantage to time-release cryptography is that the recipient must devote an entire processor to solving the problem for the period of time that it should remain secret.

The best proposal for a Puzzle with the right properties is due to Rivest, Shamir and Wagner in this paper. It is based on repeated squaring in RSA groups. A recent result precludes any intrinsically sequential time-lock puzzles in the random oracle model (e.g., based on hashing).

In 1999, Rivest created a time capsule message to commemorate the 35th anniversary of MIT's Laboratory for Computer Science. He talks about how he designed it to require 35 years to decrypt. It is an interesting read.


Could a quantum computer recover files from ransomware if the attacker doubly encrypted them with RSA-4096? How would a quantum computer decrypt a file (or find the keys to such a file) if it were encrypted with standard RSA 4096 encryption, but encrypted two times with different keys? The keys are known by only one party. They could be different lengths and complexities.

And theoretically, how long would it take (with a general estimated Quantum PC's amount of power)?

Note: The incompetent fools at geek squad 'accidentally' ran a ransomware on my clients computer while trying to restore the files from a ransomware. Then, they did a faulty windows backup and charged him a thousand bucks. He won't take "it's just gone" for an answer, so I need numbers and proof that it's completely unrecoverable. Also, this is a very good question in regards to the future of computer encryption if you can't afford to switch to quantum right away...

Ask your friend:

Do you even have the RSA moduli used by the ransomware?

If not, even Shor's alogrithm on a real honest-to-goodness large quantum computer is not going to help.  And there's no reason for the ransomware to share the RSA moduli with you.
While RSA ciphertexts/signatures can be deanonymized by the German tank problem, there's not enough information to reconstruct enough of the modulus to apply Shor.

Do you have a billion euros rattling around in your pocket?

If not, you can't afford the research and construction for a quantum computer.

Do you have a couple decades to wait?

If not, you are too impatient and quantum computers won't be developed in time.

Do you feel lucky?

If not, you might have gambled your billion euros and decades of lifetime on a coin coming up heads when actually it's tails and quantum computers can't actually be made to work.

If the answer to any of these questions is ‘no’, your friend's data are hopelessly lost.  Advise that your friend invest in solid backups, and specifically in backups that cannot be deleted from the computer they are backing up—if you simply back up to an external USB drive, or simply back up to an S3 bucket with an access key that has authority to create and delete archives, then you are not protected.

Also advise your friend that Geek Squad is not their friend: the FBI cultivates informants at Geek Squad to actively search for material at the FBI's request on any computers they work on and forward their data to the FBI[1][2][3][4].

All that said, using RSA twice doesn't really matter: if you had the RSA moduli, then if made a Shor-capable quantum computer could factor the moduli in only twice the time, and the size of the quantum computer needed is linear in the number of bits in the modulus.


Equal hashes for different messages when doing key length extension attack sha1 I was doing the cryptopals challenge 29, and I found something weird.
When I try to create a forged hash for a forged message I get always the same hash for different forged messages.

    def attack(self, hash, message, payload, oracle):
        for k in range(100):
            forged = self.glue_padding(b'a' * k + message)[k:] + payload
            ml = (k + len(forged)) * 8
            r = self.get_register(hash)
            sha1 = SHA1(payload, r, ml)
            forged_hash = sha1.digest()
            # SAME VALUE
            print(forged_hash)
            if oracle.validate(forged, forged_hash):
                print("[*] forged message : " + str(forged))
                return True
        return False

is this the normal behaviour?

Is this the normal behaviour?

No, it is not.  While it is known that SHA-1 collisions can be found, it's a lot more work than what you do.

It's likely to be a bug in your code.  I went through your code, and I'm not sure whether you might be computing the hash of the same preimage each iteration - that would certainly cause each hash to be the same.


Encrypting a pseudorandom message Does encrypting a pseudorandom message need the same requirements from a block cipher?

For instance, can we decrease the number of rounds of AES if we want to cipher a random block, without any security loss?

Thank you

A message - strange as it may sound - cannot be encrypted by a block cipher. A block cipher is a deterministic keyed permutation. As it is deterministic, it cannot be a CPA secure cipher: identical messages will result in identical ciphertext, leaking information about the message. This is why ECB mode encryption, which consists of block encrypting subsequent blocks of the message, is insecure. A secure mode of operation - CBC, CTR etc. - and an IV are required to turn block ciphers into secure ciphers.

As there is no way of distinguishing the message from random data the cipher doesn't need to be that secure. It is however still required to use a mode of operation and an IV if the block size is small. Otherwise the block cipher must be relatively large (˜256 bits for large messages) so that repetition of blocks in the plaintext cannot be detected.

If there is even a hint of information on the message (a header or the parity bits of a DES key, a slow starting PRNG, a PRNG started with too little entropy in the seed, a non-secure PRNG etc. etc.) then these kind of schemes will fail spectacularly. The scheme would be brittle to the extreme; if anything breaks or if any info leaks it will crumble. Obviously an attacker should certainly not be allowed to control the plaintext, so the scheme would not be CPA secure.

So yeah, you could reduce the number of rounds or even use a repeated XOR cipher. But the risk of leaking info would be huge.


Is the output of ISAAC still secure if I take the 32 bit number mod 8? I'm using ISAAC for encryption but only need an 8 bit number.  So, if I use N mod 255, I presume the output would be only a random sequence of 255 numbers... but is it still secure?

I could of course copy the 8 bit number to be encrypted into the first 8 bits of a 32 bit number and then fill the rest of it with random numbers and then mod it with the 32 bit ISAAC output.

Well, let's start with that N mod 255 doesn't convert number to 8bit byte, but a byte without highest possible value, 255. You were looking for either N mod 256 or N and 255 (somewhat known assembly trick to do some divides faster).

Now, if your source is cryptographically sound, then any amount of bits cut from it will be sound (except might collide faster). However this isn't case when cutting a value that isn't power of 2! In your example, let's assume we are cutting 8-bit values (0-255) to your N mod 255 (0-254). In this case we will get 1-254 with same probability, but we are twice as likely to get 0, and we will never get 255. This obviously makes skew in your data, which is usually combated by cutting last values that would cause such skew (in my example, we would reject 255 and draw value again).

Of course all above holds in your specific case of ISAAC.


Can one passively load-balance HTTPS traffic based on TLS SNI? Is it theoretically possible to passively snoop into the HTTPS traffic, reliably detect whether or not TLS SNI is attempted to be used by the client, and, if it is, redirect the stream of the connection as-is to one of the many different upstreams (each one of which requires HTTPS in order to connect and may have its own certificate not necessarily known to us)?

The SNI extension is plain text in the ClientHello. This means that it is possible to passively snoop the value and redirect the traffic. This is already used in practice, i.e. haproxy has this feature for several years.


If Kerckhoff's Principle holds, why do we need a cipher at all? I understand Kerckhoff's principle, in a very practical sense, that the best attack that can be performed on a given cryptographic algorithm should be only as practical, if not less practical, than an exhaustive key search, that is, testing every possible key. My question is, if this is the case, then why go through the trouble of creating a cipher in the first place? Why not simply use a ridiculously long key, if you're gonna create a cipher that only takes as long as an exhaustive key search anyway?

...why go through the trouble of creating a cipher in the first place? Why not simply use a ridiculously long key, if you're gonna create a cipher that only takes as long as an exhaustive key search anyway?

Designing a cipher is significantly less hassle then using a ridiculously long key.

Designing a cipher only needs to be done once by a competent professional.

Using a ridiculously long key would need to be:

Done by all parties

"all parties" includes everyone with a networked electronic device
Almost all of them are not competent professionals
Requires a pre-existing secure channel, or more likely a face-to-face meeting

"secure channel" must not use encryption, otherwise the problem is circular

Done pairwise for each group of communicating parties

e.g. You have to go through the key establishment process for every particular site you want to visit
A web site with 1000 users that each have a 1GB key would need to have access to 1TB of reliable, secure storage just to store the key material (that's a small website)

Done repeatedly

You will eventually run out of key material
Your keys could become compromised

Updating them in a useful time frame will be next to impossible

Destroyed securely after use

Re-using any part of the key will lead to a practical lose of confidentiality

In a practical scenario (e.g. HTTP requests) known-plaintext attacks apply, which will allow trivial recovery of the key

It simply would not work in practice. A proper cipher will.


Stripping off message authentication or signature If attackers can strip off RSA / EC / -DSA digital signature and conduct CCA on AES-CTR or CBC payload, why can't they do the same for AES-GCM?

If attackers can strip off RSA / EC / -DSA digital signature and
  conduct CCA on AES-CTR or CBC payload, why can't they do the same for
  AES-GCM?

The scenario, you're talking about is iMessage or Signal Protocol or other protocols which allow optionally to sign the ciphertext and thereby don't MAC it.

The problem here is a) that you could replace the signature with your own (if it is valid and required) or b) completely strip it off if it is not required, which would be considered a protocol flaw in my eyes.

The situation is different with AES-GCM because the authentication is a mandatory part of the specification. Any non-stupid implementation will return an "invalid ciphertext" if the tag is missing or just the last ciphertext block (i.e. largely unrelated), so this won't allow you to even get to decrypt the CTR stream and thereby exploit its CCA weaknesses.


Downsides of not using deterministic ECDSA signatures for blockchain validation? I've noticed that in many Bitcoin wallet implementations, as well as other blockchains, deterministic ECDSA signatures are being used (generally based on RFC 6979).

There seems to be some benefits to this:

Testing would be easier, as you can have known inputs and outputs.
There is no need for a good source of randomness at the time of signature generation
Some blockchain operations might be easier if signatures produce consistent output for the same data (e.g. identifying if the same blocks have been signed before)

I'm working in a constrained hardware environment where I don't have access to a deterministic ECDSA implementation, but I do have good entropy. Are there any security risks in participating in a blockchain network without deterministic signatures?

No, you'll be fine (most likely).

DSA (the base of ECDSA) has been around since at least 1993 (when FIPS 186 was released). Much like with ECDSA you also need a $k$-value for DSA for each signature. From what I know, RFC 6979 (August 2014, first draft in march 2011) was the first general standard and Ed25519 (special case of EdDSA now, september 2011 (PDF)) the first specific DSA variant to use deterministic $k$-generation. So essentially people used random $k$ values for nearly 20 years and issues came up only when people failed to ensure the randomness of the value (by re-using it or using a bad RNG). However this does not apply to you as your HSM will take care of that. So you'll be just as fine as all the people were before we had deterministic (EC)DSA.

The only drawbacks are essentially those that you listed in your question, the first two of which don't matter if you trust your HSM and the last one you can't do anything about.

Also note that a deterministic (EC)DSA signature is indistinguishable from a non-deterministic one except if you have two signatures of the same data.


Differential privacy on medical data When we apply the differential privacy on medical data to protect the personal data of the patients, how the doctors can access the original data to analyze them and to intervene in real-time. In other words, the added noise to disturb the data, can be eliminated?

Differential privacy does not help to prevent disclosure of individual records when the user—the doctor, in this case—needs access to the individual records themselves.

Differential privacy is a property of a system for aggregating a collection of records into statistical queries on a data set so that the inclusion or exclusion of an individual record can't change the answers to the statistical queries much.  That way, the answers to the statistical queries—which might be published in a medical journal, or used to study trends—can't reveal much about individual patients.


Does this proof sketch show that finding a SHA-1 preimage is NP-hard? Jutla & Patthak wrote "Is SHA-1 conceptually sound?" back in 2005, in which they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard.  Now, there are some issues with the proof sketch (as far as I can see).  It does not take into account the additional constraints introduced by linear message-expansion; and it does not handle the CHOICE function and is therefore applicable to rounds >20.  At a somewhat more pedantic level, the constructions look a bit artificial, but perhaps that's just aesthetics.

Nevertheless, it seems that if the proof sketch does hold true, then this provides a NP-hard model for two-thirds of SHA-1 preimage-finding, which seems like it should be a big deal.  The paper has never been published in conference proceedings or journals, nor is it cited by the most significant SHA-1 preimage work in recent years (i.e., Knellwolf & Khovratovich ; Rechberger; and Aoki & Sasaki).  I assume that there's something more important that's wrong with the proof as a whole, but I'm not sure what it could be.

So my questions is: what's wrong with it?

they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard

No, they don't.  The definition of a problem being NP-hard is "if you have an Oracle that can solve instances of this problem in polynomial time, you can solve any problem in NP in polynomial time"; as we can quickly find SHA-1 preimages using a huge lookup table, we can easily see that finding SHA-1 preimages is not NP-hard (unless P=NP, in which case every problem is NP-hard)

What they do (at best) is show is a class of problems that are jointly NP-hard (of which finding SHA-1 preimages may be an instance).  However, that doesn't tell us anything about the concrete difficulty of SHA-1; NP-hard problems can have easy instances (trivial example: travelling salesman problem over every city in the world; is there a circuit that's at most 1 kilometer total distance?  Even though the traveling salesman problem is NP-hard, this is a trivially solved instance)


Encrypt a file for random access but only after an initial read of the whole file I'm symmetrically encrypting a file (using a random salt and a user supplied password with PKCS5S2, i.e., nothing special) and I need to be able to access it randomly. Therefore I'm using a stream cipher. This works well, but it allows the attacker to verify a wrong password when reading only a tiny part of the file (garbled data are easy to recognize).

IIRC there's an encryption schema making it impossible to read any part of the data in isolation, you must read it all (I forgot how it's called). This seems to conflict with my random access requirement, however I always need to read the whole file first and then I need the random access.

Is there an encryption schema allowing this, i.e.,

to obtain any information, all data must be decrypted first
afterwards, any portion of the data can be decrypted in isolation

Yes, you can do that.  Start by generating a random key and encrypting the data under that key.  Now, you in turn encrypt that key with your password-derived key.  The twist is that you include the already encrypted file in your PBKDF.  So you generate a random key $k$ and then encapsulate it as $\mathcal{E}_{k'}(k)$, where $k' = H(PBKDF(\text{password}) \| \mathcal{E}_k(\text{file})$.  That way, to decrypt you have to read and hash the entire encrypted file to obtain the wrapper key, which gives you the key to decrypt the file itself.  Once you have that key you can do random access, but for each password attempt you have to read and hash the whole file again.


Is the RC4 keystream random or not? I have cause to use the PRNG half of RC4, but am seriously confused as to the randomness of its output.  (Only the PRNG half.)

On the one hand, there is a large body of literature finding ever greater biases in RC4's keystream.  It appears that both weak and strong distinguishers can identify RC4 from a truly random sequence.  These analyses are performed by clever people.

On the other hand, an RC4 keystream passes most accepted randomness testing suites.  I've personally run the Dieharder tests against a 100 GB file of output and it passed.  These test suites are designed to identify biases in allegedly random bit sequences and are written by clever people.

Can anyone square this circle?

EDIT:

Having reviewed the answers/comments, I'm minded to believe that the PRNG portion of the RC4 algorithm is better than it appears initially from cursory inspection.  In saying this, I'm excluding the so called key scheduling algorithm which clearly is quite broken.  I would make the following observations:

The fact remains that a singular keystream passes the best statistical tests for randomness.  This cannot be ignored.  If there was significant deviation from randomness, of any type, standard testing would discover it.  The only hypothesis that matches the evidence is that long term bias is within typically acceptable levels.
The below referenced paper accepts that major statistical biases occur only within the first 512 bytes of the keystream, and are fully attributable to the key scheduling algorithm/key length.
Long term biases are 500 times lower than the initial ones, and the authors highlight the uncertainty with which long term biases were determined, with $2^{-16}$ biases difficult to fully assess or categorise.
The decimal expansion of pi shows similar magnitude biases (10e-6) even out to 2 trillion digits — that's the nature of randomness.
If the same degree of extensive scrutiny were applied to other PRNGs, would they too show similar biases?

In summary, it appears to me that with a fully randomised and manually injected state array (thus bypassing the inherent key scheduling component), RC4 is a good PRNG.

Statistical tests have no value to evaluate randomness in a cryptographic sense, because an attacker is not required to use any specific test. The fact that a stream passes some set of predetermined tests tells you nothing about how it fares against tests which are not in the set.


Why is RSA usually limited to messages up to 1 block I'm wondering why RSA encryption usually is only used for messages that fit into one block.
For larger messages hybrid encryption in combination with symmetric ciphers like AES seem to be the solution of choice e.g. c.f.
Bouncy castle FAQ.

I know about the advantages of hybrid encryption considering

better performance
efficient handling of multiple and changig recipients

Are there any other reasons not to use only RSA?

We do not really know how to do RSA encryption of messages which span multiple blocks. At least not securely. The problem is already hard for block ciphers (see all the defined modes of operation).

Also, the worst performance issue with arithmetic cryptography like RSA is not about CPU, but about size. When you encrypt a piece of data with RSA, you get some overhead. E.g. with a 1024-bit RSA key, you can encrypt at most 117 bytes at a time, but this yields 128 bytes. When transmitting a long message, a fixed overhead of a few hundred bytes is much more tolerable than a +10% size increase.

CPU efficiency is often quoted as the reason we do hybrid encryption, but it is rarely as compelling as the two problems explained above.

(Additional point: since proper RSA encryption needs randomness, you must have a cryptographically strong PRNG -- also known as "a stream cipher". So even non-hybrid encryption does not avoid using symmetric primitives.)


Factorizing N to derive D So I have the value of N. I have to use this value of N to find the value of D.
N = 265291078722948385089717069136983657793
Now I read about RSA algos and found out that
N=PQ | where P and Q are prime factors

I found -
P - 14716976826788780483
Q - 18026193955816294571

The following is an example of what I've approached
Choose p = 3 and q = 11
Compute n = p * q = 3 * 11 = 33
Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]

We have
P = 14716976826788780483
Q = 18026193955816294571
N = 265291078722948385089717069136983657793
E = 65537 (given)
φ(n) = 265291078722948385056973898354378582740    [using (p-1)(q-1)]

I'm unable to solve the equation  (d * e) % φ(n) = 1 for the above values.
We need to find/derive D.
I tried using this online calculator
Princeton Extended Calc
But it doesn't accept large values
Any help is appreciated

Wolfram alpha can do this:

http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+65537+mod+265291078722948385056973898354378582740

yields

d = 240894030773496778838526583320400223673

The alternative is to write a small C program using gmp or using python, e.g.


What Permutation Entropy really is? I was wondering about what is permutation entropy(PE). Then, I came to know this paper which describes PE. Now, let's assume that we have a pseudorandom permutation that is generated using an entropy source and we used a uniform shuffle algorithm(like Fisher-Yates shuffling algorithm). Also, assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the output permutation can have at max 256-bits of entropy? For every value of entropy, we shall get a unique corresponding permutation.

Assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the permutation can have at max 256-bits of entropy?

There's a semantic problem: in cryptography, unless otherwise stated, we consider Shannon entropy, and that's defined for a symbol-generating process, not for a symbol. A permutation can be a symbol, not a process. Hence "permutation … have … bits of entropy" is not something defined. That's true including if we consider Permutation Entropy (a different breed of entropy, discussed in the second section of the present answer).
What we can define is the entropy at the output of a deterministic process/algorithm generating permutations. And then yes, if there is 256-bit entropy (per symbol) at the input of this process (for example, if the input consists of 256-bit bitstrings chosen uniformly at random, uniquely defining one output permutation in a deterministic manner), then there can be at most 256 bits of entropy (per symbol produced, that is permutation) at the output. Argument: applying any deterministic function $f$ to a source of symbols $s$ can not increase it's Shannon entropy, defined as
$$\sum_{s\text{ with }\Pr[s]>0}\Pr[s]\,\log_2\left(\frac1{\Pr[s]}\right)$$
because $f$ can only change that sum when $f(s)=f(s')$ with $s\ne s'$, $\Pr[s]>0$ and $\Pr[s']>0$, and then that change is the negative
$$\Pr[s]\,\log_2\left(\frac{\Pr[s]}{\Pr[s]+\Pr[s']}\right)\,+\,\Pr[s']\,\log_2\left(\frac{\Pr[s']}{\Pr[s]+\Pr[s']}\right)$$
What's more, that threshold of 256-bit output entropy is exactly achievable: there are $(2^8)!=2^{1683.996\ldots}$ shuffles of $\{0,1\}^8$, and that's (way) more than $2^{256}$. Depending on how we use Fisher-Yates shuffling and the form of the entropy at the input, that threshold will be reached, or not.
One way to reach this 256-bit output entropy threshold, if the 256-bit input entropy is in the form of a 256-bit uniformly random bitstring, goes: the first 64 times the Fisher-Yates algorithm requires a random integer $j$ in range $[0,i]$ with $i\ge15$, we pick an integer $j$ in $[0,15]$ based on 4 bits of the input (that we assemble into an integer per big-endian convention, then discard). And any other time the algorithm requires a random integer, we pick the integer $j=0$. That method will generate one of $2^{256}$ distinct permutations with probability $2^{-256}$ for each, and probability $0$ for the $(2^8)!-2^{256}$ other possible permutations. That's exactly 256-bit Shannon entropy per permutation output by this process.
As noted by Maeher, the above must not be used to generate a pseudo-random permutation from a 256-bit uniformly random bitstring in a cryptographic context! If that's needed, one option is to seed a Cryptographically Secure Pseudo Random Number Generator (CSPRNG) and use it to generate the $j$ in $[0,i]$ during Fisher-Yates. The output entropy will still be near 256-bit per permutation, but it will be computationally impossible to distinguish the output permutations from permutations generated at random (that is, with $1683.996\ldots$ bits of entropy per permutation).

Answering the title of the question

What Permutation Entropy really is?

Permutation Entropy, and the "paper" linked in the question (which I won't discuss or seriously consider), have no relation with the entropy of a permutation generator. Permutation Entropy is an alternate entropy defined by Christoph Band and Bernd Pompe's Permutation entropy: a natural complexity measure for time series in  Physical Review Letters, 2002 (paywalled).
Given a source of values, it's Permutation Entropy of order $2$ is the Shannon entropy of a modification of the source, where we replace a symbol by $0$ if it's lower than the next, by $1$ otherwise.
This generalizes to Permutation Entropy of order $n>2$: we replace each symbol by an integer $k$ in $[0,n!)$ characteristic of the order of $n$ symbols starting from there.
A property of Permutation Entropy is that it's invariant when the source goes thru any strictly monotonous transformation. Perhaps that's interesting in physics, but I do not see that this property, or Permutation Entropy in general, is much useful in cryptography.


Getting a random number on an STM32L0x1 device for SRP6a I'm trying to get a random number for a STM32L0x1 MCU to use it in protocol SRP6a.
(I know that there are MCUs with an embedded hardware random number generator. But it would cost twice as much as the MCU I'm using right now.)
Now some questions arise:

Would a "bad" random number seed (like reading values from ADC) negatively affect the security of SRP6a?

If yes: how to get a "good" random number (random enough for SRP6a) on STM32L0x1?

What about the following approach:
a) Create the random number seed externally at the factory and save it in EEPROM of the MCU
b) Every time the MCU is (re)started, run a one-way function (like a hash) on the seed, save that new seed and use it for the software random number generator.

Would a "bad" random number seed (like reading values from ADC) negatively affect the security of SRP6a?

Yes. At least, a reused random on the server side enables replay of a captured session. On the client side, I think (without detailed analysis) that a predictable RNG can be used to extract secret information allowing login, or even the password if it is weak.

How to get a "good" random number (random enough for SRP6a) on STM32L0x1?

That's a generic microcontroller with 32-bit CPU, RAM, Flash, EEPROM, ADC. This gives at least two options:

The one outlined in the question: use a Cryptographically Secure Pseudo Random Generator, seeded with a secret random value at factory, and it's state kept in permanent memory (e.g. EEPROM) from one invocation to the other. The difficulties are

Keeping the state secret (including, setting it up initially). If an adversary can use a JTAG port, poof goes security. There are other avenues of attack, e.g. power analysis.
Going from one state to the other atomically including in the event of power loss, perhaps at a moment chosen by an attacker. That's EXTREMELY difficult. That's significantly easier with RAM, if there is a battery backup of that.
Update per comment: problem with atomic EEPROM update is that the underlying hardware does not provide it. When a byte erase or write gets interrupted by a power loss, what's read there (until another erase or program) is unspecified. Experience shows that it often is neither the old nor the new value, and sometime varies from one re-read attempt to the other, as a function of power supply voltage or temperature, and time. This is because individual bit cells of the EEPROM byte are left incompletely erased or written, giving no noise margin to the read comparator. Reliable atomic update is possible despite that, but hard to get right and test well. A prerequisite is to obtain some assurance that physically re-erasing (and/or over-programming) a byte that appears erased or (successfully programmed) is possible, rather that blocked by some driver (or worse hardware) trying to reduce EEPROM wear.
EEPROM eventually wears, and perhaps adversaries or just Murphy will induce repeated updates. I've witnessed contactless Smart Cards powered-up and activated with a sub-second cycle merely by being stored next to an NFC mobile phone, and have heard mildly credible anecdotes of bank Smart Cards destroyed in the process.
Choosing the CSPRNG correctly; not the hardest!

Leveraging some physical source of randomness, e.g. sample the 12-bit ADC (it can run at over 1 M sample/s) and post-process that (e.g. feeding enough samples into a hash and using the result as the random). The hardware can boil down to a single trace connected to an existing point at an appropriate voltage. The main difficulty is evaluating the appropriate number of samples, which can vary depending on environment (in particular temperature, nearby EMI source). Taking a lot of headroom is good, but often not enough: if an adversary has some level of access to the hardware, the approach often can be made to fail (e.g. by forcing the input of the ADC to a slightly higher voltage than the maximum, thus making the output of the ADC fixed to all-one; or by pouring liquefied gaz, lowering the temperature dramatically, making the ADC malfunction or/and reducing the amount of noise).

The two approaches can be combined, making a successful attack more difficult. But designing a robust random number generator, especially when an adversary has access to the device, is notoriously difficult.


Collision free one way function I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do not know how to prove or disprove the function as being collision free. My only proof so far has been from unit testing all possible inputs, which for all 2 byte combinations has proven successful, but is obviously not concrete.

The algorithm iterates over a sequence of bits. It counts upwards through prime numbers, beginning at 2. For each contiguous '1' bit in the input bits, an exponent counter is incremented. When a '0' bit is encountered, the current prime is exponentiated and composed into the running output, the exponent counter reset to 0, and the current prime is set to the next prime.

For example:

"11001101"

Is interpreted as:

(2 ** 2) * (3 ** 0) * (5 ** 2) * (7 ** 1)

Is this function provably collision free, assuming the output is not truncated?

Is the function uninvertible for sufficiently large inputs/outputs?

Lastly, does the function become harder to invert if the output is modified (i.e. truncated or rotated)?

Edit in response to an answer:
Let me rephrase the question to be more accurate with what I was actually doing. Suppose we iterate through integers, starting at 0 and incrementing by one. Convert each integer to it's binary form and process it in the manner described above. Do any output values produced this way ever collide?

No, it is not collision-free. All possible sequences of 0's produce the same output:

0    --> (2 ** 0) = 1
00   --> (2 ** 0) * (3 ** 0) = 1
000  --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1

In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.

This could be easily solved by initializing the exponents to 1, and not to 0.

Anyway, I'm afraid you have not discovered anything new. The Fundamental theorem of arithmetic states that any positive integer can be represented uniquely by a product of prime numbers:

$$n
= p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}
= \prod_{i=1}^{k}p_i^{\alpha_i}$$

Your idea is basically a method for interpreting the bit string as the sequence of exponents $\alpha_1, \alpha_2, ..., \alpha_{k}$.

It is also very easy to invert (leaving aside the issue of the number of trailing 0's). Let us assume that $f(s) = n$. If $n$ is divisible by 2, then the first bit of $s$ is 1. Now you divide by 2 and if the result is divisible by 2, then the next bit of $s$ is also 1. Repeat until it is not divisible by 2, and you know the next bit is 0. Repeat this process with the divisibility of 3, 5, 7, etc.

With respect to the new question you added: yes, there are collisions.

For example: $f(1) = f(2) = f(4) = ... = f(2^k) = 2$

In fact, for any integer $n$, it can be seen that $f(n) = f(n\cdot 2^k)$, for every integer $k>0$, which means that for each integer there are infinite collisions.


Can I use an ECDH Shared Secret from the same Private / Public Key Pair? I'd like to know if using the ECDH shared secret of a static EC Private Key with it's own corresponding static EC Public Key causes a problem / weakness.

(edit) not asking if it's ok to re-use the keys multiple times.  Static EC Keys are known to be ok in this usage case.

Background:

In this environment, several agents are producing and consuming data, and the streams are being protected with static ECDH keys.

The ECDH Shared secret is hashed before it is used as a key in the asymmetric stream cipher. The shared secret will be the same each iteration / connection.

The stream is eventually stored to disk (encrypted)

Typical usage (not considered a problem):
$$
Alice( public ) : \ Q_A = d_A G
$$
$$
Bob( private ) : \ d_B $$
$$
ECDH Secret (Alice Bob) = d_B Q_A = d_B d_A G
$$

Normal so far...

Question Case:

In some instances, the Producer and Consumer are the same agent, and this ECDH secret devolves into:

$$
ECDH Secret (Alice Alice) = d_A Q_A = d_A d_A G = (d_A)^2G
$$

Is this a problem?

No, it's not a problem.

What you've found is known as the square computational diffie-hellman problem(SCDH) and it can be shown that this is equivalent to the computational diffie-hellman problem(CDH).

For completeness:
SCDH:
Given $g$ (your $G$) and $g^x$ (your $Q$), find $g^{x^2}$ (your $d_A^2G$).

It is shown here that this problem is as hard as the traditional diffie-hellman problem (below):
CDH:
Given $g,g^x,g^y$ find $g^{xy}$.


"Probability" of an ECDSA signature The article Elliptic Curve Digital Signature Algorithm in Bitcoin's wiki  talks about signatures having probabilities (as in Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50%, and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.).

What does “probability” mean in this context?

It's the probability that an ECDSA signature (over the Bitcoin curve, secp256k1) will have the corresponding size. In other words, 25% of the secp256k1 ECDSA signatures have 73 bytes, 50% of them have 72 bytes and 25% of them have 71 bytes. Of course, after the signature is generated its size is settled and the probability does not apply anymore.
(The reason is that an ECDSA signature is the ASN.1 encoding of a structure with two integers. Each encoded integer requires a bit to indicate the sign, even though in ECDSA they are always positive. Therefore, if the upper bit of the integer is set, then the encoded integer will require a whole byte to store the sign bit since the integers have 256 bits, a multiple of 8. There is a chance of roughly 50% of an integer in the secp256k1 ECDSA signature having the upper bit set, requiring a whole byte for the sign bit, which creates the 25%/50%/25% split over two integers.)


SHA1 multipart calculation Is it possible to combine SHA1 digest values to get the SHA1 of the concatenated parts ?
I know the "S1" SHA1 of "part 1" and the "S2" SHA1 of the "part 2" and I would like to know the SHA1 of the "part 1" concatenated with "part 2" calculated from "S1" and "S2".

Is it possible ?

No.

Something similar which might be confused:

If $M$ is an unknown message and you know $h = \operatorname{hash}(M)$ and $l = \operatorname{length}(M)$, then for many hash functions it is possible to calculate the hash $h'$ a message $M' = M\ ||\ P\ ||\ X$, with $P$ only depending on $l$ (and the hash function) and $X$ arbitrary chosen by me (or by someone else).

It is still necessary to know $X$ to do the attack, mere knowledge of $\operatorname{hash}(X)$ doesn't help.

This attack (length extension) applies to many older hash functions, including MD5, SHA-1, and all hashes of the SHA-2 family. It doesn't apply to any of the SHA-3 candidates (because resistance against this was a criterion).


Would knowing the random seed help to break AES or similar? Consider I knew the seed of the random number generator that Bob uses to send encrypted emails to Alice. Would I have an advantage in deciphering the message? Also, how does, for example, openssl generate a completely random seed so the rest of the generated sequence isn't discovered? Am I missing something here?

Yes, it can hugely help. There are many examples, but the DUHK attack is as good as any. This allows you to passively attack cryptosystems with the following characteristics:

  It uses the X9.31 random number generator
  The seed key used by the generator is hard-coded into the implementation
  The output from the random number generator is directly used to generate cryptographic keys
  At least some of the random numbers before or after those used to make the keys are transmitted unencrypted. This is typically the case for SSL/TLS and IPsec.

The reason it is specific to the X9.31 PRNG can be found here (in short, X9.31 has a "long term seed key").
The idea is that if you know the long term seed key, and see some direct output (the 4th assumption), you could recover the state of the PRNG, which is then sufficient (via the 3rd point) to recover the generated cryptographic keys.

Heuristically, if your PRNG starts with too little entropy, the outputs of it are "less random" than other parts of the protocol assume, which can break the other parts of the protocol.

As for how devices generate random seeds, they typically poll a system RNG (typically /dev/urandom/ on UNIX devices). How does /dev/urandom/ generate random numbers?
From the environment (see here for some discussion). I do not know what is currently used in each device/OS, but generally (theoretical) cryptographers mention things like:

Measuring temperature fluctuations on the CPU
Measuring timings on various input devices (keyboards/mice), and in general other "random" information from external devices

These may not all be used in practice, but give some intuition for what "random sources" a device may have available to it.
Note that certain devices (say embedded devices) may have less sources available --- this has led to attacks on embedded systems. A followup paper to an attack. This paper includes the following motivation of their work:

  Motivation: Our work is inspired by the recent paper of
  Heninger, Durumeric, Wustrow, and Halderman [16], which
  uncovered serious flaws in the design and implementation of
  the Linux kernel’s randomness subsystem. This subsystem
  exposes a blocking interface (/dev/random) and a nonblocking interface (/dev/urandom); in practice, nearly
  all software uses the nonblocking interface. Heninger et al.
  observe

  that entropy gathered by the system is not made
  available to the nonblocking interface until Linux estimates
  that 192 bits of entropy have been gathered, and
  that
  Linux is unnecessarily conservative in estimating the entropy
  in events, and in particular that on embedded systems no
  observed events are credited with entropy.

  These two facts
  combine to create a “boot-time entropy hole,” during which
  the output of /dev/urandom is predictable.

  The Linux maintainers overhauled the randomness subsystem in response to Heninger et al.’s paper. The timing
  of every IRQ is now an entropy source, not just IRQs for
  hard disks, keyboards, and mice. Entropy is first applied to
  the nonblocking pool, in the hope of supplying randomness
  to clients soon after boot. (Clients waiting on the blocking
  interface can block a bit longer.)

Note that the Heninger et al attack mentioned was the Mining your P's and Q's attack, which was an attack on RSA.
RSA has a public key which contains $n_i = p_iq_i$, the product of two semiprimes.
The attack essentially collected many $n_1,\dots, n_k$ RSA moduli, then searches (pairwise) for common divisors among all of them (which can be made quite efficient).
Any such common divisor allows you to factor two moduli.
If PRNGs were working properly then the theory behind this predicts this will fail.
This attack exposed that the PRNGs were not working properly, due to insufficient entropy early in the boot process in embedded devices.

Note that "insufficient entropy" can be viewed as "having some partial information about the seed". Knowing the seed completely is an extreme example of this, and while this won't necessarily mean every cryptosystem breaks, many break from weaker assumptions.


Encryption algorithms that require more work to decrypt versus encrypt? Are there any encryption algorithms that require significantly more work to decrypt, versus the amount of work required to encrypt?
I'm looking for a method of fast encryption, but which will require much more CPU time to decrypt later, as a method of spam prevention (prevent people from decrypting too many files in a short amount of time).
One thing I should mention, is that the encryption key itself will be public knowledge.
I'm not trying to lock anyone out, I just want to force them to work before they can acquire data.

Since the encryption key is public knowledge, one simple method is to encrypt using a standard symmetric algorithm (such as AES), but randomize a portion of the encryption key.
For example, if you use AES-256, and the encryption key is published, but each individual encrypted file has 12 bits of the key overwritten with a random value (which is never saved or stored anywhere), so decrypting the file will require the decrypting device to brute-force the final 12 bits of the key.
The number of bits randomized, can be adjusted based on how quickly people are able to crack it, to hit whatever sweet-spot of required work you are looking for.
IMPORTANT:
It should be noted, as A. Hersean pointed out in the comments, that this method may have significant negative side effects:

... proof-of-work is a bad idea: motivated people will have enough work power, while normal users will be negatively impacted. It will most likely not solve your problem and just make your system use so much power that nobody would want to use it.


Should number of iterations of PBKDF2 stay secret? Let's say I encrypt my passwords with PBKDF2 and store it somewhere. Now let's say it was stolen and the hacker, who stole it knows it was hashed with PBKDF2.

Does a knowledge of number of iterations make it easier to brute force the password?
Reasons?

Normally we store the number of iterations with the hashed password. In the same string actually.
This allows us to upgrade the number of iterations in a running system and in an interm phase have different passwords with different number of iterations.

If however you tried to keep the number of iterations secret, an attacker who knows the password for a single account could easily discover the number of iterations.

If we really can't tell the number of iterations an attacker would need to assume an upper bound and both do more interm checks but more importantly may continue longer then needed if his upper bound isn't tight.

I do not recommend trying to hide this information.


Indistinguishable encryptions in the presence of an eavesdropper equivalence I'm trying to prove that definition 5 and definition 6 in this document are equivalent. This is what I've done at the moment: Asume that the scheme has Indistinguishable encryptions in the presence of an eavesdropper (definition 5), then:

$$\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=1]=\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=0]+\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]=(1/2-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1])+\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]\leq 1/2+negl(n)$$

And we get that:

$$\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1]\leq negl(n)$$

Now I'm trying to prove that:

$$\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,0))=1]-\mbox{Prob}[\texttt{output}(\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n,1))=1]\leq negl(n)$$

For finishing the inequality with the absolute value. Is there someone who can help me with this? Thanks!

PS: I can understand the last line in the definition 6 in the document I've given: where the probability is taken over...

Can someone explain me that?

I've found an answer to my question, I'm going to post it because it can be useful to someone out there.

The point is that, if we assume that $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=1]\leq 1/2+negl(n)$, then $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=0]\leq 1/2+negl(n)$ too (if this were not to happen, then we could create an adversary that solves the experiment with a better probability than $1/2+negl(n)$).

This allows us to use the same argument I've used for proving the first inequality for getting the inequality with absolute value.


The security of Hidden Field Equations - sentence I am reading this paper "The security of Hidden Field Equations (HFE)"

and at the end of the page 3 the author wrote:

  The random oracle paradigm would be to ignore that the function
  formulae exist.

I know what is the random oracle paradigm but sincerily I do not understand why the

"The random oracle paradigm would be to ignore that the function
 formulae exist."

Could you explain me please what that sentence means?

Random oracles are used in cryptographic proofs as a way to abstract away a complex function, making the analysis easier (ie "ignore the actual function, and model it as a random oracle instead").

In the paragraphs before the sentence you highlighted, they propose to measure the "complexity" of an equation / function by the degree of its multivariate polynomial representation over $GF(2)$.

In the context of the surrounding paragraphs, I would interpret that sentence to mean

  The random oracle paradigm abstracts away the complexity of the function, which renders our complexity metric useless.


Question on Miller's algorithm (change the input m) From the book titled " An Introduction to Mathematical Cryptography" (Chapter 5,page 322), we know that the miller's algorithm returns a function $f_P$ whose divisor satisfies
$$div(f_P) =m[P]-[mP]-(m-1)[O],$$
where $O$ is the point at infinity. When the order of $P$ is $m$, we will get
$$div(f_P) =m[P]-m[O]$$.

I am thinking what if we change the input $m$ to $m^\prime=km$. Then we will get a function $f_P^\prime$ whose divisor satisfies
$$div(f_P^\prime) =km[P]-[kmP]-(km-1)[O]=km[P]-km[O].$$
My question is what's the relation between the functions $f_P$ and $f_P^\prime$. Or given a point $S$, what's the relation between $f_P(S)$ and $f_P^\prime (S)$.

Consider the rational functions $f_P^k$ and $f_P'$. Since $\operatorname{div}$ is a homomorphism of semigroups (i.e. $\operatorname{div}(fg)=\operatorname{div}f+\operatorname{div}g$), we have
$$\operatorname{div}(f_P^k)=k\cdot\operatorname{div}f_P=k\cdot(m[P]-m[\mathcal O])=km[P]-km[\mathcal O]=\operatorname{div}f_P'\text.$$

Now with theorem 5.36 of "An Introduction to Mathematical Cryptography", this implies that there is a nonzero constant $c$ (from the base field) such that
$$f_P^k=cf_P'\text,$$
therefore the answer to your question is: Up to multiplication by a nonzero constant, $f_P'$ is the $k$th power of $f_P$, and this carries over to the result of evaluating these functions at some point, that is $f_P(Q)^k=cf_P'(Q)$.


Cryptographic Primitive Method Is there any cryptographic primitive bijective (one-to-one and onto) function for creating cryptographic tools like symmetric encryption/decryption, Hash code generator, MAC, HMAC and Random number generator?

As CodesInChaos notes, a secure block cipher satisfies all the criteria in your question:

An $n$-bit block cipher is a (keyed family of) bijective function(s) on the set of $n$-bit bitstrings.
A block cipher can be used for symmetric encryption in any of several modes of operation.  In some of these modes (notably OFB and CTR) the block cipher effectively acts as a keystream generator for a synchronous stream cipher.
A block cipher can be used in several ways to construct a one-way compression function, which in turn can be used to construct a cryptographic hash function.  Indeed, most commonly used cryptographic hash functions are based on block ciphers.
A hash function constructed from a block cipher can certainly be used in the HMAC construction, but there are also several ways (such as CBC-MAC, OMAC and PMAC) to construct a MAC directly from a block cipher.
As noted above, a block cipher in CTR or OFB mode becomes a stream cipher, which is essentially the same thing as a cryptographically secure pseudorandom number generator.

Indeed, insofar as there exists a "universal building block" in modern cryptography, block ciphers are it.  Pretty much the only thing they cannot do is public-key cryptography.

That said, block ciphers certainly aren't the only possible building block.  For example, a cryptographic hash or pseudorandom function can be used in the Feistel / Luby–Rackoff construction to construct a block cipher, which can then be used to construct all the other things described above.


Which is the best algorithm for large scale file encryption other than AES? I've been looking for a fast, powerful and robust algorithm for encrypting large files with authentication .
I would like to implement the algorithm on my own without using third party software. I've used different modes of AES but the software implementation is prone to side channel attacks. Besides the most commonly used AES 256 GCM has an encryption with authentication size limit of 64 GB. I've tried other famous ciphers like Xchacha20/ XSalsa20 with poly1305, but I cant get around their respective size limits (I can only encrypt upto 256 GB with XChaCha20 - Poly1305 - IETF version ) !

Is there a powerful enough cipher other than the above that I can use for large scale encryption with authentication ?
What modifications should I apply to existing algorithms like Xchacha20 / XSalsa20 with Poly1305 for unlimited encryption with authentication?

You shouldn't encrypt large files as if they were just one message; you should split them up into small chunks and encrypt each chunk separately with an AEAD, using some construction that:

Protects against modification, reordering, insertion and deletion of chunks;
Protects against truncation of the file;
Rotates keys once too much data has been processed by a single key.

One reason is that cryptographic libraries typically are implemented so that you need an entire message in memory to encrypt it. Another reason is that users of tools often expect that the output will be produced incrementally (so they can pipe it to other tools), but typical AEAD ciphers demand that you never output the decryptions of forged ciphertexts, so encrypting the whole file as just one message requires you to authenticate the whole thing before you produce any output. (Not that outputting authentic prefixes of a forgery is always safe.)

See:

https://www.imperialviolet.org/2014/06/27/streamingencryption.html
https://github.com/miscreant/meta/wiki/STREAM
https://libsodium.gitbook.io/doc/secret-key_cryptography/secretstream

Once you have adopted this paradigm, the message length and ciphertext size limits in ciphers that you're concerned about don't matter anymore, because each you only ever encrypt short messages and you can build in key rotation if you go past the ciphertext limit for a single key. For example the Libsodium secretstream API I link to above offers this feature:

  Ratcheting: at any point in the stream, it is possible to "forget" the key used to encrypt the previous messages, and switch to a new key.

So if you just keep a count of how much data you've processed and instruct the library to rekey when it approaches a limit, you have, as the documentation puts it, "no practical limits to the total length of the stream."


IPSec recomendations about rekeying IPSec like strongSwan can be configured to do rekeying after time or bytes transferred or packets transmitted. Is there any recommendations to set those settings? Maybe according to algorithms used?

This isn't specific to StrongSwan, but here is a Cisco article relating to rekeying. In this example, keys are replaced every 1,000 or 10,000 seconds. It is, obviously, best to rekey as often as possible, while taking into consideration hardware limitations. I would say that every few hours would be more than enough.

-Hope this helps.


Is compressing data prior to encryption necessary to reduce plaintext redundancy? As explained in William Stallings' Book, in PGP encryption is done after compression, since it reduces redundancy.

I couldn't relate encryption strength with redundancy. Could anyone explain more on that?

There is at least one way in which compression can weaken security; it has to do with the fact that essentially all methods of encrypting arbitrarily long message will inevitably leak information about the length of the input.  The only way to avoid this leak is to pad all messages to a constant length before encrypting them — but if the messages are compressed, the compression will change their length in a way that will depend on their content, which may allow an attacker to obtain information about the content based on the length of the ciphertext.

For a practical example of such an attack, see e.g. "Uncovering Spoken Phrases in Encrypted Voice over IP Conversations" by Wright et al. (2010).


1024 RSA Hash Signature attack. Forge a valid signature I have an RSA signature of 1024 bit where i know the following:

Public modulus N
Public exponent (0x03)
Cypher message

Summary:

An MD5 hash is calculated from a collection of byte and is used as message (M).

Having an hash that is a perfect cube forge a signature accepted as valid will be easy.

Question:

Can someone give advice to find a pratical way to hashing messages changing ending until their hash will be a perfect cube?

A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach.  And, you can't control the output of MD5, and so it'll give you effectively random values.

A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ is the MD5 hash of the $i$th message).  Then, you would factor each $M_i$, and look for linear combinations of common factors.  At the same time, you would hash a large number of messages, and look for a message  with an MD5 hash $M$ that can be represented by a linear combination of signed messages $M = M_a^{i_a} M_b^{i_b} ... M_z^{i_z}$.  When you find such a linear combintation, you then have the signature for that message $S = S_a^{i_a}S_b^{i_b} ... S_z^{i_z}$


Degree of M and Max Sequence Length for LFSR For the LFSR  mod 2, determine the degree of m and maximum sequence length
s_(i+3)≡ s_i+s_(i-2)+s_(i-4) mod 2

determine the degree of m and the maximum sequence length.

I can get the degree of $m$ easily by taking $2^{(m -1)}$, but I am confused about getting the degree of $m$. I don't even know what this is referring to here. Any help?

Let $i+3=j$ so your recurrence becomes $s(j)=s(j-3)+s(j-5)+s(j-7)~mod~2.$ The degree of the corresponding connection polynomial is $7$ and the polynomial itself is $c(x)=1+x^3+x^5+x^7.$ If the polynomial is primitive, then the period of the resulting LFSR sequence with nonzero initial state is $2^7-1=127.$ However this polynomial is not even irreducible since it is $(x+1)(x^6+x^5+x^2+x+1)$ modulo 2. Thus your sequence will not be maximum period. Depending on the initial conditions it will be generated by either $x+1$ or the degree 6 factor. The degree 6 polynomial turns out to be primitive, however.


Number encryption algorithm I have a list of numbers. I will be calling a service(let's say accountant service) which is going to perform some operation on these list of numbers and will return me the final result number.

I don't want to pass my data in plain format. I want to encrypt numbers in such a way if service performs any arithmetic operation and return me the result, I will be able to decrypt it back with actual result.

You are looking for a combination of homomorphic encryption and verifiable computation.

Homomorphic encryption plays a part in this, but it is possibly not the only tool that you need. Homomorphic encryption can preserve the confidentiality of your values, but it cannot ensure that the computation was performed as you specified. That is what verifiable computation does.

Depending on the nature of the operations that you need to perform, you may not require fully homomorphic encryption. If you only require the ability to add ciphertexts together, and you don't care about post-quantum resistance, then the Paillier cryptosystem is an option for you. It's not standardized to my knowledge, but it's older and has been used in other projects.

Otherwise, if you really want/need a standardized homomorphic encryption algorithm, you might opt to use one of the submissions that were recently submitted to NIST. These algorithms are not standardized yet, but they are on track to be, assuming that they are not broken before then. Many of them are based on lattice problems, which implies that may offer homomorphic encryption.

While verifiable computation doesn't have a standardized solution yet (that I am aware of), there has been work into implementing it: See Pinocchio and Pepper.


Can a hash of the original plain text file be used to brute force an encrypted copy? I have encrypted files stored on a public cloud, in the same directory on the cloud I have the sha256 hash of the files before they were encrypted in a text file.

The keys used to encrypt the files are stored locally. Is it plausible that someone after downloading the files could use the original hashes to help brute force the encryption?

I am thinking that it would provide no advantage but I just wanted to check.

It depends on the contents of your files. If the contents has high entropy and is unpredictable then you're probably safe.

However, if the contents is a password or a pin number, then brute forcing it should be trivial, it is for this reason that we use slow hashing.

Another scenario might be if the contents had a value which was commonly known (ie, a pirated movie). If the hash of that file is common knowledge, then so is the contents of your encrypted file.

To err on the side of caution, it's probably better to ensure the integrity of your file with a HMAC or Authenticated Encryption. You might want to read this thread.


What is the security loss from reducing Rijndael to 128 bits block size from 256 bits? As you know in the past few weeks it has emerged that NIST/NSA have been involved in weakening encryption standards over a long period of time so that they can retain the ability to break encryption used by corporations and the general public. We've already seen evidence of that with the Dual_EC_DRBG which has been recently disavowed by NIST after public outcry. That's probably a red herring, I think there's another smoking gun here.

I want to highlight a particular issue in the Advanced Encryption Standard process. The Rijndael algorithm had the option of block sizes of 128, 192 or 256 bits to match the key sizes. When that algorithm was decided as the winner, NIST went away and then defined a "restricted" block size of 128 bits for AES. Apparently that was what the spec called for in the first place.

However that doesn't make sense. If you were concerned about security, why would you have a 256 bit key size, but not have a matching block size? It would appear to be more secure to keep them at the same length. For example, a modern cipher like Threefish which has key sizes of 256, 512 or 1024 bits, also has matching block sizes of 256, 512 or 1024 bits.

Can the overall security of AES with a 256 bit key be reduced from
2256 to 2128 by attacking the lower block size?
Could that be combined that with various other attacks on AES which
would reduce the 2128 bit security to even less e.g.
2100 bits?
Now that commercial quantum computers are viable (just one D-Wave Vesuvius is ranked in the top 10 of the TOP500 list), and assuming the NSA have taken advantage of that and constructed a quantum cluster in the basement of Fort Meade/Utah data center, if they employed Grover's algorithm which runs in O(N1/2) time, would that reduce the security of AES to 264 for all key sizes or worse 250 with attacks?

Extra links:

https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
https://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy
http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/
https://www.scientificamerican.com/article.cfm?id=google-nasa-snap-up-quantum-computer-dwave-two
https://dwave.wordpress.com/2011/12/01/vesuvius-a-closer-look-512-qubit-processor-gallery/
http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-computer-usc/
http://arstechnica.com/security/2013/09/nsas-pipe-dream-weakening-crypto-will-only-help-the-good-guys/
https://en.wikipedia.org/wiki/Grover%27s_algorithm
https://en.wikipedia.org/wiki/Threefish

Security issues related to block size boil down to the following: a pseudorandom permutation is not a pseudorandom function, and the difference becomes visible when you query the function too many times. Imagine a function which accepts as inputs, and offers as outputs, elements from a set of size $N$. For instance, the inputs and outputs are blocks of $n$ bits, so $N = 2^n$. If you feed this function with different input values, then you will first get as many different output values. However, with a PRF, you expect to obtain a collision at some point: a new input which yields the same output as a previous distinct input. On average, this should occur after about $\sqrt{N}$ queries. With a PRP, you will never get a collision, because permutations are, by definition, injective.

So when encrypting with a block cipher, using blocks of $n$ bits, you begin to have problems when processing more than $2^{n/2}$ blocks with the same key. 3DES has 64-bit blocks, so encrypting more than $2^{32}$ 8-byte blocks with 3DES can be troublesome: that's 34 gigabytes or so, a value which is not so huge nowadays. To avoid this problem, NIST launched an open competition for an "Advanced Encryption Standard" (the AES) with the following rules:

128-bit blocks.
Keys of 128, 192 and 256 bits.
Not slower than 3DES (many candidates turned out to be widely faster).

And that's what they defined. They did not really care that the selected candidate (Rijndael) had extended versions which could accept other block sizes; 128 bits were sufficient.

In all of the above, the important point is that the $2^{n/2}$ figure is related to the number of queries. It is generally estimated that, for an attacker, obtaining $x$ pairs plaintext/ciphertext is widely more difficult than trying out $x$ potential keys, since the former requires cooperation of the target system, while the latter requires only some computing power on the attacker's own machines. You'll have a hard time finding an "honest system" which needs to encrypt $2^{68}$ bytes with AES (that's close to 300 billions of gigabytes), and even more so an honest system where the attacker can get 300 billions of gigabytes of known plaintext while still being "locked out" (if the attacker can get the honest system to process that much data, then what left is there to attack ?).

Basically, the block size and the key size work on different scales, and it just happens, fortuitously, that "128 bits" is a nice level for keys (exhaustive search on $2^{128}$ keys is not feasible with current technology), and also a nice level for block size ($2^{64}$ blocks of 16 bytes of known plaintext is not a realistic attack scenario with current technology).

Notably, if a quantum computer ever sees the light, that computer would be able to break a 128-bit key in $2^{64}$ effort, but it would do absolutely nothing about the issues related to block size: 128-bit blocks would still be as good as they are today.

All of the above is for usage of a block cipher for encryption. When a block cipher is to be reused as a core element for something else, e.g. a hash function, then other constraints may apply. Typically, for the Skein hash function, the internal block cipher had to offer much larger blocks if the hash function was to live up to its promises (note that a hash function has no key, so we are far from the attack model of an encryption system). This is why Threefish, the block cipher in Skein, has big blocks. This is not because big blocks are good for encryption; this is because big blocks are necessary when a block cipher is turned into a hash function the way Skein does it.

A similar case is Whirlpool, which uses the "W" block cipher, which is a Rijndael derivative (with even larger blocks -- 512 bits -- and a revamped key schedule).

As for D-Wave systems, they are not "true" quantum computers; they compute a specific problem instance in a "somewhat quantumish way", but are not able to apply the nifty algorithms which eat crypto for breakfast. The difference is qualitative, not a question of mere tuning. See this for pointers.


How small are we talking about when defining the small public/private key exponent I've been wondering about the 'small' part of the attacks on RSA, like the small public key exponent and the small private key exponent and what's not really clear is how small are we talking about? Like is it how small with respect to the large prime numbers or what exactly?

Exponentiation by squaring takes time approximately proportional to the number of bits in the exponent. 3 has been used but allows attacks on some weak padding schemes. 65537 ($=2^{16}+1$) is the one used widely in practice.

Cf. Impacts of not using RSA exponent of 65537