How does secret sharing solve the partial exposure problem? I have been trying to understand how secret sharing methods like Shamir's secret sharing solve the problem of a share revealing information about the secret. I guess there are some random numbers involved, but how is it done mathematically?

A simple partial explanation addressing your "random value added", too long for a comment. This works well for the trivial case of two shares: Given a secret $x$, split it into $r$ and $x-r$, where $r$ is a random number. Having both shares, you can get the secret by as their sum.

Having only one share, you can do nothing at all, assuming there are no bounds on the variable values. This wouldn't work with integers, so some finite field gets used, e.g. modular arithmetic with a prime modulus $p$. As an example, consider $p=101$ and $r=42$. Now each secret $x$ is equally possible, e.g., $x=10$ corresponds with the other share $x-r = 10-42 = -32 = 69$ (computed modulo 101). This is what information-theoretic security means in this trivial example.

It's easy to extend this for an arbitrary number shares where all of them are needed to reconstruct the secret. I hope it can help you to understand the general method described elsewhere.


Is it secure using LWE-based cryptosystem under RLWE-based parameters? I'm computer guy having trouble with cryptography.

I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions.

I was implementing Threshold version of BGV encryption [AJW12] using HElib optimized under the RLWE assumption, and I found out that [AJW12] proved the security under the LWE assumption.

A paper [LN16] says that the RLWE is a special instance of the LWE problem.

So, I think that [AJW12] encryption under RLWE parameters is still secure, but I'm not sure.

Am I right?

Am I right?

Possibly, but it's not guaranteed, even if we assume that LWE is secure.

RLWE is a special instance of LWE; however that doesn't mean that RLWE is secure if LWE is.  The LWE assumption holds if we have a random instance; that is, one chosen from a specific probability distribution.  The RLWE problem has a different probability distribution; one in which the vast majority of LWE instances have probability 0.  The probability that the LWE will choose an instance which has a nonzero probability for being a RLWE instance is negligible.  It may be that the RLWE instances happen to be weak; that would not practically impact the security of LWE.

Now, it's not known that any such weakness applies specifically to RLWE; however it's also not proven that there isn't, either.


Why is H(message||secret_key) not vulnerable to length-extension attack? Given a Merkle-Damgård hash function $H$, I know that an attacker can forge a message protected by a MAC computed as $H(\textrm{secret_key}||\textrm{message})$.

Why can't he perform the same extension attack on a MAC construction $H(\textrm{message}||\textrm{secret_key})$?

How does the length extension attack against $H(k||m)$ work?

For Merkle-Damgård hashes, if you know $H(x)$ but not $x$ you can still choose an $e$ and then compute $H(x||p||e)$. With $x=k||m$ you can compute $H((k||m||p)||e)=H(k||(m||p||e))$ which is a valid authentication tag for $m||p||e$.

Why doesn't it work against $H(m||k)$?

With a length extension an attacker chooses the extension. The only non trivial way to make $H(m||k||e)$ a valid tag is if $e$ ends with $k$. Since the attacker doesn't know the secret key they can't put the key at the end of $e$ and thus can't produce a valid tag.

What should I be using?

Either use H(k||m) with a hash that's not vulnerable to length extension attacks, such SHA3. Or use HMAC with  an older hashfunction, such as SHA2. $H(m||k)$ is not ideal because it can be attacked by finding collisions of $H$. Collisions are one of the easier attacks crypto-analytically and require a hashfunction twice the width of the target security level. e.g. SHA-256 for a 128 bit security level.


Why is modulo being used for congruence in SHA-2 padding when the outcome is always the same? I am reading up on SHA-2 algorithms and I came across this paper: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

In section 5.2.1 it talks about the formula for padding a message. There is states there is congruence between:

$$\text{message length} + 1 + k$$
and $$896 \pmod{1024}$$

To calculate $k$ (the amount of zeroes) the following example is given for a message length of 24:

  896-(24+1) = 871

I am wondering though why is $896 \pmod{1024}$ used when the outcome of this is always constant? Why not simply use the number 896?

We are given an $\ell$-bit message and we are trying to find the smallest nonnegative $k$ such that $\ell + 1 + k \equiv 896 \pmod{1024}$.  This means we are trying to find $k$ such that $\ell + 1 + k$ is 896 plus an integer multiple of 1024: $\ell + 1 + k = 896 + n\cdot 1024$, for some $n$.

Suppose you have an 895-bit message, $\ell = 895$.  A single bit of padding, with $k = 0$ zeros, makes its length a multiple of 1024 plus 896: $895 + 1 + 0 = 896 + 0\cdot 1024$.

Suppose you have an 897-bit message, $\ell = 897$.  The smallest amount of padding you can add to make it a multiple of 1024 plus 896 is 1023 bits, with $k = 1022$ zeros: $897 + 1 + 1022 = 896 + 1\cdot 1024$.

Another way to phrase ‘a multiple of 1024 plus 896’ is ‘a multiple of 1024 minus 128’.  The point is that we're adding the smallest amount of padding that will fill a 1024-bit block with room to append the length of the message as a 128-bit integer at the end.  The complete padded input is $$m \mathbin\Vert 1 \mathbin\Vert 0^k \mathbin\Vert \operatorname{be128}(\ell)$$ where $\operatorname{be128}(\ell)$ is the 128-bit big-endian encoding of the integer $\ell$, and $0^k$ is as many zeros as you need to make this an exact multiple of 1024 bits long.

We want an exact integer multiple of 1024 bits in the padded message so that we can break it into blocks $b_1 \mathbin\Vert b_2 \mathbin\Vert \cdots \mathbin\Vert b_n$ to compute $$f(f(\dots f(f(\mathit{IV}, b_1), b_2)\dots), b_n),$$ where $f$ is the internal compression function defined on a 512-bit state and a 1024-bit block, and $\mathit{IV}$ is the standard initialization vector.


Discrete logarithm weak group I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ .

I thought one way is to produce a prime $p$ that $p-1$ is an smooth integer which then makes discrete logarithm problem easy using Pohlig-Hellman algorithm but i couldn't find any algorithm for generating such primes. Trivially, we can generate random numbers and then check if it's prime and if it's prime, check if $p-1$ can be factorized to a set of small prime numbers. It can be done in another way, considering a set of small prime numbers and generating random exponents for every prime in the set, multiplying all primes powered to their exponent. By doing so, we have a number $r$ that can be factorized to small prime numbers and then we can check if $r+1$ is prime.

Clearly these methods are just trial and error and may take a long time to find such prime, specially when it comes to generating 256 bit prime numbers. Is there any better algorithm ?

What are other ways to generate a  256 bit long weak modulus?

Is there any better algorithm ?

Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient.  You say that it's trial and error (and it is), however it's about as efficient as the traditional algorithms we use to search for primes; if you're looking for an $q$ bit prime, then you'd expect to need to try an average of $\log(2^q) / 2 = q \log(2)/2$ sets of primes before finding one that makes up a prime (actually, a bit less, because you know apriori the numbers you generate won't have $q_1, q_2, ..., q_n$ as a factor).

An alternative approach to creating a weak DLog problem is to make $g$ weak; that is, generate a $p$ of the form $2qr + 1$, where $q$ is a small prime and $r$ is a large one (and the same algorithm can be used to seach for it).  Then, you select $g$ to be of order $q$ (that is, you select a random value $h$ and set $g = h^{2r} \bmod p$, and check that it's not 1); if $q$ is an $m$-bit prime, then the discrete log problem will take $O(2^{m/2})$ time; for example, $m=32$ makes this solvable in milliseconds.

Of course, the use of either approach can be fairly easily detected by someone examining $p$ and $g$...


Does ECC's cofactor affects ECC's private key selection? I am doing a project using ECDH with Curve25519. I use mbedtls library, in the implement, I realize that the private key of Curve25519 is clear 3 last bit, or it is divide by 8 and the cofactor of Curve25519 is 8 too. I looked to another curve (Curve448) it cofactor is 4 and the private key is divide by 4 too.
I tried choosing a non-divisible key for 8 and the algorithm still works. So does cofactor affects private key on ECC.

Does ECC's cofactor affects ECC's private key selection?
If I intentionally choose a key that is not divisible by 8, is there a problem?

Diffie-Hellman on Curve25519 and Curve448 is specified on RFC 7748 and the algorithm clearly mentions that the scalar must be a multiple of the cofactor (by setting the 2 or 3 least significant bits to zero depending of the curve).

If you choose a key with least significant bits not all zeros, then it depends of the implementation. An correct implementation following the RFC will make sure the least significant bits are set to zero before the scalar multiplication (whether when the key is imported in the program, or just before the scalar multiplication).

Now, you can eventually make an implementation that does not clear the least significant bits, the algorithm will give you something, but then it is vulnerable to small subgroup attack.

If someone sends you a small order point (let's say $4$), then by getting rid of the least significant bits of your private key, the result of the algorithm will give $0$ which is consider invalid and the small order point will be automatically detected.


How comparable is OFB to a one-time pad? This is a rather trivial question, I just want to see if I get the concept right.

In OFB you generate a pseudorandom stream based on some nonce, and you XOR that with the message to get the ciphertext. This sounds a lot like a one-time pad but I don't see the parallelism anywhere in literature. Am I missing something?

As @CodesInChaos said, OFB is a stream cipher.  The one-time pad is a stream cipher, too.  One difference is that the one-time pad is information-theoretically secure, while OFB is computationally secure.


Design a OT-based Private Set Intersection protocol to obtain $A \cap B \cap C$? This is a tutorial question for a Foundations of Privacy computer science course, I'm unsure on how to tackle it because we haven't talked much about these particular topics in class.

(a) Assume Alice, Bob and Carlo respectively have the data set $A = \{ \ldots \}$, $B = \{ \ldots \}$, $C = \{ \ldots \}$. How to use the OT-protocol to design a Private Set Intersection protocol among Alice, Bob, and Carlo, so that each one can obtain $A \cap B \cap C$. You can design your solution based on the OT-based PET (Private Equality Test) protocol in the figure below.

PET Figure

(b) How to use the OT-protocol to design a privacy-preserving integer comparison protocol between two parties, e.g., two integers $x,\space y$, both of them are $n$ bits, where $x \gt y, \space x \lt y,$ or $x = y$. You can design your solution based on the above OT-based PET protocol. (Hint: you may disclose two bits information in your solution!)

I think I understand what to do for (b):

If Alice and Bob use a homomorphic encryption algorithm, Alice can
use a private key pk and a public key sk. Bob would only have the
public key pk.
Alice then sends $\text{E}(x)$ and $\text{E}(y)$ to Bob. Bob computes
$\text{E}(r(x-y)) =$ $($$\frac{\text{E}(x)}{\text{E}(y)})^r$ using the homomorphic
property, where $r$ is a random number, and returns $\text{E}(r(x-y))$ to
Alice.
Alice recovers $r(x-y)$, and if it is equal to $0$, then $x = y$,
otherwise $x \not= y$.

With this solution, are the only bits disclosed the ones that are given in the comparison result? I'm a little more foggy on how to attempt (a). Any help is appreciated!

I worry that the first problem is harder than your instructor suspects. We had to work a little hard to get a multi party PSI protocol based on efficient OT in our paper

  Practical Multi-party Private Set Intersection from Symmetric-Key Techniques,  by Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, Ni Trieu

If I remember correctly, we may have some optimizations for the 3-party case, but I don't think it falls to the level of a homework assignment.

The real challenge is that the 2-party equality test reveals the outcome of the comparison in the clear to one party. This makes it hard to hide partial intersections. For example, if $x \in A \cap B$ but $x\not\in C$, then Alice must not learn that Bob also has $x$. This suggests that Alice and Bob can't simply use the 2-party equality test on their inputs. In our paper we had to go to extra lengths to hide these intermediate equality test results.


Proof one-time pad is perfectly secret with eavesdropping game definition I have the following definition of perfect secrecy (please assume that the probabilistic version is not available):

If we consider the eavesdropping game given by:
$$\begin{array}{|r | r|} \hline Alice & Eve \\ \hline & (m_0,m_1) = E.m()\\ k \leftarrow Gen() &  \ \\ b \leftarrow fair\_coin() & \\ c \leftarrow Enc_k (m_b) &  \\ & r = E.r(c)\\ \hline \end{array}$$
one says that a symmetric encription system is perfectly secret if there is no attack $E$ which wins the game with probability strictly greater than $1/2$, where winning the game means that at the end of the process $b = r$.

With this definition I have to prove that the $(G,l)$-one time pad (that is one-time pad over groups) given by $Enc_k(m) = m \circ k$ and $Dec_k(c) = c \circ k^{-1}$ is perfectly secret. Here one defines for $m = (m_1,\ldots,m_l)$ and $k = (k_1,\ldots,k_l)$, $m \circ k = (m_1 \circ k_1,\ldots,m_l \circ k_l)$ and $k^{-1} = (k_1^{-1},\ldots,k_l^{-1})$.
My approach
$k$ is uniformly distributed by assumption and since $m_b$ should be independent
of $k$ then $m_b \circ k$ is uniformly distributed. But no attack can distinguish in a uniformly distributed sequence with probability greater than 2.
Is my approach correct?

Might be too late.. but yes the approach is correct. As you said, since the one time pad is being used, Eve doesn't really need $c$(not even choosing the two messages) she could just use some simulator $\sigma$ and generate a random uniform $c' = \sigma((G, l))$ and run $r = E.r(c')$. So the distribution of $(m_0, m_1)$ doesn't matter, r and b are independent. Thus equal with probability at most $1/2$

Now, I'll try to  answer this more "formally".

Notation:  Let $(S, B)$ denote the system that emulates Alice, meaning a systems $S$  correlated with a uniformly distributed bit $B$. $S$ performs the $otp-enc(m_B)$. Let $S_0$ be Alice when the bit is zero(i.e sends $otp-enc(m_0)$, $S_1$ is defined similarly. Let $D$ be a distinguisher(Eve) characterized by a joint distribution $P^{M_0,M_1}[m_0, m_1]$ over the set of possible messages, and an algorithm $R: (G,l) \to \{0,1\}$. $R$ takes a cipher text and outputs a bit.

The setup: Eve is trying to win the bit guessing game wherein a distinguisher $D$ interacts with $(S, B)$ and outputs a bit $R$. The advantage of Eve is $\Delta^D((S, B)) =  2Pr^{D(S, B)}[R = B] - 1$. In other words by how much she performs better than when she just guess.

Now observe that what the question asks is to show that the advantage is 0 for any Eve.

Another type of game Eve could play is a distinction game where Eve is connected and interacts with either $S_0$ or $S_1$ and outputs a bit $R = 0$ if she thinks she is interacting with $S_0$ and outputs 1 otherwise. The advantage of Eve in this game is $\Delta^D(S_0, S_1) = Pr^{DS_1}[R = 1] - Pr^{DS_0}[R = 1]$. I introduce the following result without proof:

$\Delta^D((S, B)) = \Delta^D(S_0, S_1)$., for a uniform $B$.

So we can instead find the advantage of the distinguishing problem, which seems easier. We have that $Pr^{DS_1}[R = 1] = Pr^{KM_0}[m_0 \oplus k = c]  = \frac{1}{|G|^l}$. This is the same for $Pr^{DS_1}[R = 0]$. So $\Delta^D(S_0, S_1) = 0$.

Therefore $\Delta^D((S, B)) = 0$, which is what we wanted to show.

Remark: if Eve were to be allowed to additionally ask for encryption of up to $t$ messages, that would somehow be a proof of information theoretic  ind-cpa security of the OTP. Although some could argue that this notion doesn't really fit with the OTP.


Can Pseudorandom values be used as secure keys? I want to derive $n$ keys from a master key.

I pick a master key $mk$ and use pseudo-random function (PRF) to generate $n$ pseudo-random values, $v_i=PRF(mk,i)$ where $1\leq i \leq n$.
Next, I use key derivation function to generate $n$ keys: $k_i=KDF(v_i)$, where $1\leq i \leq n$. Note that key derivation must be deterministic.

Question 1: Is above scheme a secure way of generating $n$ keys?

Question 2: Can we consider values $v_i$ as secure cryptographic keys?

Yes and yes, as mentioned in the comments.

It is worth noting that Bitcoin wallets use a scheme similar to this in BIP32, a method of creating n various EC keypairs from a single seed deterministically:

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

EDIT: This answer only holds true if  is a CSPRNG.  (This application is sort of why the definition for CSPRNG exists.)


Any benefit to writing a message as a mix of 2 languages before encryption? For example, imagine a message that is a mix of Japanese and English words; Japanese in unicode, English in ASCII. Japanese doesn't use spaces between words.

The sentence structures, anything abstract, and verbs would have to be in Japanese. Anything directly translatable such as colors, transportation machines, proper nouns, etc. would be in English.

Would writing the original message as a mix of 2 languages (especially a Western and non-Western language) contribute to making it more difficult to decrypt?

Historically, there did exist a benefit to using a language that the adversary was not familiar with.  The name for this is code talkers, and the most famous ones (at least in the USA) are the Navajo code talkers of World War II.  The idea was to defeat attacks that relied on statistics about the language used in the plaintext.

In modern cryptography, however, there is no benefit, because modern ciphers are designed to obscure any patterns in the plaintext—even patterns that we haven't thought of.  This is because modern ciphers are expected to be not just "hard to crack," but indistinguishable from random data.

There's a second reason why using multiple languages would not have any benefit, which is that you're using a computer, so no matter what language you use you're still encoding text into a character encoding like UTF-8—and this already gives you statistical patterns that an attacker could look for.

Third reason: English and Japanese are both widely spoken languages with lots of example text available.  There's a reason why code talkers tended to use aboriginal languages.

Fourth reason: Kerckhoffs' principle.  Your cryptographic system should not rely on the secrecy of simple tricks like what you propose.


Collision resistant functions - definition Let $f$ be a collision resistant function i.e. it is computationally impossible to find $x_0, x_1$ such that $f(x_0) = f(x_1)$. If a computationally bounded adversary demonstrates that he knows some $x_0$ and $f(x_0)$, in what sense is he unable to determine $x_1$?

My instinct is that he can do no better than choosing a random guess from the domain of $f$ but is this how collision resistance is defined? Moreover, if $f$ has a trapdoor, is the definition still the same i.e. collision resistance implies that either the adversary knows the trapdoor or he can do no better than pick a random element from the domain of $f$?

I apologize that this is a bit of a yes/no question although if the answer is no, then there is more to say!

EDIT: Alternatively, what is the mathematical statement that captures the idea that there is no efficient algorithm to find a collision?

Let the range $Y$ of the function $f$ have size $N$ A collision resistant function cannot be better than an ideal function which maps uniformly into $Y$ since collision probability is minimized by the uniform distribution. Thus, given $(x_0,f(x_0))$ the number $k$ of random points $x_i\neq x_0$ that must be tried before the probability that $f(x_i)=f(x_0)$ is significant, say at least $1/2$ is $k\approx \sqrt{\ln 2 N}$ by the birthday paradox.

If necessary see @fgrieu's detailed post on the mathematics of the birthday paradox here.


Range proof without knowing randomness Party A has a ciphertext $c = (g^r, g^2 h^r)$, which is an encryption of the integer 2 under A's public key, $h$. The encryption scheme used is the additively homomorphic variant of El Gamal. This ciphertext has been homomorphically modified by other parties, so A does not know the randomness $r$.

Is there a way for A to prove that $c$ is an encryption of a non-negative integer? All of the range proof schemes I have found seem to use commitments, which require A to know the randomness in the ciphertext.

First (just to be sure): $(g^r, g^2h^r)$ is not an encryption of $2$ but of $g^2$ (because decryption in general will only give you $g^2$, then you are left solving the DLOG.
I'll assume this is not a problem in your scheme (e.g,. there are only polynomially many valid values that may ever be encrypted).

Second: it is unclear what you mean by "non-negative integer". All exponents of $g$ can be interpreted as a non-negative integers. So what would ne negative integer be? I'll assume you have some range of numbers inside $\mathbb{Z}_{|\mathbb{G}|}$ that you interpret as "non-negative". I won't mess with your desired range proof, just give you an idea for the ElGamal part.

I'll call the integer you want to range-proof $z$ and your ciphertext $(x,y) := (g^r, g^zh^r)$ (in your example, $z = 2$).
You commit to $z$ with whatever commitment your range proof needs. Send the commitment and the ciphertext to the verifier.
Then you should prove (e.g., with a Schnorr-like protocol, see Construction 2.5 here) that there exists a secret key $a$ (the ElGamal secret key) and that you know $z$ such that:

$h = g^a$ (i.e. $a$ is indeed the ElGamal key)
$(x^{-1})^a\cdot y = g^z$ (the ciphertext decrypts to $z$)
that your commitment opens to $z$.

Then, using the commitment to $z$, you run your range proof.

Another route may be to omit the extra commitment and just integrate the range proof into the same Sigma protocol, where $z$ is already a part of. My guess is that the range proofs you found only require you to commit to the value so that the statement is nontrivial ("I know some integer in this range" is not a particularly interesting statement by itself), but can probably be used in conjunction with other statements in the same protocol without an extra commitment (effectively, the ElGamal ciphertext would be your commitment to $z$).


Using what we already know about the data to decrypt it? Are there any methods or tools out there that let us use what we know about the data in order to crack the encryption?

For example let's say I get access to an encrypted database file but I know everything about it... Let's say I know it's a RDBMS, the table & field names, and the primary keys/foreign keys. Since I know the field names I also know what will be stored as boolean, string, numeric, date/time, etc.

Would this or any other information about the data help with decryption? (Maybe the character encoding)

I'm not talking about cracking a password that "decrypts" the file for us (like public/private key), I am wondering about decrypting the actual data.

I'm not very educated on encryption or ciphers, but I can't seem to find any information about introducing the human element into decryption. Sure it may take more time than the universe has existed to break AES encryption using a billion gpgpus processing in parallel, but this is only brute force -- shouldn't we be able to narrow down the the possibilities based on whether the output makes sense?

Just so I could play around with this idea, is there any software that will output the results of the keys that are tried?

I guess a better question with more scope would be, "Is there any way to narrow down our possibilities?"

I recommend you will read a bit about chosen-plaintext attack.
If the scheme you are using is CPA-Secure then even when an adversary is choosing two different plaintexts, giving them to the challenger and then the challenger picks one of them, encrypts it and sends it back to the adversary - the adversary won't have an efficient algorithm to find out which one was encrypted.

AES-CBC with random IV is assumed to be CPA-Secure if my memory don't betray me. So, If you are using the encryption right, the knowledge of the structure of the plaintext should not help you.


Using SHA3 as an entropy pool Has any work been done on analyzing the SHA3 sponge construction for use as an entropy pool (e.g. /dev/random)?

All the use cases I've heard of consts of a sequence of input operations followed by a sequence of output operations where as an entropy pool would require security to be maintained for any sequence of intermingled input and output operations.

As Paŭlo Ebermann already mentioned in his comments, SHA3 can indeed be used as a pseudo-random number generator.

The paper "Sponge-based pseudo-random number generators" talks about just that and it also describes a clean and efficient way to construct a re-seedable PRNG with a (Keccak) sponge function. What you'll get is a PRNG based on a cryptographic hash function… with the usual security implications.

For example: the paper explicitly states that you should reseed regularly with sufficient entropy to prevent an attacker from going backwards on the period of the PRNG (which is probably what you've been hearing about).

Related to proof of security of such a sponge-based PRNG construction, the paper states that the presented PRNG has the property of indifferentiability (which practically claims it is indifferent to an ideal PRNG), a resistance against state recovery (which is a result of it's indifferentiability), and that it passed the statistical tests proposed by NIST. This is the result of the fact that the sponge-based PRNG construction inherits the provable security properties of the sponge construction itself.

I would like to advise you to check on the paper yourself to grasp all the details; like learning how and when to re-seed the PRNG to prevent some potential attacks. It answers your question with ample detail.


Can a secret message be securely transmitted within a MAC tag? A sender wants to transmit an ultra secret code $M$ which could be either 'go', 'stop' or 'wait'. This could be any selection of code words really and adopted for any use such as transmitting short commands or short status messages. The code list could also be specific or relevant to a current mission/objective. A limited number of code words will make things a lot faster for the recipient however. I will try explain:

Both sender and recipient know the valid code list $L$ and share a random 256 bit key $K$ beforehand. This exchange is out of scope.
Let $H$ be a secure hash function with an output of 256 bits which also claims to be a secure MAC in the format of $H$($K$ | $M$). Skein and possibly a few others fit this criteria.
Sender generates a random 256 bit nonce $N$ per transmission.
Sender generates a MAC tag $T$ by calculating $H$($K$ | $N$ | $M$);
Sender sends $N$ | $T$ in the clear to the recipient.

The recipient tries each message in the code list with the nonce and key to try get a match with the sent MAC tag and thus decipher the message:

function(K, L, N, T) {
   foreach M in L {
      if (T equals H(K | N | M)) {
         return M
      }
   }
   return invalid
}

You will note there is no separate MAC tag sent to authenticate the nonce and MAC tag sent in the clear. Because there are only 3 valid codes, there are only 3 possible MACs considered valid by the recipient. This increases the attacker's chance of a creating a forgery to 2^256 / 3 = 2^254 but this is still comfortably secure. You could in fact have 1000 code words and the security would still be adequate at 2^246. However shorter code lists would be better to prevent a DOS type attack when an attacker sends fake transmissions causing excess MAC validation work for the receiver. For longer code lists, perhaps a separate MAC of the $N$ and $T$ would fix that.

From what I can ascertain, only the recipient should know the true message. An attacker can if they do a brute force of the key space (2^256 difficulty) or break the hash function. There is practically no chance of the receiver interpreting the transmitted code incorrectly because the odds of a valid code word producing the same MAC tag is extremely unlikely due to the collision resistance of the hash function.

Can a secret message be securely transmitted, authenticated and read like this?

There are two parts to this proposal: the use of a code book and a scheme to send short confidential and authenticated messages utilising an existing shared symmetric key.

A code book can be used alone to provide a degree of confidentiality, or can be used to ascribe specific pre-agreed meanings to short messages, in combination with any scheme for sending those short messages. The rest of this answer focuses on the use of a MAC for sending such short messages.

Short answer: yes, this scheme preserves confidentiality and integrity of messages.

Pre-image resistance of the secure hash function ensures confidentiality of the message (in conjunction with an appropriately strong key).

The use of a nonce ensures that an eavesdropper can't tell whether a genuine message is the same as any previous messages.

The properties of a MAC prevent forgeries or manipulated messages being accepted.

Note that this system does not protect against replay attacks or message re-ordering attacks, i.e. it can't be used as a generic secure channel. Once an attacker has observed a message, they can replay the message and the recipient cannot differentiate between a replayed message and a fresh message. If the recipient were to record all valid nonce-message pairs they could detect replays, but not out-of-order messages.

This use of a MAC isn't a standard way to build a secure messaging system, so shouldn't be used for production systems. Practically, it has very large message expansion (256 bit ciphertext + 256 bit nonce per ~10 bit data transferred = ~500bit overhead per 10 bit message). An example of a standardised alternative is GCM, which is more size-efficient (96bit nonce + up to 128bit tag = up to 224bit fixed overhead per any length of message) as well as supporting very long messages.


Help me understand how to do a crypto assignment about AES/CBC I'm doing the Coursera cryptography I course from Dan Boneh. I am attempting to do week 2's programming assignment, but I think I am having some sort of misunderstanding of either the theory, the actual implementation, or both. I am neither a crypto or python expert so I'm sure I'm messing up both.
Essentially, I am trying to decrypt some ciphertext given the key. Sounds simple. We are given:
In this project you will implement two encryption/decryption systems, one using AES in CBC mode and another using AES in counter mode (CTR).  In both cases the 16-byte encryption IV is chosen at random and is prepended to the ciphertext. (I'm just doing CBC first)
CBC key: 140b41b22a29beb4061bda66b6747e14
CBC Ciphertext: 4ca00ff4c898d61e1edbf1800618fb2828a226d160dad07883d04e008a7897ee2e4b7465d5290d0c0e6c6822236e1daafb94ffe0c5da05d9476be028ad7c1d81
We're also told: the 16-byte encryption IV is chosen at random and is prepended to the ciphertext.
So I'll go through an example of what I did for the first two blocks. The IV is 16 bit and pre-pended, so it's the first 16 characters of the ciphertext:
IV  = 4ca00ff4c898d61e
Next, I tried to decrypt the next block, which is positions 16-31 (0 indexed) of the cipher text:
c[0] = 1edbf1800618fb28
I believe how this should work is the plaintext for m[0] should be:
$$ m[0] = (c[0] \oplus k) \oplus IV $$
Actually, what my lecture slide says is:
$$ m[0] = D(k, c[0]) \oplus IV $$
And then for the following blocks, just increment the indices by 1: $$ m[i] = D(k, c[i]) \oplus c[i-1] $$
But I'm not 100% sure what "D" actually is (yes, decrypt... but is it xoring? Something else?). When I calculated each one in turns, I just got gibberish. If my understanding is correct (the decryption of the current layer being just xoring c[i] with the key), then it could be an implementation problem?
I'm also a bit unsure about xoring the key with the blocks. I know that IV is supposed to be the same length as the blocks (16) but the key is 32 bits. Do I pad or repeat the blocks so they are 32 bits? Do I use the first 16 bits of the key? etc. I have been using this function given by the prof in a previous assignment:
def strxor(a, b):     # xor two strings of different lengths
    if len(a) > len(b):
       return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
    else:
       return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])

But I don't know if that's still the right way to do it. I know I need to string.decode('hex') before I feed things into the above function and then string.encode('hex') them back into hex afterwards.

For the CBC mode the encryption and decryption equations are as follows;

CBC encryption;

\begin{align}
C_1 &= E_k(P_1 \oplus IV)\\
C_i &= E_k(P_i \oplus C_{i-1}),\;\; 1 < i < nb,
\end{align}

CBC decryption;

\begin{align}
P_1 =& D_k(C_1) \oplus IV\\
P_i =& D_k(C_i) \oplus C_{i-1},\;\; 1 < i < nb,
\end{align}

But I'm not 100% sure what "D" actually is (yes, decrypt... but is it xoring? Something else?).

The $D$ is for Encryption and $E$ is for encryption, and $nb$ is the number of blocks.

If my understanding is correct (the decryption of the current layer being just xoring c[i] with the key), then it could be an implementation problem?

The key is given to AES to produce the encryption and decryptions, we don't x-or with the key, that is OTP or Vigenere.

I'm also a bit unsure about xoring the key with the blocks. I know that IV is supposed to be the same length as the blocks (16) but the key is 32 bits. Do I pad or repeat the blocks so they are 32 bits? Do I use the first 16 bits of the key?

AES has 128-bit block size regardless of the key sized those are 128,192, and 256. Therefore AES can support 128 bit IV/nonces. 128 is 16-bytes and 256 is 32-bytes.
A message to be encrypted with CBC mode needs proper padding like PKCS#7 padding and the padding is performed on the last block. The padding is the missing bytes are filled with the count of the missing bytes, if the last block is full then a new block is needed that is filled with 10. And remember CBC mode is applicable to the padding oracle attack due to improper uses of the padding error and lack of encrypt-then-mac.
The key size must be given to you, and the key size cannot be detected except in the side-channel attacks where if one can see that encryption is 40% slower than AES-128 then it must be AES-128.


Components of Cryptanalysis What are different components of Cryptanalysis. I can't seem to find them. Are they the same as Cryptosystem or is there any difference.

Disclaimer: this answer is opinion based.

TL;DR: The question does not really make sense. Because you cannot put things into boxes like that.

The best way to make you understand it is to make an analogy. Cryptosystem is to Chess what Cryptanalysis is to Chess Games Strategy/Reviewing.

As you define a Cryptosystem with the following components:

Plaintext
Encryption Algorithm
Ciphertext
Decryption Algorithm
Encryption Key
Decryption Key

You can define Chess with:

a 8x8 board
16 white pieces (King, Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 pawns)
16 black pieces idem.
a set of rules

And you can see the review and strategy as:

Openings moves and tactics (Alekhine's Defence, Caro-Kann Defence, King's Gambit...),
Midgames moves and tactics,
Endgames  and tactics,
Mat in 3 (and more),
pinning,
forks,
discovered attacks
etc.

Cryptanalysis will be the art to look at a cryptosystem, find it's weaknesses and how to improve it:

differential/linear/integral Cryptanalysis,
boomerang attacks, related key attacks, impossible differentials,
birthday bounds,
Meat-in-the-middle attack,
Game-based proofs,
Shor's/Simon's/Grover's algorithm
etc


Weak and strong uniformity of cryptographic hash functions For any $n\in\mathbb{N}$, let $\{0,1\}^n$ denote the set of $\{0,1\}$-strings of length $n$. For $n\in\mathbb{N}$ let $$\{0,1\}^* = \bigcup_{k\in\mathbb{N}}\{0,1\}^k \text{ and } \{0,1\}^{\leq n} = \bigcup_{k\leq n}\{0,1\}^k.$$
Note that $|\{0,1\}^{\leq n}| = 2^{n+1} -1$.
Cryptographic functions $h$ map $\{0,1\}^*$ to $\{0,1\}^n$ for some fixed $n\in\mathbb{N}$. Note that in general, for a cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ it is not known whether $\text{im}(h) = \{0,1\}^n$ where $\text{im}(h) = \{h(x): x\in\{0,1\}^*\}$ is the image of $h$.

A cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ is said to be weakly uniform if for every hash value there are infinitely many collisions, i.e. $h^{-1}(\{h(x)\})$ is infinite for every $x\in\{0,1\}^*$. (The pidgeonhole principle only implies the existence of one $x\in\{0,1\}^*$ such that $h^{-1}(\{h(x)\})$ is infinite.)

A cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ is said to be strongly uniform if the number of pre-images for each possible hash value approaches $1/|\text{im(h)}|$ as the input length grows longer, or, formally, if for every $x\in \{0,1\}^*$ we have: $$\lim \sup_{n\to\infty} \frac{|h^{-1}(\{h(x)\})\cap \{0,1\}^{\leq n}|}{2^{n+1}-1} =\frac{1}{|\text{im}(h)|}.$$

Question. Of all the hash functions known to be cryptographically secure, is there one of which we know whether it is weakly, or even strongly, uniform?

For the usual suspects (MD family, SHA family etc.) none are known to be weakly uniform (to be picky, they also aren't known to be cryptographically secure). To demonstrate uniformity in a constructive way would give a collision attack; to do it in a non-constructive way would be an existence proof that would generally use some sort of mathematical structure and the functions are not really designed in that way.
If we look at more mathematically structured hash functions which use ideas from public key cryptography such as the Chaum-van Heijst-Pfitzmann Hash Function (see section 7.4 of Stinson Cryptography: Theory and Practice), we can reduce the output modulo $2^n$ and have weak uniformity by the surjectivity of powers of primitive roots. Moreover, if $p-1$ is divisible by $2^n$ then we will have strong uniformity.
Note that the cost of collision finding in Chaim-van Heijst-Pfitzmann is the same as the cost of solving a discrete logarithm which is below the birthday bound and so larger parameters are required for collision resistance.


What's wrong with MARS? Why did the MARS cipher receive such a high number of negative votes in the AES competition? As I understand only MARS and Serpent implement measures to counter future cryptoanalytic attacks, so it would seem that it is one of the most secure ciphers in the competition. Am I missing something?

People found MARS to be clunky and overly complex, leading to more effort for implementation and optimization, and also a less clear overall security picture.

Assessments of "security" are, in fact, extremely subjective, because they rely on speculations about unknown future cryptanalytic attack, empiric traditions (e.g. "more rounds" = "more security"), and wishful thinking. If we want to remain objective, then out of the 15 AES candidates, 13 were "as secure as one can get" and there is relatively little more that can be said on the subject. The rest is a matter of implementation (for performance and for resistance to side-channel leaks), and the word of the implementers about MARS was, mostly, "please don't".


Double-CBC as AES-KW Substitute? Background.

I'm trying to make a local command-line based password manager. So far, I've managed to make the output look dizzy on tty, and I plan to encode user credentials in individual 512-byte blocks.

To encrypt these blocks, I thought about using XTS, but the overhead of "tweaks" just makes it less favorable compared to the key wrapping modes in NIST.SP.800-38F.

But the key-wrapping in NIST.SP.800-38F involves splitting blocks in halves into "semi-blocks", which is a bit off-putting, and implementing it in full would mean the complication of various working variables.

So instead I made an ad-hoc design.

 The Double-CBC.

In 2CBC mode, the plaintext goes through two rounds of encryption.

In the first round, AES-CBC is applied to the data with an all-zero IV, and because the chaining of cipher output, we can be sure that the result of the last block depends on all previous blocks.

In the second round, AES-CBC is applied again, but this time, with the last block from first round as IV, and because IV is the output of a cipher, we can be sure that it's suitably random, and because it's the output of chain of cipher, we can be sure it'd depend on all parts of the input.

I feel it'd be easier to implement 2CBC than AES-KW.

 On Integrity and Semantic Security.

Because the block is large enough for the type of data it holds, it is possible to have dedicated area in the content of the 512-byte block for randomization vector and integrity check value.

Specifically, the last 128 bits will have 1.) a 96-bit randomization value, 2.) a CRC32 checksum of all previous 508 bytes.

 However, I do not see a reason why message authentication is needed, as it's data at rest mostly.

However, I'm not sure if this is sufficient for the use case here. Specifically, what kind of adversary do I need to prevent tempering of the records from, and how.

 The Questions.

Are my arguments enough to claim that 2CBC is secure for just confidentiality? Or I've made a terrible mistake and missed something important?
If I want to add integrity, can I do it the same way as extending KW from W?
Does the randomization value have to be unpredictable? Can I have meaningful information such as modification time on it? (Probably not, since if attacker checks mod time of the file, he/she will know there's some known plaintext in the file).
How should the need for authenticating the records be satisfied?

Let's assume that the final design of record structure can be altered for security and various other reasons.

CBC mode requires a uniformly random and unique IV for each invocation with the same key. The IV for the 2nd round is satisfied with this property with the reasons mentioned in the question.

This is basically a deterministic pesudo-random permutation on a large block, and semantic-security could (and should) be added by adding randomization inside the block.
Since this question's been slashed, let's separate the concerns here.
Modern ciphers such as AES are currently not known to be suspectible to KPA. Since every bit of the 2CBC ciphertext is the output from AES encryption function, such concern could be said neglegible.
As said before, seperation of concern.

First we should redesign the record structure, we can have 128 bytes for the site of login, 128 bytes for username, 128 bytes for password, 64 bytes for randomization. (When strings are nul-terminated, the rest of the empty area as said in the question could also be used for randomization)

These are the contents to be encrypted using 2CBC. Next we use a separate key (assuming we have a KDF for deriving encryption and authentication keys) to HMAC-SHA512 the encrypted data and append a 64-byte MAC to the end to form a full 512-byte record.

Also remember, if you're not sure there's the need for message authentication, just have it before you find yourself having to break backword compatibility, gain should always be greater than pain.


Learning elliptic curve cryptography for specific application I would like to develop a protocol for specific purpose. This protocol will utilize asymmetric cryptography in which one private key can be paired with numerous public keys: messages encrypted with any of those public keys can be decrypted by that one private key.

That seems to be feasible with elliptic cryptography as per this question and answer.

The obstacle is that, although I am a software engineer, I currently cannot just implement that solution because I do not thoroughly understand it. I do have a basic idea of how asymmetric cryptography works in say SSH and HTTPS. But, in the linked question, all those formulas, equations, expressions and the specific use of verbs "define", "broadcast" etc. make very little sense to me.

Assuming no issues with self-education and tenacity, what would be the quickest pathway to learn the knowledge I need? How to avoid studying branches of cryptography not necessary for what I want to implement? Which resources should I start digging through?

Consider this an oversimplified, though hopefully useful outline of the path to take.

Proficiency in calculations modulo n is a must. That includes results such as Lagrange's theorem, exponentiation, the Extended Euclidean algorithm, and quadratic residues (most likely I am missing some important items here). The essential concepts from group theory are largely embedded in this stage.

Besides its usefulness elsewhere (or I should say everywhere in asymmetric cryptography), a knowledge of the aforementioned items will put you at the right place for understanding the Discrete Logarithm Problem (DLP). The DLP epitomizes the impracticality of searching for, or computing, the discrete logarithm. This is important to understand because the safety of elliptic curves (EC) is premised on that computational impracticality.

A concise, introductory definition of elliptic curves is here. My first exposure to EC was pages 60-64 of Mastering Bitcoin, by Andreas M. Antonopoulos, but there is plenty of alternative resources that cover everything I've mentioned hitherto.

Upon learning about the DLP, textbooks cover El Gamal cryptosystem. Understanding this topic is relevant to EC because of the analogies between the idea behind El Gamal and the digital signing of messages (for instance, as used in Bitcoin).

Hash functions, AES, and key exchange protocols are further topics that oftentimes are combined with --or on top of-- EC but without being part of EC itself.

Note that nowhere have I mentioned RSA, factorization algorithms/heuristics, or the Pohlig-Hellman algorithm, since I am mindful that you are interested only in the requisites for dealing with EC.

To make this answer more self-contained, I will repeat my comment that other concepts you read in the answer to which you linked are similar to any context from telecommunications. For instance, the notion of broadcasting refers to divulging certain information --such as your address or public key-- that will let any counterparty know where to send you a message that only you can read/decrypt (by means of your private key). Boradcasting means no other thing in cryptography.


What are the risks of using CTR mode with 64 bit blocks? On DJB's blog he writes:

  I was one of about 40 people sitting in a meeting where the speaker, NSA's Louis Wingers (one of the Simon and Speck authors), falsely claimed that counter mode is safe for 64-bit blocks, since counter mode doesn't have block collisions. NSA's continuing promotion of these dangerous ciphers includes perfect sentences to quote in the introductions of "provable security" papers studying small block sizes.

I can think of the following problems with 64 bit CTR mode (either used with HMAC or without the need for message authentication)

The keystream can be distinguished from random if the length is close to (or greater than) $2^{32}$ blocks. No two blocks will have equal values assuming no counter overflow. The birthday effect means repeat block values are expected after around this many blocks.
There is a potential plaintext information leak. For ciphertext $C$ and plaintext $P$ (for any length), only if  $P_i \neq P_j$ may $C_i = C_j$ where $i \neq j$. This is true for CTR mode with any block size but is more of a problem for 64 bit blocks than for 128 bit blocks because the birthday limit for 64 bit blocks is smaller.
Random IV collisions are too common because the maximum length of the IV is less than 64 bits.

Are there other problems for CTR mode associated with 64 bit block sizes? (Perhaps associated with different message authentication algorithms.) If not, then what is Bernstein referring to? The problems I identified seem like they would be minor if keys can be regenerated to avoid encryption of too many blocks with the same key.

I hope my list is not exhaustive just so I don't need to post an answer to my own question. Besides mathematical problems I suspect there are a lot of human problems. Those alone I think are serious enough to justify completely discouraging 64 bit block sizes. Plus I believe the IV problem is especially serious.

I believe that he was referring to the misconception that the birthday problem that arises in encryption is only when you use the same counter twice. If a random IV is used, then such a counter repeats at $2^{32}$ blocks with high probability (and if you want a $2^{-32}$ safety margin then you can only encrypt $2^{16}$ blocks). However, if distinct counters are guaranteed to be used, then you never get a collision on the input to the block cipher and so you can encrypt more. I assume that the NSA claim was with reference to this version of counter mode where distinct counters are guaranteed (something that's easy to do if you have state).

Anyway, this is a misconception for the exact reason that you point out. The problem is that people think that this leaks only a very little bit of information, unlike in CBC mode where a collision in the ciphertext immediately reveals the XOR of two plaintext blocks. Recently, at EUROCRYPT 2018, a paper was presented showing how to obtain actual plaintext in a number of realistic scenarios when counter mode is used beyond the birthday bound, even with unique counters. The paper is called The Missing Difference Problem, and its Applications to Counter Mode Encryption. I recommend reading it.


What is the best way to send two floating point numbers to a server on the internet from a small device such as an arduino? I was thinking about sending some sensitive data (temperature) from an arduino (AVR 8-bit processor) to a server on the internet.

But I would like to make sure that it would not be possible for Eve to find the temperature.

I understand that the only way to solve this is to share a secret between the arduino and the server that Eve doesn't know. But where is the line between security by obscurity and a compile-time constant shared by server and arduino?
(I ruled out asymmetric encryption due to performance & (expected) implementation problems).

So assuming they can encrypt the data with a secret key, I still have a sort of known-plaintext problem since Eve knows (from reading the source) that I'm sending 2 floats in a predictable range (-20C..50C). The only solution I could think about is interleaving the 2 floats in an array of random floats and an initial (random) byte to signal the kind of interleaving used. While this sounds to add security, I wonder if it actually does.

So perhaps to recap: what would be the best scenario for sending two temperature measurements to a server on the internet?

ps. at the moment I'm not worrying about authentification but if needed I could add a H/CMAC?

You have to define precisely what Eve can and cannot do. For instance, has Eve occasional physical access to the Arduino-based device ? If yes, then she can (at least conceptually) grab the device, "open" it, extract the shared secret, and replace the device with one of here own which does the same job, except that it also sends a copy of the data to another server that Eve controls. Arguably, she could also add her own measuring device along yours, to achieve the same effect. This would be a quite hard security model.

If Eve does not have occasional physical access to the device, then the "shared secret" model is fine. You still want to be careful with the secret; e.g., if you deploy several Arduino-based devices, have each of them use its own secret key, uncorrelated with the secrets in the other devices.

As for the encryption part:

You do want an integrity check, i.e. a Message Authentication Code. Otherwise, Eve could, for instance, intercept messages and replace them with older messages. Eve would not directly learn the data, but that would probably be harmful to your system.
You need either some randomness to each message, or some memory on the device, to avoid problem. Without either, the same pair of temperature values would yield the same encrypted message, and this would be visible to Eve. Actually, if you use only randomness but no memory, Eve could reorder messages at will, which could also be a problem. By "memory" I mean that the device must be able to store a value and change it, and such that the storage resists reboots.

Here is a specific scheme which will ensure security: to encrypt a pair of temperature values, encode them into a 128-bit word containing, in that order: the first temperature (over 24 bits), the second temperature (24 bits), a field containing only zeroes (48 bits), and counter (32 bits). Then encrypt this as one block with AES (the key being the secret shared between the device and the server). This yields a 128-bit value which you can send to the server. The counter must be managed with some care:

The counter must start at 0. For every message, the counter must be incremented. It must not be possible to "reset" the counter to a previous value, even in case of temporary power loss.
The server must verify, upon decryption, that the field containing zeroes indeed contains only zeroes. That's what serves as a MAC.
The server must store the counter value from the last received message from the device. The new message is accepted only if it has a counter value which is greater than the stored counter value. (Potentially, the server could enforce stricter rules, e.g. refusing to increase the counter value by more than 100 as well.)

Under these conditions, the device will be good for four billions of messages or so. Even if it sends one message every second, this will still take 120 years before running out of counter values.

Security comes from the indistinguishability of AES from a random permutation over the space of 128-bit blocks. It would not work with a block cipher with smaller blocks, e.g. DES (or TripleDES). Also, the "zero-field" which serves as a MAC must not be too short; Eve could send messages with random junk, and a 48-bit field means that the risks of seeing one such message accepted by the server as genuine are around $2^{-48}$ -- since each message has length 16 bytes, it would take on average $2^{52}$ bytes (4000 terabytes) for Eve to succeed. 4000 terabytes, that's huge, but not impossibly huge. If you shorten this field to, say, 30 bytes, then these become 16 gigabytes, and that's highly doable.


Can I make a PRNG that is secure even when state can be modified by user? I am interested in making a PRNG which, after being initially seeded, can accept and incorporate client data as the only ongoing source of "entropy".  It is not directly for a cryptographic purpose, but I wish to get a sense of how much the resulting system might compromise the integrity of the generator.

A simplified design based on SHA1, might be:

Internal state is 160 bits, initially set from a source of good entropy (assume this source cannot be attacked), and hidden from all client systems.
Generator is a SHA1 of the internal state - let's call it
Foo.rand():

a. The return value sent to client is 80 bits, A xor B, where A is
first 80 bits and B second 80 bits of the original digest.

b. The internal state changed by xor-ing it with the original 160-bit
digest.
The client system can at any time send a 160-bit string and it will be xor-ed with the current internal state. Let's call this Foo.alter_state( data ). In reality there might be some transformations, and access to the whole state at once is not likely either. But I think this captures the essence of what I am doing in a worst-case scenario.

figlesquidge helpfully commented more formal notation for the above:
\begin{align}    \mathbf{Init}_s(k):& s\leftarrow k            &\text{where secret key $k$ has full ($2n$-bit) entropy} \\ \mathbf{Update}_s(v):& s \leftarrow s\oplus v            &\text{Add to digest state} \\ \mathbf{Read}_s:& h \leftarrow H(s)            &\text{for some secure hash function $H$} \\ & \mathrm{Update}_s(h) \\ & d \leftarrow \mathrm{MSB}_n(h) \oplus \mathrm{LSB}_n(h) \\ & \mathrm{Return} \ d \end{align}

The end user might turn "attacker" (in essence they have agreed to use the PRNG as a source of randomness, but have a vested interest in controlling the values output by Foo.rand()). Such an attacker has full knowledge of the above, and can call Foo.rand() and Foo.alter_state( data ) completely freely, but cannot peek at the internal state directly. Is there any way that they could discover the internal state via these methods more efficiently than brute-forcing the initial or current value?

If there is an attack better than brute-forcing the state, is it predictably constrained (e.g. it is equivalent to brute-forcing something with half or quarter the number of state bits,so I could increase the size of initial state and maintain an attitude of "not as secure as a cryptographic PRNG with the same size of internal state, but still not hackable for practical purposes")?

I tried to think through some attacks on this system, but am not anywhere near experienced enough to judge whether I have missed something obvious.

I think one key aspect of the system is folding the digest in step 2a - it ensures that an attacker cannot use Foo.alter_state( data ) to repeatedly set the state back to an unknown but identical original, and probe the effects of changing each bit. But is it enough? Does this still leak too much state?

The choice of SHA1 is for simplicity, and any cryptographic hash would do (in theory). I could also consider an HMAC variant if that helped in any way. E.g. instead of simply folding the digest in step 2a, the return value was the HMAC of the original digest, and the secret for the HMAC would be set using a good entropy source, kept hidden and not altered. I feel this would probably mean even if the initial system was easily compromised, the worst-case scenario
would resolve to brute-forcing the secret. However, I'd like to know that I was doing this for a reason, and not just cryptalchemy.

This is not secure.  There is a distinguishing attack that involves about $2^{41}$ invocations of the interface.

Define $f(x) = \text{MSB}_{80}(x) \oplus \text{LSB}_{80}(x)$.  Consider applying the following operation, which I'll call "Leap":

Call Read.  Call the result $d$.
Call Update $(0 \, || \, d)$ (i.e., call Update passing the 160-bit value obtained by concatenating 80 zero bits followed by $d$).

Notice that if $s$ is the state before a Leap operation and $s'$ is the state afterwards, then $f(s)=f(s')$.

The attack will involve applying the Leap operation about $2^{40}$ times.  If you examine the internal state $s_i$ after the $i$th Leap operation, it will satisfy $f(s_i)=c$, where $c$ is some constant that is the same for all of them (in fact, $c=f(k)$, where $k$ is the initial state).

Thus, each $s_i$ comes from a space of $2^{80}$ possibilities, and each $s_i$ is basically a random element from that space.  Now by the birthday paradox, once you have $2^{40}$ randomly chosen elements from a universe of size $2^{80}$, there is a pretty good chance that some pair of those elements will be the same.  This means we expect to find some indices $i,j$ such that $s_i=s_j$, i.e., where the state after the $i$th Leap operation is the same as the state after the $j$th Leap operation.

But of course the behavior of the PRNG is a deterministic function of the state.  Therefore, the behavior of the PRNG at time $i+t$ will be the same as the behavior at time $j+t$.  In particular, the sequence of outputs at times $j,j+1,j+2,\dots$ will be a repeat of the sequence of outputs at times $i,i+1,i+2,\dots$.

In other words, if you perform a bunch of Leap operations, the PRNG will enter a cycle and start repeating after about $2^{40}$ steps.  This is too fast.  It's something that a true-random generator would not exhibit.  It allows to distinguish the output of the PRNG from truly random, and to predict future outputs (assuming we continue to apply Leap operations).

By academic standards, this would count as a break of the PRNG, since $2^{40}$ operations is feasible.  By practical standards, it might not be an enormous risk, because it requires that the adversary has a way to alternate Read and Update operations and that the adversary has total control over all of the Update operations -- but it's still a break, by the standards that cryptographers use.

A possible fix would be to change your Update operation to

$$s \gets H(s,v).$$


Would using two keys for Salsa20 or ChaCha increase security? Would using the keys (as in two passes with a key each) increase security for Salsa20 or ChaCha stream ciphers increase security?

Would using the keys (as in two passes with a key each) increase
  security for Salsa20 or ChaCha stream ciphers increase security?

More or less.
It wouldn't increase the difficulty of brute-force by a lot (one bit to be precise) due to the infamous meat-in-the-middle-attack if you would use the same keylength, if you used different ones the effective keylength would be the higher of the two lengths.

What it would do though, is to increase the cryptanalytic security of the construction. Ie an attacker would have to successfully break both ciphers with cryptanalysis which is indeed more unlikely than him breaking one.

Is it worth it? No. The extra keybit is not that valueable and it's already a matter of "meh, can't break" anyways even with a single cipher. Regarding the cryptanalytic defense, neither ChaCha nor Salsa have been broken, but these ciphers are quite similar so you don't get the advantage you would get from two ciphers with radically different designs.


Can we have Rijndael s-boxes constructed using reducible polynomials? Is it necessary for the Rijnael polynomial to be irreducible? Can we have s-boxes constructed using reducible polynomials? If not what is the mathematical property that is obstructing to do so?

As noted by poncho in the comments to your previous question, the Rijndael S-box is defined based on the multiplicative inverse of the input byte in a particular representation of the finite field $GF(2^8)$, where the representation is defined by the choice of the reduction polynomial.

However, in order to represent a finite field using addition and multiplication of polynomials modulo some reduction polynomial, the reduction polynomial must be irreducible.  If it isn't, the resulting algebraic structure will not be a field, and in particular, not all non-zero elements will have multiplicative inverses.

Of course, you could simply dispense with the finite field inverses entirely, and just construct your S-box in some other way.  As the Rijndael authors note in section 7.2 of the Rijndael AES proposal:

  Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a trapdoor being built into the cipher, the current S-box might be replaced by another one. The cipher structure and number of rounds as defined even allow the use of an S-box that does not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an S-box that is “average” in this respect is likely to provide enough resistance against differential and linear cryptanalysis.


ed25519 adoption -- challenges If ed25519 is that attractive that it seems to be, can someone explain why adoption has been slow and if there are, if any, challenges with implementing ed25519.

Nathan Aw

In general, assumptions that have been around for a long time are considered far preferable to new ones. Although a new curve is not strictly a new assumption, these curves do have special structure and so may contain surprises. This is not to say that they do contain surprises, and indeed they are not vulnerable to any KNOWN attacks (but that is only what is known). Also, note that EdDSA may be less side-channel resistant than expected, as shown in Daniel Genkin's talk at RWC 2018.


ID-based key exchange protocol with PFS The traditional authenticated DH protocol with PFS against active adversaries, ensures that the compromise of both party's long-term private keys after the session is completed will not help the adversary to compute session key, even adversary gets involved in the generation of messages.

An ID-based key-exchange has some differences with the traditional ones, such as it needs a KGC,

and public/private key generation is handled differently compared with the traditional ones.

Compared with the traditional authenticated DH protocol, what's the advantage of ID-based ones?

And if I want to design a ID-based key-exchange protocol with a bilinear pairing especially under eCK model, are there some ways to realise PFS against active adversaries besides using digital signatures?

Where should I pay particular attention?

In an ordinary ID-based scheme, you won't get strong PFS.  The center always knows a secret that can be used to recover your private key and thus can violate PFS.

One approach is a hybrid scheme, such as the following.  You could do a (non-ID-based) Diffie-Hellman or ECDH key exchange, with messages signed and authenticated using an ID-based signature scheme.  You'd use the Diffie-Hellman/ECDH key exchange to derive an ephemeral session key for encrypting the rest of the channel.  That would get you PFS (against passive eavesdroppers), along with the advantages of ID-based cryptography.

Apparently, the following paper describes an even better scheme.

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead.   Rosario Gennaro and Hugo Krawczyk and Tal Rabin.  IACR ePrint 2010/068.

Their paper apparently provides PFS against passive attackers and PFS against active attackers (even if the center is corrupted, apparently).  Thanks to Alex for pointing this out.

The "advantage" of ID-based schemes is that you can use, e.g., someone's email address as their public key.  The disadvantage is that you must trust the center an awful lot, because the center knows or could compute everyone's private keys.  This is standard and you can find a lot written about ID-based key exchange that explains these tradeoffs in detail.


FIPS 140-2 compliance and RSA encryption I remember reading that the RSA algorithm was only permitted for encryption when used to encrypt a symmetric key (essentially leading to hybrid encryption).
However, reading through Annex A: Approved Security Functions for FIPS PUB 140-2 this doesn't seem to be an option.
Did I mis-remember? Are there any approved asymmetric encryption algorithms?

There's a difference between FIPS approved and FIPS allowed algorithms.  RSA is an allowed algorithm for doing key wrap and key transport, however it's not FIPS approved for that purpose.  It's only approved for digital signatures.
If you're using a FIPS validated module take a look at the security policy for the module you're using and see if RSA is allowed or not for key wrap or key transport.  It must be documented there.  If it's not then you can't use it (and claim compliance) even if it's available in the module.
And no, there are no approved generic asymmetric encryption algorithms, they're only approved for digital signatures.


Solving Quadratic equations in Galois Field (2^163) Hello I am working on implementing a message to elliptic curve point mapping hardware circuit
I have done some research and found out the koblitz mapping method:
I will be using a field of binary polynomials F(2^163) the equation will be of the form of :
$$
    y^2 + xy = x^3 + x^2 + 1
$$

The given algorithm consists of checking the Tr "Trace of polynomial" at first and then solving the quadratic equation based on the chosen coordinate "x" that satisfied the needed trace conditions and obtain "y" the second coordinate
I have given to understand that finding the trace of any polynomial C in field 163 is XORing(bit0,bit157) of the given polynomial

But after calculating the Trace and finding the x coordinates I do not understand how to solve the quadratic equation in hardware and how to implement it
I have found some reading material suggesting of calculating the H(C) which is the half trace of the polynomial C
but my questions are:

1.What is trace of a polynomial and how it is calculated? is it by
    xoring all bit together from 0 to m-1 ?

what is half trace ? and    how does it relate to trace? and why is
it used to solving quadratic    equation isn't it a 1 -bit answer
how can I solve the given
       equation to obtain the y coordinate and if there are 2 Y answers
       which one will be chosen?

Thank you I really appreciate the help. I could not find clear reading material on this matter with a simplified and easy to read algorithm/pseudo-code

Added:
I found the following algorithm but I do not know what it's name? and how are the parameters a2n and a2n+1 computed and how they vary for different fields lets say (163)

algorithm for solving the equation taken from:
A Low-Power Design for an Elliptic Curve Digital Signature Chip (Rich Schroeppel, Tim Draelos, Russell Miller, Rita Gonzales, Cheryl Beaver)

I'll try to give additional explanation on algebraic number and the link with EC.

Let $q=2^{163}$ the finite Field $F_q=GF(q)$, as selected by NIST has some features for doing cryptography. This field has been generated with the irreduccible pentanomial you gave in the table.
To understand what the trace of the polynomial is, it corresponds to the coefficient of monom of degré 162, which is Zero in this case. And remembering that any finite field could never be algebraically closed, we can considere all the 163 roots of p, $\{x_0..., x_{162} \}$, which are conjugate each other. The trace of the polynomial is simply the sum of all its roots.
But as they are all conjugate, only one root suffices to calculate the trace by repeating square. (Cf ref books).
Then we see, that we can define the trace of any element in $F_q$ by  $Tr(\alpha)=\sum_{i=0}^{i=162}\alpha^{2^{2^i}}$.
This define a linear map (endomorphism) from $F_q$ to $F_2=\{0,1\}$!

Now the "Trace" map, is useful to help in solving quadratic equation. if $\lambda$ is a solution in $F_q$ of $\lambda^2 + \lambda = b$, then so is $\lambda+1$. This show that the equation is solvable only if $Tr(b)=0$

And the link with EC ? As fkraiem observes it, you have nothing to do! NIST has done all the work by selecting the field of appropriate size, generating polynomial and indicates how to get the trace for any algebraic element in $F_q$. For this case of K-163 (Koblits Curve) or B-163 (random Curve), and a given $\mu \in F_q$, $Tr(\mu)=\mu_{157}+\mu_0$ snipped from the table you show us.

When we want to select randomly a point on a given standardized curve EC: $y^2+xy=x^3+a_2.x^2+a_6$, we begin by chosing the abscisse $x\neq 0$, and then try to compute the corresponding y!
setting $z=\frac{y}{x}$ gives $z^2+z=x+a_2+\frac{a_6}{x^2}$, which allow us to understand why the trace of the second member must be Zero in the algorithm 2 shown above.

The Half Trace, can be explained by the fact that in a finite field there is exactly the same number of quadratic and Non-quadratic residues.

Then the Half trace is defined by $\tau(\alpha)=\sum_{i=0}^{\frac{n-1}{2}}\alpha^{2^{2i}}$(Ref N. Smart Elliptic Curves in Cryptography), which gives the solution of the equation. There are generally 2 solutions, and you can select one to build the point, the other allow to select the opposite point.
And when a solution is chosen, the point is $P=(\alpha, \lambda.\alpha)$, and a straiforward calculation allow to check that it belong to EC!

@user3368764: I'd a look to the paper you indicate. They use a tower factorization of finite field $GF(2^{178})$. As 178=2.89, a first field extention $GF(2^{89})=GF(2)/(u^{89}+u^{38}+1)$, followed by $GF(2^{89})/(v^2+v+1)$ allow to get $GF(2^{178})$. If you plan to design a hardware for $GF(2^{163})$ it can't be used for another field. Arithmetic in Binary is simple, but unfortunaltly not flexible.

Now Let's return to Nigel Smart's book for depicting the solution of $\lambda^2+\lambda+\beta=0\cdots$!  Recall that any finite field of $q=2^{163}$ elements, field'elements are charaterized by $X^q=X$. Then with the definition of Half Trace : $$\tau(\beta)=\sum_{i=0}^{\frac{n-1}{2}}\beta^{2^{2i}}=\beta+\beta^{2^2}+\beta^{2^4}+\cdots+\beta^{2^{n-3}}+\beta^{2^{n-1}}$$
In a binary field, the square is a linear operator, which gives:
$$\tau(\beta)^2=\beta^2+\beta^{2^3}+\beta^{2^5}+\cdots+\beta^{2^{n-2}}+\beta^{2^{n}}$$
As $\beta^{2^{n}}=\beta$, it remains: $\tau(\beta)^2+\tau(\beta)=\beta+Tr(\beta)$ which mean that if $Tr(\beta)=0$; then $\tau(\beta)$ is a solution of the quadratic equation


Identifying negligible functions I am having a hard time understanding and applying the formulas that are used to identify a function is negligible or not?

One text defines it as; a function $f$ from the natural numbers to the non-negative real numbers is negligible if for every positive polynomial $p$ there is an $N$ such that for all integers $n > N$ it holds that $f(n) < 1/p(n)$.
Another textbook defines it as; a function $f$ is negligible if, for every polynomial $p$, we have $\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda)=0$

Example: $1/2^{\lambda/2}$ would this be considered as negligible function?

From the first definition;

To see that a function is negligible, you have to find an $n >N$ for every positive polynomial $p(n)$ such that after $f(n) < 1/p(n)$ is holds. Here two examples;

consider $p(n)= 10^6$ then $n \geq 800$ then $1/2^{800/2} = 1/1048576 < 1/10^{-6}$
consider $p(n)= 10^{3}$ then $n \geq 200$ then $1/2^{200/2} = 1/1024 < 1/10^{-3}$

  From the second definition;
  $\lim_{\lambda \rightarrow \infty} p(\lambda) f(\lambda) =0?$

For your $f(\lambda) = 1/2^{\lambda/2}$ we have to see that the limit is 0 whatever the polynomial $p(\lambda) = a_n \lambda^n +\ldots + a_0$

$$\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda) = \frac{p(\lambda)}{2^{\lambda /2 }} = \lim_{\lambda \rightarrow \infty} \frac{a_n \lambda^n +\ldots + a_0}{2^{\lambda /2 }} = 0,$$

since if you take the L'Hôpital's rule the $n$-times the numerator will be 1 and eventually zero. The denumerator, however, goes to infinity.


Could Riemann hypothesis solve certainly RSA? I don't have the background for dealing with Riemann hypothesis but is well known that covers the prime distribution below a specified number.

In order to solve the RSA problem you have to factor the semiprime or calculate the totient itself, that's hard as factoring the modulus.

Question is, could Riemann hypothesis be used to calculate how many coprimes are below the modulus by counting the primes below $n$ and also counting how many products of those primes are below $n$, except those involving $p$ and $q$?

If the previous is negative, can someone clarify why some people say that Riemann hypothesis could "break" RSA?

Thanks for your patience and comprehension.

It's not that proving the Riemann Hypothesis would itself lead to a breakthrough against RSA.  Rather, it's speculation that the methods leading to the discovery of a proof of the Riemann Hypothesis could lead to a profound discovery about prime numbers that, say, makes factoring easy.

The reason that proving the Riemann Hypothesis in itself has no bearing on RSA's security is that we can simply accept it as true now.  We don't need to wait for a proof to use the Riemann Hypothesis to find holes in RSA.  If we found a way to use the (apparent) fact that all nontrivial zeros of the zeta function have real part $\frac 12$ to crack RSA, and this crack actually worked, then it simply doesn't matter whether the Riemann Hypothesis was proved.


uuidgen has consistent 13th digit and it's 4 I ran uuidgen 10k times and noticed that the 13th digit is always 4.
Why is that?

You can find a full explanation in the Wikipedia article on UUID.

UUID's come in different versions. The 4 you highlighted indicates version 4 was used where the UUID is created by generating a random number. Other versions use for example the date-time and MAC address of your computer.

When you look further at the first character of the next block you will see it is not very random either: it shows only the characters 8, 9, A and B . This is because the two most significant bits are 01 for the variant of this UUID version.


CPA on theoretical OTP with CBC mode Body of question

Note: this is THEORETICAL exercise. I understand OTP and CBC does not get along.

I have to find a CPA on CBC enc-mode using OTP as the encryption algorithm, s.t a new key is generated only for every new message, but not for every block.

Second question is whether this method is not safe at all, or, it could be safe for odd block number, or perhaps for even block number?

What I've tried myself

I can see myself that in even block number case, the key is cancelled out at last (thanks to CBC), so what I get is $IV \oplus P_1 \oplus...\oplus P_n$, but can't think of a way to distinguish two messages with the IND-test for CPA.

Basically I can calculate the blocks of each $m_1,m_2$ that I use for the test, but the randomized IV will prevent me from knowing what message is the ciphered text retrieved from the test...

And what about the odd case?

Any ideas?

Scheme is not IND-CPA for any message longer than one block. I'll include a image of CBC mode below for reference (Source: Wikipedia).

Suppose instead of block cipher encryption we have plaintext xor-ed with the key as you propose. You'll note that for message block 1, $M_1$, the ciphertext block $C_1 = M_1 \oplus IV \oplus Key$. Similarly $C_2 = M_2 \oplus C_1 \oplus Key$ Substituting for $C_1$ we get $C_2 = M_2 \oplus M_1 \oplus IV \oplus Key \oplus Key$ which reduces to $C_2 = M_1 \oplus M_2 \oplus IV$. Knowing this we can build a distinguisher $D$.

Suppose we send two messages $M0$ and $M1$ to the encryption oracle and get back $C$. $D$ will take $C$ and check if either $C_2 = M0_1 \oplus M0_2 \oplus IV$ or $C_2 = M1_1 \oplus M1_2 \oplus IV$ (note that the $IV$ is not secret), returning whichever plaintext corresponds to $C$. Clearly this distinguisher has non-negligible advantage, and thus the scheme is not IND-CPA for messages longer than one block.


Function with no inverse My friend asked once a question which sounds very interesting:

  If a function does not have inverse, does it mean that the message cannot be deciphered ?

What is the answer to this question ? In my opinion it is a definitely yes

A function that doesn't have an inverse still has an inverse image or preimage.  I.e., if we have $f : P \to C$, and we can efficiently compute the set $f^{-1}(c) = \{p \in P\; |\; f(p) = c\}$, then that tells us information about what are the possible plaintexts $p$ for a ciphertext $c$.  It doesn't tell you which one of the alternatives is the "true" one, but in real life you very often have other, independent information about what the plaintext is likely to say.  If you put that independent information together with the preimage of the ciphertext, you may well end up inferring the plaintext.

Or an even dumber attack, you can just enumerate your independently- generated guesses at the content of the plaintext, from more likely to less likely, apply the function to each them, and see if the result matches the ciphertext.  Password cracking works precisely like this—the dictionaries and other tricks of the trade (masks, mutations, etc.) can be understood as hypotheses about which passwords real-world users are likely to pick, and the stolen outputs of the password hashes—which are functions without inverses—are used to test these hypotheses.  It's wildly successful.

So I would not look at it as a yes/no question, but as a quantitative one: how much does the attacker's knowledge of the function and ciphertext help them achieve their goal, relative to whatever independent knowledge they have?


What is the main difference between Anonymous HIBE and Anonymous Predicate Encryption? What is the main difference between Anonymous HIBE and Anonymous Predicate Encryption? In my opinion, both work for the same concept in different ways.

Identity-based encryption (IBE) uses the receiver's identity as a public key. The sender specifies an identity that the receiver with a matching identity already has. An IBE scheme is anonymous if a ciphertext does not reveal the identity of the recipient.
"Hierarchical IBE (HIBE) is a generalization of IBE that mirrors an organizational hierarchy. An identity at level $k$ of the hierarchy tree can issue private keys to its descendant identities, but cannot decrypt messages intended for other identities."[1] (p.1; details are given in Section 2.1) (HIBE) is a scheme "in which an identity is a vector of strings $id= (id_1, \ldots,id_l)$ with the understanding that when $l = 0$ this is the empty vector $()$." See this paper, especially pp. 19 and 20, for the quote and more information. For more about IBE, see Adi Shamir's Identity-based cryptosystems and signature scheme (1984).
Anonymous IBE (A-IBE) aims to hide attributes. It is an early example of public key predicate encryption. Anonymous HIBE offers hierarchical key delegation and fully anonymous ciphertexts.[2] Anonymous HIBE is a form of IBE that does not leak the identity of the sender. D. Bonah et al. have characterized the security of HIBE as IND-ID-CCA and IND-ID-CPA (p.4; paper listed below).
In predicate encryption (PE), secret keys correspond to predicates. The master secret key owner can issue tokens that allow access to specific data. This scheme can be useful in controlling access to classified information--think of keywords associated with classified data. It is also used in biometric matching and secure cloud storage. Predicate encryption generalizes attribute-based encryption (ABE). ABE has to do with access that follows from the data's attributes, and is probably based on an access roster and policy. ABE treats a set of attributes as if it were an identity. Again, PE is useful for precise access control over encrypted data--namely, who gets to see what. Anonymous predicate encryption hides the users' identity; for example, from a server that controls users' access privileges.
The main difference between anonymous HIBE and anonymous PE is that the latter offers granular access control over encrypted data.
[1] D. Boneh, X. Boyen, and E. Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext.   In Advances in Cryptology—EURO-CRYPT 2005.
[2] X. Boyen and B. Waters. Anonymous hierarchical identity-based encryption (with-out random oracles). In Advances in Cryptology — Crypto 2006.


Is encrypting a file with AES-CTR and then encrypting the AES key with RSA-4096 secure? I'm using microsoft visual studio 2019 c++. I have aes-ctr-128 implementation.

Encryption process:

Generate key pair for aes-ctr-128 using CryptGenKey() function
Encrypt whole 16000 bytes array using key\nonce that was generated previously
Encrypt key and nonce with RSA master key
Write encrypted key\nonce in "key.txt" and "nonce.txt"

Decryption process:

Read encrypted key\nonce
Decrypt encrypted key\nonce with RSA master key
Decrypt whole 16000 bytes array using key\nonce that was decrypted from file

The question is: does this algorithm provide secure encryption process?

First of all, CTR mode is an archaic mode of operation that only provides you confidentiality. In modern standards, we use Authenticated Encryption (AE) modes like AES-GCM or ChaCha20-Poly1305. AE provides you confidentiality, Integrity, and authentication in a bundle.

There is no need to encrypt the IV. They are never designed to be encrypted. They provide probabilistic encryption that is very useful if a key is used more than once.

To encrypt with RSA-4096 you need a proper padding scheme like PKCS#1.5 or OAEP. The latter, OAEP, is better since the former has more issues. Once you use proper padding you are fine (not exactly). Note that RSA is totally broken if someone is able to build Shor's algorithm with enough Q-bits.

It is not clear how are you going to keep your RSA-private keys safely. Is it turning into a chicken-egg problem? Another problem is what if someone plays with the key.txt file. Alas, you can no longer access your files! You need backups.

In these kinds of problems, we prefer passwords based key derivation function like PBKDF2 or Argon2id. Have a good password and derive the encryption key with good parameters and from there encrypt with a AES-256-GCM [*]. It actually uses CTR mode inside. You will only get an additional tag this is up to 128-bit storage overhead and this is nothing compared to your file size. The speed lost, see yourself below from the OpenSSL speed tool.

$openssl speed -evp aes-256-ctr
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-ctr     474901.33k  1490379.07k  2337490.52k  3131689.64k  3592602.97k  3086712.83k

$openssl speed -evp aes-128-gcm
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-256-gcm     435559.37k  1178543.34k  2184926.89k  3160146.94k  3705495.55k  3713903.27k

In the end, a Veracrypt may be good for you. Have a good password, generate it with diceware or Bip39 then you will have a good entropy. Use it while creating your volume.

Diceware passphrase has an entropy around

A five-word  has 64.6 bits
six words have 77.5 bits
seven words 90.4 bits
eight words 103 bits
nine words 116 bits
ten words 129 bits.

Bip39 creates $\approx 2^{263}$ with 256 coins tossing and selecting 24 words.

And, don't forget to back up your files.

[*] Since we talked about Shor, we have to consider Grover, too.


Determining the secret using the Blakley's scheme? I am solving a example with Blakley's scheme problem. The issue that I am having is using the row operation to determine the secret $x_{0}$. So what I have so far is:

Given three planes: $z = 7x + 84y + 41$, $z = 17x + 5y + 3$, and $z = 37x + 46y + 66$. Then I set up the matrix:
$$
\begin{equation}
\begin{pmatrix}
    7       & 84 & -1  \\
    17       & 5 & -1  \\
    37   & 46 & -1
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} -41 \\ -3 \\ -66 \end{pmatrix}
(mod \ 87)
\end{equation}
$$
I used the row operations calculator to get the matrix, however it seems way off and incorrect. Am I suppose to do a row operations first and once I do that what do I need to do after to get $x_{0}$,$y_{0}$, and $z_{0}?$
Any help is appreciated.

I don't see any problem with your matrix, it is invertible.

Once you've setup the matrix, you can work out the solution of your system. Just don't forget you are working modulo 87, so:

$$
\begin{aligned}&
\begin{pmatrix}
    7       & 84 & -1  \\
    17       & 5 & -1  \\
    37   & 46 & -1
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} -41 \\ -3 \\ -66 \end{pmatrix}
\pmod{87} \\
\equiv&
\begin{pmatrix}
    7       & 84 & 86  \\
    17       & 5 & 86  \\
    37   & 46 & 86
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} 46 \\ 84 \\ 21\end{pmatrix}
\pmod{87}
\end{aligned}
$$

And for example the inverse of $5 \bmod{87}$ is $35$, so I would multiply $\bmod{87}$ the second row with $35$ to get a $1$ in the second column:
$$\begin{pmatrix}
    7       & 84 & 86  \\
    \color{red}{73}       & \color{red}{1} & \color{red}{52}  \\
    37   & 46 & 86
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} 46 \\ \color{red}{69} \\ 21\end{pmatrix}
\pmod{87}$$

As mentioned, since the matrix has an invertible determinant $\bmod{87}$, the matrix is invertible, so if there is a solution (don't worry, there is one), you can find it using Gaussian Elimination, I think you should try it too, until you obtain in the end a system of the form:
$$
\begin{pmatrix}
    1   & 0 & 0  \\
    0   & 1 & 0  \\
    0   & 0 & 1
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} ?? \\ ?? \\ ??\end{pmatrix}
\pmod{87}
$$

PS: Note that the rank's theorem for a matrix does not exist in a commutative ring.


Cheating in (2,6)-Shamir Sharing Scheme We consider a $(2, 6)$ Shamir secret sharing scheme over $Z_{11}$. Four players $A,B,C,D$ cooperate to find the secret, but one of them is cheating (so the share he claims to have might not be an actual share). They claim that their shares are;

$$A:(1,2)\quad B:(2,5)\quad C:(3,10)\quad D:(4,3)$$
Who is cheating and what is the secret?

I am using 4 equations:

\begin{aligned}
2 &= s + a & (1)\\
5 &= s + 2a &(2)\\
10 &= s + 3a &(3)\\
3 &= s + 4a &(4)
\end{aligned}

And solving for $s$ and $a$.

I don't seem to know the exact approach? How do I go about solving this problem?

You have four equations and two unknowns.  Any two of those equations should therefore be solvable, and all pairs that don't include the cheater should yield the same solution.

(You don't actually need to solve all six possible pairs of equations if you know there's at most one cheater.  It's sufficient to e.g. just solve equations 1 & 2, and check which of 3 & 4 fails to fit the solution.  If both fail, solve 3 & 4 instead, and check which of 1 & 2 fails to fit.)

Also, remember that you will need to solve all those equations in $\mathbb Z_{11}$, i.e. using arithmetic modulo 11.


Prime modulus for RSA and sharing a secret? According to this paper entitled "Using Commutative Encryption to Share a Secret" they define their modulus to be a large prime p, which is public. Both exponents are private in this case.

According to the wikipedia article on RSA link the modulus has to be a product of two primes, and " p, q, and φ(n) must also be kept secret because they can be used to calculate d.", and the exponent can be public.

In the paper both the modulus (p) and φ(p) are known. How is the algorithm in the paper secure? Is it because both keys are private?

Is there a secure way for the same modulus to be used across all parties, and $a_i$ are public for each user?

I think the confusion lies in mixing two distinct hard problems.

RSA is related to the difficulty of factoring large numbers. The scheme you link to in the paper is based on the difficulty of solving discrete logarithms. Since they are very different hard problems, you can't really compare the two in terms of what must be kept secret.

For RSA, $\varphi(n)$ must be kept secret since with that you could factor $n$ (and hence make the hard problem easy). With the scheme you link to, you must keep the exponent secret as that is what you are trying to solve for when computing a discrete logarithm.


How to decrypt this RSA-like cipher Suppose we have a RSA-type Modulus $n = pq$ with $p,q$ prime. We also pick a random public exponent $e$ with $\gcd(e,\varphi(n)) = 1$ and compute the private exponent $d$ with $de \equiv 1 \pmod{\varphi(n)}$. $(n,e)$ is the public key, $(n,d)$ is the private key. Just like RSA, so far.

Now we encrypt a message representative $m$ with $0 \leq m < n$ by applying the following steps:

Choose a random $r$ with $1 \leq r < n$
Compute $y = (r^e)^e \pmod{n}$
Compute $z = (r \cdot m)^e \pmod{n}$
$(y,z)$ is the Ciphertext

How is it possible to decrypt this cipher using just the ciphertext $(y,z)$ and the private key $(n,d)$?

Here's what i have so far for the decryption algorithm:

Compute $r = (y^d)^d$
Compute $rm = z^d$
Find the multiplicative inverse $r^{-1}$ of $r$ modulo $n$
Compute $m = rm \cdot r^{-1}$

The problem with this is, that $r^{-1}$ only exists, when $\gcd(r,n) = 1$ and thus the decryption fails, when this is not the case. Is there a better way to do this?

A slightly more efficient method to perform decryption would be:

Compute $r^e = (y^d)$
Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$
Compute $m = (r^{-e} \cdot z)^d = (r^{-e} \cdot r^e \cdot m^e) ^d$

This has two computations of $x^d$ for some $x$; your method has three.

On the other hand, this doesn't address your question; if $r^{-1}$ doesn't exist, neither will $(r^e)^{-1}$.

For your question, well, there is no such "better" algorithm, because the decryption is inherently ambiguous.

Suppose that $n = pq$ (where $p$ and $q$ are distinct primes), and you selected a value $r = kp$ (for some integer k).  Then, if we consider two distinct messages $m_1$ and $m_2$ with $m_1 = m_2 \mod q$, and the encryption of both these messages with that same $r$.  They share the same $y$ value (because $y$ depends only on $r$), and as for the $z$ value:

$z_1 = (r \cdot m_1)^e \mod n$

$z_2 = (r \cdot m_2)^e \mod n$

we see that:

$(z_1 - z_2) \bmod p = r^e \cdot (m_1^e - m_2^e) \bmod p = 0$  (because $r$ is a multiple of $p$

$(z_1 - z_2) \bmod q = r^e \cdot (m_1^e - m_2^e) \bmod q = r^e \cdot 0 = 0$ (because $m_1^e$ and $m_2^e$ are the same modulo q)

and hence (by the Chinese Remainder Theorem), $z_1 = z_2 \mod n$

So, if you attempt to decrypt the message $(y, z_1)$, there are at least two valid decryptions ($m_1$ and $m_2$), and no algorithm can distinguish which is meant.

If you prefer a concrete example, consider the case where $p=5$ and $q = 11$.  We can select $e = 3$ and $d = 27$ (actually, $d=7$ would work just as well).  Then, if we select $r = 10$ and $m_1 = 2$ and $m_2 = 13$, then the encryption of $m_1$ would be:

$((10^3)^3, (10\cdot2)^3) = (10, 25)$

and the encryption of $m_2$ would be:

$((10^3)^3, (10\cdot13)^3) = (10, 25)$

Hence if we get the ciphertext $(10, 25)$, we can't tell if the original message with 2, 13, or even a bunch of other values (24, 35, 46)

Now, in practice, this is not likely to be a concern; the probability of this happening with a random $r$ is about $1/p + 1/q$; if $p$ and $q$ are large enough to make factorization difficult, this failure probability is negligible.

BTW: why are you considering this method, rather than a more straightforward RSA-based approach?  If it is to get some homomorphic properties, well, it doesn't hide the encryption of 0 very well, and that's really what we would like in a multiplicative homomorphic encryption.


Is it secure to hash an AES key? Let's say I want a way of generating a deterministic public ID for a specific symmetric cryptographic key (AES, for example). Would it be secure to use SHA-3 (or SHAKE) to hash the key, and then distribute the hash as the public ID for the secret key?

Is there an advantage or disadvantage to using a larger or shorter hash length relative to the key length? For example, if the key is 256 bits (32 bytes), using a 256 vs 512 bit SHA3 hash?

Would it be secure to use SHA-3 (or SHAKE) to hash the key, and then distribute the hash as the public ID for the secret key?

Sure; SHA-3 and SHAKE are effective uninvertable.  Now, I suppose someone could try various AES keys and see which hashes to the public identity; on the other hand, they could try various AES keys and see which one decrypts the ciphertext properly. We believe that the second is infeasible, and so the first (which requires no less effort) is also infeasible.

  Is there an advantage or disadvantage to using a larger or shorter hash length relative to the key length?

The only disadvantage to using a shorting hash length is that it increases the probability that two different keys that you actually use will end up with the same public identifier (hash).


Is it possible to extract the decryption key from a locked android device Is it possible to extract the decryption key from a FDE android device while the screen is locked but the phone is powered on.

Is the data only safe when the phone is off ?

Is the data only safe when the phone is off?

This is really hard to properly assess and depends on your definition of "safe" alot. However I'll assume that you mean "is the data protected by the FDE encryption?".

The clear (and obvious) answer to this is no.
You can unlock your phone quickly (without having to wait one or two seconds) so the key for the FDE must be stored in RAM and thus the security level is "lower" than when the device is turned off.

To verify this yourself, observe that you enter your password in the pre-boot authentication and have to wait a moment until your phone can tell you whether the password was correct or not. This is due to the password-based key derivation function being used there which takes a lot of computation power which can be spend right after startup bu not each time the screen is unlocked (where the user wants to access his phone quickly and doesn't want to waste CPU / battery)