OMAC : Padding on empty string I started to implement some MAC since last week with the specifications given here. I'm currently testing the OMAC (one-key CBC) with test vectors. In the OMAC specifications at page 4, they explain how the padding works. Just below that, they said :

  [...] Where the empty string counts as one block.

This is strange, because the block is empty and that cause me a problem. How could I use M[i] and Xor it with Y[i-1] if M[i] is empty ? (see the algorithm definition at page 8)

Following this question, should I pad the message to get a full block before working with M even if the padding is applied after the for-loop ? I think this would be logic but am I right with this logic ?

A clear explanation of that will be very appreciated. Thanks for all help I'll got.

What the specification is saying is that prior to processing, the message is padded to a full block length, with the empty message padded to a single block.

The spec on page 4 describes the input into the algorithm as:

Define $||a||_n = max\{1, \lceil|a|/n\rceil \}$, where the empty string counts as one block
Let $m = ||M||_n$
Partition $M$ into $M[1] ... M[m]$, where $|M[i]| = n$ for $ 1 \le i < m$

i.e. The number of blocks of size $n$ in a message $M$ is rounded up, and must be at least 1 before it can be passed to the $CBC{-}MAC$ portion of the algorithm.

The padding applied to the last block (which is an empty block for the empty message) is defined in formula $(1)$. In byte terms it translates to:

Set the first byte to $0x80$ (i.e. set the high bit)
Set all remaining bytes to $0$

In implementation terms, this means that you would buffer up to (and including) a complete block, and only process that block when either more data arrives, or the MAC is finalised - an empty message is thus treated as a 0 byte block that needs padding, and a full last block is not padded.

If you're not trying to implement from the spec as an exercise, the Bouncy Castle CMAC implementation should make the buffer/padding scheme clear (CMAC being the NIST standarised name for OMAC1).


What does TLS_ECDHE_ECDSA_with_AES_128_CCM means collectively. What is the signature algorithm and keys used here? Will the signature algorithm be ECDSA and key (i) ECC key or (ii) ECDHE and ECDSA keys?

TLS_ECDHE_ECDSA_with_AES_128_CCM

ECDHE: Key exchange with Ephemeral Elliptic Curve Diffie-Hellman
ECDSA: Signature with Elliptic Curve Digital Signature Algorithm
AES_128 : 128-bit Encryption with Advanced Encryption Standard
CCM: Mode of Operation with Counter with CBC-MAC which is an authenticated encryption algorithm designed to provide both authentication and confidentiality.

ECDHKE_ECDSA key exchange is performed as defined as in rfc4492 and the x-coordinate of the shared secret is applied to a KDF to derive the key. The same key both in AES and CCM.
CCM combines CTR mode of operation and CBC-MAC. It has an authenticate-then-encrypt authenticated encryption.  Firstly, the message tag $t$ is calculated on the message by CBC-MAC then the message and the tag are then encrypted using counter mode (CTR). In the above, the encryption is done by AES. CCM only defined for 128-bit block sizes.

The good

this scheme can work on a single key.
The encryption scheme is semantically secure under a chosen-plaintext attack.
The MAC function is unforgeable under a chosen message attack.

The bad:

Like any mode uses CTR internally (e.g. GCM) the (key,IV) pair reuse must not occur.

It is defined in rfc7251 with 4 ECC
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_128_CCM = {0xC0,0xAC}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_256_CCM = {0xC0,0xAD}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_128_CCM_8 = {0xC0,0xAE}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_256_CCM_8 = {0xC0,0xAF}

And it is mentioned that these cipher suites make use of the AEAD capability in TLS 1.2 RFC5246 in June 2014
The 8 means use eight-octet authentication tags and the default is 16 octets


What is h in this RSA variant? I am trying to implement a proposed improved algorithm of RSA . Here the author has increased the number of exponents. However I am unable to understand what $h$ is in the Key generation step. Can someone tell me what $h$ is exactly?

The author's paper is : http://www.jacn.net/papers/47-N024.pdf
I had originally posted this paper : http://iosrjournals.org/iosr-jece/papers/Vol9-Issue1/Version-5/H09154347.pdf

  n = p x q
  Ø(n) = (p-1)(q-1)
  ϒ n, h = ph-p0 ph-p1…ph-ph-1 + qh-q0 qh- q1 … qh-qh-1
  r such as 1 < r < n
  and gcd r, Ø=1 and gcd r,ϒ=1 (r should be small integer)
  e such as r.e = 1 mod Ø(n) and 1< e < Ø(n)
  d such as d.e= 1mod ϒn and 1 < d < ϒn
  Encryption Key = {e,n}… public key
  Decryption Key = {r,d,n}… private key

The authors of the paper might be able to tell you; I suspect no one else will.

You are having problems understanding the paper; a large part of the reason is that the paper isn't very well written; it introduces terminology (such as "ph") without ever defining it, and includes things that don't make any sense, such as the first line of their "Encryption Process": "If M=3, such that M$<$n ").

This might be an indication that they are not used to writing papers (along with their lack of fluency in English), or it might be an indication that they really don't know what they're talking about.

My best guess about their proposal (from making "corrections" in what they wrote, and in a way that's looks to be secure) would be:

Select primes $p$ and $q$ and a small value $r$
Compute $e = r^{-1} \bmod pq$ and $d = e^{-1} \bmod (p-1)(q-1)$ (there's no indication what to do if $e$ is not relatively prime to $(p-1)(q-1)$; perhaps pick a different $r$?)
To encrypt a message $M$, compute $C = eM^e \bmod pq$
To decrypt a message $C$, compute $M = (rC)^d \bmod pq$

This would work and also be secure (as it can be easily reduced to RSA); however it also begs the question "what advantages does it have over standard RSA?".  After all, they use a large public exponent $e$ (remember, it's $r$ that is small); and so it would appear they're making the public operation more expensive; what benefit are they gaining for that expense (perhaps some tolerance to side channel attacks?  If so, they would need to spell out the side-channel resistant implementation).


Computational LWE-Trapdoor without tag In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$  in paragraph $\textbf{Further optimizations}$ in section 5.2 if we use a single tag $H=I$. I want to use this together with the computational instantiation but I do not get how to reduce this case to the LWE-problem here.

We can obtain a gadget-matrix $G' = \left[ I \  | \ \tilde{G} \right]$ with an identity submatrix by a unitary transformation $G' = G \cdot U$ where $G$ is the gadget-matrix mentioned in the paper. Thus, $S' = U ^{-1}S$ is an adequate basis for $G'$ where $S$ is the basis from the paper.
Next, we let $\bar{A} =  \hat{A} \xleftarrow{$} \mathbb{Z}_q^{n \times n}$ and $R \xleftarrow{} D$ be random and then we obtain a "tuple" $\left[ \bar{A} \ | \ 0 \right] T^{-1} = \left[ \bar{A} | -\bar{A}R  \right]$ or the parity-check matrix
$A = \left[ \hat{A} \ | \ G' - \hat{A}R \right]$. But in this case I don't how to use this as an instance of decision-LWE.

Here is the optimization in more detail. Start with $[\bar{A} \mid I_n \mid G']$ where $\bar{A} \in \mathbb{Z}_q^{n \times n}$ and $G = [I_n \mid G']$ (where $I_n$ is the $n$-by-$n$ identity matrix).
Note that the concrete gadget matrices $G$ constructed in the paper already contain an identity submatrix (up to reordering of columns). But in general, $G$ will have an invertible $n$-by-$n$ submatrix $K$, which we can move to the leftmost columns, and then replace $G$ with $K^{-1} G = [I_n \mid G']$. This is just as good of a gadget matrix as the original $G$, because it has the same kernel lattice $\Lambda^\perp(G)$ (up to permutation of coordinates).
Now we can build a public matrix $A = [\bar{A} \mid I_n \mid G' - (\bar{A} R_2 + R_1)]$ for secret short $R_1, R_2$ whose entries are drawn from $\mathcal{D}$, which will serve as the trapdoor. (In fact we really only need to store $R_2$; see below.)
The $[\bar{A} \mid \bar{A}R_2 + R_1]$ part is an LWE instance and hence pseudorandom by assumption, so $A$ is indistinguishable from uniform (apart from its $I_n$ submatrix). We also have $$ A \begin{pmatrix} 0 & R_2 \\ I_n & R_1 \\ 0 & I \end{pmatrix} = [I_n \mid G'] = G, $$ which is the desired "trapdoor" relation. (Of course we can treat the $0$ and $I$ submatrices in that block matrix as implicit.)
We are basically done, but note that LWE instances constructed from $A$ should ignore its $I_n$ submatrix (see also this question and my comment); let's make this explicit. By dropping the $I_n$ submatrix from $A$ we get $A' = [\bar{A} \mid G' - (\bar{A}R_2 + R_1)]$ and $$ A' \begin{pmatrix} R_2 \\ I \end{pmatrix} = G' - R_1 .$$ This is a good enough approximation to the trapdoor relation when we use only "short" LWE secrets $s$ and the identity tag: given $b^t = s^t A' + e^t$ for sufficiently short $s,e$, we can use the trapdoor $R_2$ to compute $$ b^t \begin{pmatrix} R_2 \\ I \end{pmatrix} = (s^t A' + e^t) \begin{pmatrix} R_2 \\ I \end{pmatrix} = s^t (G' - R_1) + e^t \begin{pmatrix} R_2 \\ I \end{pmatrix} \approx s^t G',$$ from which we can recover $s$ and then $e$.
Importantly, the "most-significant bits" of the entries of $s$ are zero because $s$ is short, so to recover $s$ from the "noisy" $s^t G'$, we don't need the "noisy" $s^t I_n$ subvector that is now missing due to omitting $I_n$ from $G$. If we were to use a non-identity invertible tag $H$, then we would need to recover $s$ from a noisy $(s^t H)G'$, which is trickier because $s^t H$ can have "large" entries. It's not clear to me whether this can be done efficiently in general.


Distribution of the Difference of Uniformly Random Elements In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (finite) field is again uniformly random (Lemma 5.9). This is again used in the reductions of 'Worst-case to Average-case Reductions for Module Lattices', for Module Learning with Errors.

Firstly, why is this true?
Secondly, what happens when you relax the algebraic conditions on the sample space? For example, in an integral domain, one might not have inverses at all; is there a different sufficient and necessary condition for the difference of distinct, uniformly random elements in an integral domain to be again uniformly random? What about simple modules? Euclidean domains?

Firstly, why is this true?

This is easy to see, if we consider the finite field as a finite group with the addition operation (and ignore the multiplication operation)
If we consider the value $X - Y$, where $X, Y$ are uniformly and independently distributed elements of the group, then there are $n^2$ equiprobable $X, Y$ pairs possible (each with a probability $n^{-2}$.
For any group value $Z$, we have $Z = X - Y$ for $n$ possible $X, Y$ pairs (if we select any value for $X$, we see that the unique value of $Y$ that them sum to $Z$ is $X-Z$); each possible pair has probability $n^{-2}$, and so the probability for the sum to be $Z$ is $n^{-1}$.  This holds for all group members, and so the sum is equidistributed.

Secondly, what happens when you relax the algebraic conditions on the sample space?

As long as the relaxation still leaves us with a ring (that is, the addition operation is still a group), the above argument still holds.


TLS 1.2 is still secure or should we move to TLS 1.3? There are some vulnerability such POODLE, that allows the attacker to gain access to encrypted blocks of data and then gain exposure to plain text information using side channels.
Another vulnerability is TLS 1.2 which allows the GOLDENDOODLE attack to breach outdated crypto methods.
Is TLS 1.2 still secure and reliable or should we leave it and migrate to 1.3?

According to who? According to NCSC (the Dutch center for cyber security) for instance, TLS 1.2 is still considered "good", but it does go on to specify which cipher suites and specific configuration options are still considered "good".
This is kind of the problem with TLS 1.2: it has become a hodgepodge of different algorithms, key agreement schemes, certificate status, signature formats, bulk ciphers, hash algorithms and whatnot. So specifying that TLS 1.2 is good enough is basically hiding all the problems that are associated with it. TLS 1.2 is as good as the options that are chosen, and making sure that all the configuration / implementation pitfalls are avoided.
TLS 1.3 has been defined to strip most if not all of these problems away, and be build upon the best practices for popular encryption algorithms. It is both very similar to TLS 1.2 and different path from 1.2 in that sense. We've come a long way, and it is likely that TLS 1.3 will be more secure for longer than TLS 1.2 in a generic sense.
Is TLS 1.3 perfect? No, problems have and will be found. But it is generally more secure, more performant it has certainly a lot fewer options compared to TLS 1.2 that are certainly not secure or that are likely to become security issues in the future. There are still things like the mentioned 0-RTT and PSK that are relatively dangerous to use. In that sense TLS 1.3 in itself is not a secure solution all by itself either; specific usage scenarios still have to be considered.
That all said, it is certainly possible to configure TLS 1.2 in such a way that the protocol is still considered secure, or at least not broken fundamentally. So in that sense I suppose you could argue that there is no pressing need to move to TLS 1.3, as long as your choices for TLS 1.2 are considered sound.
Do note that this also kind of assumes that the inherent complexity of TLS 1.2 is not a problem in itself, and that's certainly debatable as well.


Why does the modulus of Diffie–Hellman need to be a prime? I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?

Answer to Martin's and Vadim's comments:

Let $n:=p$ and you want to find $x$ with $g^{x} \equiv y \bmod pq$

Calculate the two easier DL problems:
 ${x_p}$ with $g^{x_p} \equiv y \bmod p$
 ${x_q}$ with $g^{x_q} \equiv y \bmod q$

Note that
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

With the chinese remainder theorem you can calculate $x'$ from $x_p$ and $x_q$ with
$x' \equiv x \bmod lcm(p-1, q-1)$


Looking at just EC Public Key parameters, how can you tell if it is invalid? I am trying to handle when a parsers goes off the rails and reads an EC public keys wrong (just the X and Y components, I know the curve prior).
Right now I check for the following (false means invalid):

Is the key even on the Curve?
Is the Public Key X component less than the Curve's Base Point X?

I am pretty confident in #1, but not as confident in #2. #2 was just made by never seeing a case that contradicted it.
So my question is, 1) are these two checks correct? 2) are there other checks that can detect bad public keys?

The general rule for curves is given in;

2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone
They defined a point is valid if

$P \neq \mathcal{O}$
The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation - against the twist attack
Check $[n]P = \mathcal{O}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($h>1$) where $h$ is the cofactor $h = \#E(k)/n$

if 1,2, and 3 are verified and $h=1$ (i.e. prime curve) then the 4th is already satisfied.


Can we use Bitcoin miner to break 2Key 3DES, if yes how long it takes? As ASICs are specifically designed to generate the hash for a block of a block chain. which is much faster than other GPUs which are used to break 2key-3DES. can we use Array of ASICs to break 2key-3DES in practical time?

First of all, 2DES is
$$\textrm{ciphertext} = E_{K_1}(D_{K_2}(E_{K_1}(\textrm{plaintext})))$$
The below from 19 September 2020 on the Bitcoin mining, Bitcoin mining is based on SHA256d calculations. All in all, ASICs, FPGAs, GPUs, and CPUs.
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in a hour} & \text{in a day} &  \text{in an Year} \\ \hline
\text{Bitcoin Miners on SHA-256D} & \approx 2^{67.9} & \approx 2^{84} & \approx 2^{84.3} & \approx 2^{92.8} \\ \hline
\end{array}
We can adjust the values if we can find 2DES implementation, however, the miners use various sources to mine, however, we can approximate with hashcat on Nvidia RTX 3080.
Hashmode: 14000 - DES (PT = $salt, key = $pass)
Speed.#1.........: 53585.1 MH/s
Hashmode: 1410 - sha256($pass.$salt)
Speed.#1.........:  6980.9 MH/s (81.18ms)

The DES is around 8 times faster ( not going into too many details of hash modes ) and 2 times for SHA256d that makes $2^4$-times faster. We call the DES 3 times so the speed is $2^4/3$. Make a little approximation it to $2^3$
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in a hour} & \text{in a day} &  \text{in an Year} \\ \hline
\text{Bitcoin Miner on 2DES adjusted} & \approx 2^{70.9} & \approx 2^{87} & \approx 2^{87.3} & \approx 2^{95.8} \\ \hline
\end{array}
So in a year, they can reach $\approx 2^{95.8}$  2DES calculations. Therefore they still need $112-86.8 = 20.2$ year that is $\approx 1048576$ years to execute brute force for a single target.
The above is a simple full brute force attack. In a more careful attack design (thanks to Poncho), the attackers can simplify some calculations
for key1 in KeySpace:
   c' = DESDec(k1,m)
   m' = DESEnc(k1,c)

   for key2 in KeySpace:
      assert m' = DECEnc(k2,c')

Now this totally calls $2^{56}( 2 + 2^{56}) = 2^{57} + 2^{112} $. The outer loop can also benefit from calling the key sechedule once. This can speed the brute-force attack 3 times.
One can go for better options. An interesting case is a multi-target attack. With a multi-target attack, you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{112}/t$. For a billion targets, the cost would be below $2^{84}$ and the time would be below $2^{54}$


What is the best way to encrypt form data from client end javascript and decrypt at server side Java? I have to send user data from a form to server side and process it. But I would like to encrypt this information to make sure the information is safe.

I am using a random word Array as salt, another random word array as IV, userId as passphrase to encrypt the password.
Same salt and IV, password (without encryption) as passphrase is used to encrypt userId.

Salt, IV, userId (both plain and encrypted), encrypted password is sent to server side where the reverse operation is performed to decrypt the data.

But since passphrase is also available at client end, this doesn't seem safe. What is the best way to achieve this?

If you are not using SSL/TLS on the web server, any man-in-the-middle can tamper with the javascript code as it is pushed from the server to the client. At that point, an attacker can disable any client-side protections you have added. So, without SSL/TLS, anything you do is basically useless.

Now, once you enable SSL/TLS on the server and force users to connect via that secure connection, all information is protected in transit already, so no additional protections are needed.

So, enable SSL/TLS on the server and force all connections to use that and you are good to go.


How are CRL implemented? The source from where I learn states:-

  CRL (Certificate Revocation List) is the primary means of checking status of certificates offline.

But I can't seem to understand how is it possible for a single device (smartphone, computer etc) to store the status of every single certificate that has been revoked in existence? Won't the certificate dump become a little too big incorporating every single certificate that has been revoked?

Each CA has their own revocation list. When your device validates a certificate, it determines what CA was used to sign it, downloads the CRL (whose URL is included in the CA certificate) and checks if the serial number of the certificate is included in it.

Since all certificates have expiration dates, then any certificate in a CRL can be removed from the CRL when it expires. This prevents the CRL from growing forever.

That being said, CRL aren't used anymore by many clients, which now rely on other mechanisms like OCSP stapling.


RSA Algorithm modulo operation As per wikipedia
$$c = m^e \bmod n$$
where $c$ is the cipher text and $m$ is the original message.

To decrypt $$m = (c^d) \bmod n$$ that is $$m = (m^e \bmod n)^d \bmod n$$

My question is how do we have the following equivalence? $$(m^e \bmod n)^d \bmod n \equiv (m^e)^d \pmod n$$

The maths is fairly straightforward.

Replace $m^e$ with $a + bn$, where $a = m^e \bmod n$, and $b$ is an integer (equal to $\lfloor m^e / n \rfloor$).

The binomial expansion of $(m^e)^d$ can then be substituted with the expansion of $(a + bn)^d$ as follows:

$$(a + bn)^d = a^d + c_1a^{d-1}.bn + c_2a^{d-2}.b^2n^2 + \cdots + b^dn^d$$

where $c_1$, $c_2$ etc. are binomial coefficients.

Apart from the first term $a^d$, every term in this expansion is a multiple of $n$ and is therefore equal to zero (mod $n$).

Hence, $(m^e)^d \bmod n \equiv a^d \bmod n \equiv (m^e \bmod n)^d \bmod n$


Keyed reversible hash function? Is there such thing as a keyed reversible hash function? This would be a hash function where computing H(x) is easy and requires no key, but computing x from H(x) is only feasible with the key.

Is this absolutely synonymous with digital signatures? Or is this something else and does such a thing exist? It feels like the inverse of public key cryptography: encryption is public, decryption (reversal of algorithm) is private.

I think what you might be getting at is providing a signature that can only be verified by a particular party (i.e. who has access to the key).  Encrypting any normal hash value with the public key of the intended recipient would effectively do that.  The recipient could decrypt the hash with their private key and then re-hash the message to verify it.  Others would be left unsure of what the additional data represented.

However, if you're thinking of "hashing" the full message in a way that only the intended recipient reverse it, that is pretty much what defines encryption. And, as mentioned in the comments, public key cryptography handles exactly this use-case.

Either way, public-key cryptography seems to be what you're looking for, it's just a matter of how you want to deploy it.


RSA: Is it secure to use the private key to encrypt and the public key to decrypt? This may sound weird:
What if I don't let others know my public key, then use my private key to encrypt, and the public key to decrypt? Is this secure?
Let me explain a little bit:

Common usuage: use private key to sign and disclose public key, then others can vefriy the data signature use public key

Weird usage: use private key to encrypt and don't disclose public key, in other end use public key to decrypt. notice here I will not disclose private key
either so it's not swap
In second scenario, if I can keep both keys secure(I mean don't disclose to otheres), does it secure?

No, you generally cannot swap the public and private keys.

Your public key consists of a public exponent and a modulus. The modulus should be known to the person doing the encryption. The public exponent - in general - is a relatively small prime such as 3 or 65537 (Fourth number of Fermat). So given the modulus all an attacker has to do is guess the public key. It's very easy to factor pretty small exponents (I've written software to generate public keys given a private key). The exponent of the private key on the other hand consists of a number that is about as large as the modulus. It cannot be easily factored; the security of RSA relies on this fact.

Currently the majority of software uses RSA with a small public exponent. It is however possible to create an RSA exponent that is the same size as the private exponent. In that case you would have something close to two private keys. Note however that the public key is generally not required to be private. So software may not protect the public key as much as the private key (with regards to e.g. side channel analysis). Sometimes the software may also use padding required for signature generation instead of those for encryption if you present it a public key - mainly due to some weird signature functions required for SSLv3 and TLS 1.0.

So even if your software would accept the public key - RSA is modular exponentiation after all - then by all practical means it not going to be secure.


There are no known attacks on SHA3 series that are faster than the generic attacks.

Your problem is the 2nd pre-image attack: given a message $m_1$ finding another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$.

SHA3-256 has $2^{256}$ 2nd preimage resistance.

Now, you only allow the attacker first 20-byte which is 160-bit of your data. The attacker must try to find the $m'$ if exist. He cannot brute-force the 160-bit space to execute the generic attack. That is not reachable, even 128-bit is not.

The bitcoin miners' latest SHA-256 hash rate peak was $2^{66}$ hashes per second and $2^{83}$ per day from 108464285TH/s on 29/09/2019.

Another question is: does this 2nd pre-image exist? With a negligible probability, no!

  Even if the change is about a single byte,

We want the avalanche effect from the hash functions that is; a single bit flip should randomly flip the %50 percentage of output bits.

In general, if you want to find an attack into a good hash function you need some degree of freedom. What you are looking for is the reverse.


Why do we append the length of the message in SHA-1 pre-processing? As we know, SHA-1 is irreversible, so why do we append the length of the message to the preimage?

Wikipedia has a reasonably good explanation about the Merkle–Damgård construction. The idea is the following: SHA-1 is built around an internal "compression function" which takes as input the 160-bit state and a 512-bit message block, and returns a new state. The padding is designed so that it can be proven that a collision over the hash function necessarily implies at some point a collision in one of the calls to the compression function.

For instance, imagine that the padding merely consisted in appending zeros, up to the next block boundary. Then you could imagine getting a collision between a one-block message $m_1$ and a two-block message $m_2$, where the second block of $m_2$ is exactly $m_1$ (this would require the processing of the first block of $m_2$ to end up with exactly the initial state). In this case, there is no collision in the compression function per se.

This does not mean that the all-zero padding is weak; but the padding used in SHA-1 and other Merkle-Damgård schemes ensures that we can concentrate on the compression function alone, without taking into account multi-block messages: if we can "prove" the compression function to be collision-free, then so is the whole hash function. That's what the padding is for: to turn a collision-free compression function into a collision-free hash function.


AES implementation to encrypt files I'm making a small python program to encrypt an arbitrary text file.

Currently I have a file to store passwords (hashed values), so nothing stored in plaintext. The user enters the command line arguments of a flag '-e' or '-d' to encrypt or decrypt, and a filename and a password. The password to encrypt is different to the password to decrypt, one cannot be used for the other.

The encryption works although I'm not 100% sure I'm doing it correctly. I take the file and read through it line by line, appending each line to a list. Then making a random 128 bit IV using the hashed password the user entered as a key to encrypt each line. Then I write these lines to a new file and save the file.

I'm not sure I should be using the hashed password the user entered as the key to encrypt, because I'm saving the hashed value of the password the user entered in a password file to check against user input! (if that makes sense).

Anyway my main problem is decryption, because the file was encrypted with PASSWORD_ENCRYPT, and the user wants to decrypt with PASSWORD_DECRYPT, the two are not the same. So I don't have the key to decrypt the file?

Here's some code of my encryption.

backend = default_backend()
key = hashed_password
iv = os.urandom(16)
cipher = Cipher(algorithms.AES(key), modes.CFB(iv), backend=backend)
encryptor = cipher.encryptor()
lines_of_ct = [iv]
for each_line in list_of_incoming_lines:
    b = each_line.encode('utf-8')
    lines_of_ct.append(encryptor.update(b))

try:
    with open(file + ".enc", "w") as enc:
        for each_line in lines_of_ct:
            print(each_line, file=enc)

My question is, how can I decrypt the file with the user entering a different password for read access (decryption). Is there a way to safely append the original encryption password/key to the file so I can retrieve it and use it? Like I have done with the IV, I attached that to the star

To make the encrypt and decrypt passwords different, whoever has access to the encryption password would also need to know the key derived from the decrypt password, and the encrypt password simply unlocks that key. Then you have something like this:

Enc password is entered
Enc password is derived to key $K_E$
$K_E$ is used to decrypt the stored decrypt key $K_D$
A random key $K_R$ is used to encrypt the data
$K_R$ is encrypted with $K_D$ and appended to the message with the IV

Upon decrypt, the correct password will be derived to $K_D$ and used to unlock $K_R$, which can then decrypt the message.

In regards to the rest of your system, reading line by line is a very bad idea. In this case you are not encrypting the line breaks, and someone looking at the encrypted data will know the approximate structure of the message. You should read the file as a stream of bytes from end to end and encrypt all of them. The ciphertext should also not use any kind of encoding, as that could cause a problem during decryption. If you need the ciphertext to be copyable as text, like into an email or text message, it should be encoded to Base64.

Also simply hashing a password for use as a key is wrong, you need a key derivation function such as PBKDF2. There are MANY questions regarding this here, I would suggest reading a few of the highest voted questions and answers.


Is truncating a hashed private key with SHA-1 safe to use as the symmetric key for AES for data at rest? I realize this is mixing the purposes between asymmetric and symmetric crypto, but I was wondering if it is safe to use a hashed, truncated private key (asymmetric) as the symmetric key for encrypting data at rest? For this question I  am presuming RSA is a 1024 bit key, SHA1 produces 160 bits, and AES is using a 128 bit key.

It appears that the data obtained from an RSA private key maintains a specific structure and is not completely random, so simply taking the first 128 bits from the private key would not provide enough entropy for a symmetric key, correct? (I previously heard that truncating a randomly generated number is okay when selecting symmetric keys - but in this case all the data within the private key is not random)
By hashing the entire RSA private key, the result is condensed into 160 bits, more usable with AES 128 key size, but are we greatly reducing the entropy by doing so? (Of course you could use SHA2 for AES 256, etc)
Would it be recommended to extract something like the algorithm components instead like p and/or q since those values are 'more' random?
Any other suggestions?

Thanks in advance!

I see no reason why that wouldn't be secure.
If you want to be sure, though, you could use a standard key derivation function such as HKDF or PBKDF2 to derive the symmetric key from the RSA key.

These functions are primarily designed for deriving encryption keys from low entropy-per-byte sources such as passphrases, but there's no reason why you couldn't use an RSA key as the "passphrase".  In any case, what they're designed to accomplish is to distill the entropy from a long but not entirely random input down into a pseudorandom output suitable for use e.g. as a symmetric encryption key.

(Many KDFs also include features such as adjustable work factor parameters for key stretching, useful for slowing down brute force attacks on low entropy passphrases.  However, for your application, you may safely choose a KDF without such features, or just set the parameters for maximum performance.)


Simulation Based Proof: What Can / Can not Simulator Do? I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance:

In "Foundation of..." page 660, Coin Tossing protocol, the simulator first receives the result from trusted third party (TTP) without sending the parties input to it. My question is why can it do so, where in the real protocol the parties exchange their input first.
In "Efficient two..." page 140, full simulation oblivious transfer, the simulator:

(a) Can receive the adversary input to underlying zero knowledge and extract its secret value. This is not possible for an honest party in the real world model.

(b) The simulator (despite using some incorrect input to zero knowledge) makes the adversary believe that the zero knowledge proof is verified, where it would not occur in the real world model.

Main question: What can and cannot the simulator do when simulating the real world?

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the security proof. Thus, in the case of coin tossing where no party has input, the simulator begins by getting the output. This is allowed by definition.

Now, the simulator typically works by running the real-world adversary. Here it has power. For example, it can rewind the real-world adversary, can look at its random tape, and so on. (This gets complicated depending on the model. For example, in the common reference string model it's different. But let's leave this for now.)

Finally, in a HYBRID model, there are additional issues. In this model, the parties exchange messages but also have access to a trusted party. When simulating a protocol in this model, the simulator actually runs the trusted party for the adversary. Thus, in the ZK-hybrid model, the simulator gets the adversarial prover's input (which includes the witness). This is allowed by the composition theorem of the model being used.

None of this is straightforward, and it's very hard to learn by yourself. I suggest that you look at some videos online; they may help. For example, the Bar-Ilan Winter Schools from 2011 and 2015 cover secure computation and may help you get started.


Encryption of large files RSA I know that asymmetric cipher shouldn't be used for encryption large files because it is slow. It is better to use symmetric cipher. But, what worse, I've read that it is unsecure to encrypt a large file with a public key. But, why?

Safe encryption of large files with RSA is possible. One can split the file into suitably small blocks, and encipher these individually with a safe RSA-based encryption scheme. The receiver deciphers the ciphertext blocks, and concatenates the deciphered plaintext blocks. This demonstrably is safe (in the sense that it protects the confidentiality of the large file), if the RSA-based encryption scheme is (this requires random padding, and excludes textbook RSA encryption, which allows to verify a plaintext guess).

This is however rarely done in practice because:

RSA is slow/compute intensive compared to symmetric encryption, especially for decryption; and that slowness applies to the decryption of each of the many blocks, and becomes a computational bootleneck. We are talking like 4 decimal orders of magnitude or more compared to symmetric encryption. Making the modulus larger reduces the number of blocks but worsens the problem, because RSA's execution time grows much faster than linearly with the modulus size (even much faster than quadratically, for decryption).
Safe RSA-based encryption schemes expand the size of the ciphertext. For example RSA-OAEP with SHA-256, when using 2048-bit RSA, uses 2048-bit ciphertext blocks (256 bytes) which convey at most $2048-2\cdot256-16=1520$ bits (190 bytes), loosing over 25% of the bandwidth. This can only be improved to some degree (for $n$-bit security, there must be at least $n$ bits lost per block).
RSA with long-term keys does not offer forward secrecy.

Hybrid encryption solves 1 and 2. Negotiating a session key with an appropriate protocol can solve 3.


Why is a nonce used to initialize Hash_DRBG, HMAC_DRBG, and CTR_DRBG? In NIST 800-90A, Hash_DRBG, HMAC_DRBG and CTR_DRBG (with derivation function) all require a nonce for instantiation.

I understand the usual application for a nonce to prevent replay attacks. However, I don't understand the security benefit a nonce provides for a CSPRNG. Additionally, I am wondering why CTR_DRBG without a derivation function does not require a nonce.

What am I missing here?

What am I missing here?

You could re-use the master secret over multiple invocations and just rely on different nonces.

This may come handy – for example – on embedded hardware without a proper True Random Number Generator.


Cryptographic limit to total accounts in secp256k1 Factoring in birth day attacks and all that, with 256-bit elliptic curve cryptography, lets take secp256k1 as example that Bitcoin uses, what is the maximum number of accounts that are secure? It isn't $2^{256}$ since then any time you generate a random number you find a used account.
Birth day paradox and all that, what is the upper limit of how many accounts secp256k1 actually supports?

The upper limit really depends on your risk. The birthday attack's 50% probability is a too big risk to rely on. Let's look at some numbers assuming that the total of the points is $2^{256}$ which is not bu very close*. Assuming the keys are constructed uniform randomly like a coin toss.
We will use the fact that the probability of collision among uniform randomly selected $k$ elements in the set of $n$ element can be approximated by $(2^{k})^2/2^{n}/2=2^{2k-n-1}$

Consider $2^{100}$ private keys, that has a probability of collision
$$(2^{100})^2/2^{256}/2 = 2^{200 - 256 - 1} = 1/2^{57}.$$ Not going to happen  $\times 2^{-40}$ ans still very low proabaility to execute an attack.

Consider $2^{90}$ private keys, that has a probability of collision
$$(2^{90})^2/2^{256}/2 = 2^{180 - 256 - 1} = 1/2^{77}.$$ Not going to happen $\times 2^{-20}$

Consider $2^{80}$ private keys, that has a probability of collision
$$(2^{80})^2/2^{256}/2 = 2^{160 - 256 - 1} = 1/2^{97}.$$ Not going to happen

Consider $2^{70}$ private keys, that has a probability of collision
$$(2^{70})^2/2^{256}/2 = 2^{140 - 256 - 1} = 1/2^{117}.$$ Not going to happen $\times 2^{20}$

Consider $2^{60}$ private keys, that has a probability of collision
$$(2^{60})^2/2^{256}/2 = 2^{120 - 256 - 1} = 1/2^{137}.$$ Not going to happen $\times 2^{40}$

Consider $2^{50}$ private keys, that has a probability of collision
$$(2^{50})^2/2^{256}/2 = 2^{100 - 256 - 1} = 1/2^{157}.$$ Not going to happen $\times 2^{60}$

Consider $2^{40}$ private keys, that has a probability of collision
$$(2^{40})^2/2^{256}/2 = 2^{80 - 256 - 1} = 1/2^{177}.$$ Not going to happen $\times 2^{80}$

Actually, there is no need to look lower than $2^{70}$ since the probability is already is so tiny to happen. When it is around $1/2^{100}$ we simply say that it is not going to happen. Similarly, there is no need to look over $2^{80}$ since normally, that amount of users is not going to be needed. This also shows that if an entity tries to randomly guess the private keys, will fail.
In the case that one entity decides to attack all $t$ targets than the cost to find the first of $t$ target is not cheaper than the DLOG.
* the order of the base point is = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141


Properly securing a private key for remote storage I am attempting to secure a private key for remote storage on an untrusted device. Here are the parameters and my assumptions, I'd like to confirm I'm correct with them.

The keypair that I wish to encrypt is generated with ECDSA using the P-256 curve. My understanding is that this curve has 128 bits of security.

I give the user a Diceware passphrase (using cryptographically secure entropy) consisting of 10 words. This has 129 bits of security (12.9 bits per word).

I use HKDF with SHA-256 (no salt, no "info" label) to turn this passphrase into an actual key. The WebCrypto API dictates that I also specify the algorithm I intend to use this key for. I specify AES-CTR with a key length of 128 bits. The derivation function then outputs 128 bits of data (presumably truncated from 256 bits from the SHA-256 HMAC used by HKDF). Should I use the full 256 bits here instead?

Finally, I wrap the key using AES-CTR with a new empty 16-length byte array counter and a length of 128. According to the WebCrypto docs that I could find, length is a value from 1 to 128. What does this length represent and am I using it correctly?

In conclusion, my assumptions: The passphrase has 129 bits of security, it gets fed to a key derivation function that preserves 128 bits of security, and then this 128-bit key is used with AES-CTR which I'm hoping someone can confirm preserves the 128 bits of security as well.

Therefore, can I conclude that the encrypted private key being public is as secure as the public key being public? Deriving the private key from the public is 128 bits of security hard and so is decrypting the private key.

You should store a salt for HKDF-Hash alongside the encrypted message.  That way, the adversary can't attack many passwords simultaneously.
You should use your application's name, and the purpose of the key, as the info for HKDF-Extract.  That way, even if you are tempted in the future to use the same password for another purpose, it will be clearer what you must do to avoid accidentally reusing the key.
It may be OK to use a 128-bit key, but unless you're budget-constrained, you should use a 256-bit key to avoid multi-target attacks on AES.  There's nothing wrong with using a larger key than your target security level.
The way that AES-CTR works is that for a key $k$ and a nonce $n$, it generates a one-time pad $\operatorname{AES}_k(n \mathbin\Vert 0) \mathbin\Vert \operatorname{AES}_k(n \mathbin\Vert 1) \mathbin\Vert \cdots$, and xors that with your message to get the ciphertext.

What does $n \mathbin\Vert 0$ mean, exactly?  It's the concatenation of some bit encoding of a per-message nonce, which may be anywhere from 0 to 128 bits, with some bit encoding of a per-block counter, whose length must be $128 - \ell_n$ where $\ell_n$ is the maximum number of bits in the nonce.  The point is that we never reuse $\operatorname{AES}_k(x)$ for different parts of the plaintext.

In the WebCrypto API, §25.3 AesCtrParams dictionary, your obligation is to pass a byte array [0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x0a 0x0b; 0x00 0x00 0x00 0x00] that will serve as the initial input with the nonce, and then specify how long the counter is to be incremented as an integer, marked in this example by a semicolon.

First, you must never use a nonce more than once with any given key.  If your key is used only once ever, then you can just use an all-zero or empty nonce.  If you reuse a key, then with AES, you should use a sequentially incrementing nonce, or think very carefully about what limits your application can live with on the number of messages you use any particular key with.  In this case, I recommend a single-use key; if you want to use the same password for different purposes, just derive an independent key using a different HKDF-Expand info parameter.

Second, the number of bits in the counter must fit the length of the longest message you can encounter.  That is, if you handle up to $\ell_m$-bit messages, then you must specify a counter length in bits that is at least $\lceil\log_2 \ell_m/128\rceil$.  Here we divide by 128 because each counter value corresponds to 128 bits of AES-CTR key stream.
Actually, you may not want to use AES-CTR directly because it does not provide authentication.  Unless you are again budget-constrained, or for some reason you want to avoid authentication (which makes sense in some applications, like a scheme to require 2FA for disk encryption so that the adversary can't even test a password guess without a separate physical token, but seems unlikely here), you should always use authenticated encryption by default absent a particular reason not to: AES-GCM, not AES-CTR.
Beware timing side channels in software implementations of AES (and GHASH, if you use AES-GCM)!  Even though hardware AES support is widespread today, it takes a lot of effort to audit your software stack well enough to guarantee it is reliably using the hardware AES support on all platforms that may be of interest to you.  If you use NaCl crypto_secretbox_xsalsa20poly1305 instead, this is not a problem.


Radioactive Decay, Gaussian or Uniform? I'm trying to understand the nature of true randomness. I'm building an RNG using a radioactive source. Basically, I'm measuring the time between consecutive decays which in theory should be unpredictable. The distribution of these time measurements shows a Gaussian-like distribution as I predicted. Now my understanding of true randomness requires a uniform distribution of variables, which is all variables are equally likely. How can I transform a Gaussian Distribution to uniform distribution and is it really necessary to have uniformly distributed random bits to have a good generator?

You can just follow the instructions on HotBits, which is exactly what you're trying to build. It's been running for years and is the only radioactive TRNG on the internet. It goes into great depth regarding underlying nuclear physics, sample distributions and extractor mechanism.
Although not really within the realms of strict cryptography, there is also a good counting analysis here from Caltech. In a nutshell, at low count rates the click rate follows a Poisson distribution. But as the mean click rate $(\mu$) increases, it morphs into a nice symmetrical Gaussian shape which is typical behaviour of Poisson if $\mu > \approx 20$.
If you can get a good tube and a decent/safe source, it'll be pretty simple if you follow the instructions.  Don't worry about the tick distribution. Simply detect the ticks and follow the de-biasing procedure in the sections featuring this:-

It's a reversing von Neumann extractor. It's written up so I won't repeat the details. If tube dead times and saturation levels are met (so that there is no autocorrelation), you'll get uniformly distributed random bits popping out of the de-biasing algorithm. So that we can see HotBits' quality, I downloaded their 91 Mbit data set and ran ent over it:-
Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size
of this 91750400 bit file by 0 percent.

Chi square distribution for 91750400 samples is 0.05, and randomly
would exceed this value 81.93 percent of the times.

Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141486168 (error 0.00 percent).
Serial correlation coefficient is -0.000773 (totally uncorrelated = 0.0).

They have other more stringent testing on their site, but it's a clean pass at this level. Chi square also answers your "is it really necessary to have uniformly distributed random bits to have good generator?" mini question. Yes, they do have to be uniformly random for cryptographic use.
So do what HotBits does.

Please note this though:-

the increased sensitivity of the RM-80 and its immunity from saturation increased the rate of HotBits generation from about 30 bytes per second to more than 100.

It's not fast. And there's all that high voltage stuff.


Semantic security IND-CPA of Affine Hill Cipher The ciphertext $c$ corresponding to plaintext $m$ is given by
$c= mK + w$. $K$ is the invertible matrix and w is the uniformly distributed random vector.
If $w$ is changed during every encryption, will this affine Hill cipher satisfy IND-CPA?
If $w$ is generated using a PRNG and this type of encryption is used as homomorphic encryption keeping $K$ same, will it still provide IND-CPA?
During decryption, $w$ should be subtracted from ciphertext first and multiplied with the inverse of $K$. For decryption, the key for the PRNG (LFSR based) can be used.
$(m1 + m2) = [(c1 + c2) - (w1 + w2)]K^{-1}$

Let $G:\{0,1\}^{r+l}\to\{0,1\}^*$ be some pseudorandom generator, let $K\in\text{GL}(\mathbb K,d\times d)$ be any invertible matrix over some field $\mathbb K$ and let $k\in\{0,1\}^{r+l}$ be the secret key for $G$ and $f:\{0,1\}^*\to \mathbb K^d$ be some bijective function mapping the PRG outputs to vectors, then $E_{K,k}(m):=m\cdot K+f(G(k))$.

This scheme is deterministic, that is given the same keys and the same message, it will always return the same encryption and thus cannot be CPA-secure.

However, we can easily modify the above scheme to make it CPA-secure. Let $G,K,f$ be as above and let $k\in\{0,1\}^r$. Define $E_{K,k}':=n\stackrel{\$}{\gets}\{0,1\}^l;n\parallel m\cdot K+f(G(k\parallel n))$, where $\stackrel{\$}{\gets}$ means that $n$ is sampled uniformly at random from $\{0,1\}^l$.

Essentially for every encryption we generate a nonce $n$, append it to the ciphertext and then use combination of the nonce and the key to generate the random bitstream. This is how stream ciphers work, but we are using vector-addition instead of XOR. Actually one could make appropriate choices for $f,K$ to turn this into a classic stream cipher by picking $K=\mathbb F_2$ and $f$ mapping bitstrings to vectors of the same strings. The bijectivity of $f$ is needed to preserve the uniformly random distribution of the output elements to make it an appropriate "pad". As for why $K$ is there, I don't know, it doesn't serve any purpose for the security in this scheme.


Is sharing the modulus for multiple RSA key pairs secure? In the public-key system RSA scheme, each user holds beyond a public modulus $m$ a public exponent, $e$, and a private exponent, $d$.

Suppose that Bob's private exponent is learned by other users. Rather than generating a new modulus, Bob decides to generate just a new public and a new private exponent $e'$ and $d'$.

Is this safe for Bob?

I had a similar problem, and it took me a long time to figure out all the math, as some of the proofs can be rather terse.  So, I took it upon myself to write a full explanation of how to factor N, without all the symbols and relying on a bit less prior knowledge.

This is an application of the shared modulus attack explained by Boneh in his analysis of RSA attacks.

Anyway, such a system is not safe.  If you know a valid $e$ and $d$, you can factor $N$.
Stated more formally, given $(e, d, N)$, where $N = pq$ for some primes $p$ and $q$,
and $ed \equiv 1 \bmod{\lambda(N)}$, one can easily find $p$ and $q$.

Note:  $\lambda(N)$ is the Carmichael function.  If you're used to seeing RSA described in terms of $\phi(N)$, this is very similar. Carmichael's theorem is a generalization of Euler's theorem stating:
$$\forall a\,|\,\gcd(a,N)=1,\; a^{\lambda(N)} \equiv 1 \pmod{N}$$
where $\lambda(N)$ is the smallest integer that makes this statement true.  For $N=pq$, this number is just $\DeclareMathOperator{\lcm}{lcm}\lcm(p-1,q-1)$.  It is also true that $\lambda(N)\,|\,\phi(N)$, so the use of $\lambda(N)$ instead of $\phi(N)$ when describing RSA is just a generalization.

First, a few facts. Consider solving the equation:

$$\begin{aligned}
y^2 & \equiv 1 \bmod{N} \\
y^2 - 1 & \equiv 0 \bmod{N} \\
(y+1)(y-1) & \equiv 0 \bmod{N} \\
\end{aligned}$$

i.e. computing the square root of one. Now, note that $p\,|\,N$ and
$q\,|\,N$. Since the zero product property
holds in modular arithmetic when the modulus is prime, it is true that:

$$y \equiv \pm 1 \bmod{p} \;\, \text{and} \;\, y \equiv \pm 1 \bmod{q}$$

Therefore, we know:

$$\begin{aligned}
y \equiv 1 \bmod{p} & \, \text{or} \;\, y \equiv -1 \bmod{p} \\
y \equiv 1 \bmod{q} & \, \text{or} \;\, y \equiv -1 \bmod{q}\end{aligned}$$

This gives two choices of remainder for each factor of N. From this, you
can construct four systems of equations by picking one value from each factor.
Each of these systems of equations has a unique solution modulo $N$ (by
the Chinese Remainder Theorem).
However, not all solutions are created equal. Consider:

$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv 1 \bmod{q}\end{aligned}$$

This has a solution $y = 1$, which is trivial. The solution where both
remainders are $-1$ is also trivial ($y = N - 1$), and is also not
useful. However, now consider the following case:

$$\begin{aligned}
y & \equiv 1 \bmod{p} \\
y & \equiv -1 \bmod{q}\end{aligned}$$

This has a non-trivial solution. Furthermore, if you know this solution,
you can factor $N$ by noting that $y - 1 \equiv 0 \bmod{p}$, so
$p\,|\,y-1$. Since $p\,|\,N$ also, it is easy to find $p$ by computing
$\gcd(y-1, N)$. The same can be said of the symmetric system of
equations swapping $p$ and $q$. Since $p$ and $q$ are interchangeable,
this has the same result.

We also know that any root that is non-trivial (i.e. is not 1 or -1) must
come from one of the two non-trivial cases we looked at because we know that
the solutions to these equations are unique.  This means that the above logic
works for any non-trivial root we may find.

Thus, we have fact 1: if $y$ is a non-trivial square root of one modulo
$N$, where $N$ is the product of two primes, one of the factors of $N$
is $\gcd(y-1, N)$.

The second is much simpler:

$$\begin{aligned}
a^b & = c \\
a^{{\frac b 2} + {\frac b 2}} & = c \\
a^{\frac b 2} a^{\frac b 2} & = c \\
(a^{\frac b 2})^2 & = c\end{aligned}$$

This is fact 2: given $a$, $b$, and $c$ such that $a^b = c$, the square root of $c$
is $a^{\frac b 2}$. This is easy to compute as long as b is even (i.e.
$2\,|\,b$).

Now for the actual attack. To begin, note that
$ed - 1 \equiv 0 \bmod{\lambda(N)}$. This value is important, so let
$k = ed - 1$. Because it is congruent to zero, $\lambda(N)\,|\,k$.
Furthermore, $2\,|\,\lambda(N)$, so $2\,|\,k$. Then $k$ can be written in
the form $k = 2^t r$ for some odd number $r$ with $t > 0$.

Then, picking any arbitrary $x$ (i.e. $\forall x\,|\,2 \leq x < N$):
$$x^k \equiv x^{k \, \bmod{\lambda(N)}} \equiv x^0 \equiv 1 \pmod{N}$$
Applying fact 2, we can find the square root of one modulo $N$ by
computing $x^{\frac k 2} \bmod{N}$. There are now several possibilities:

The result is $1$. This is a trivial solution. However, if the
exponent is even then it is possible to try again, dividing the
exponent by two again. If the exponent is odd, then pick a new $x$,
and try the attack again.
The result is $N-1$ i.e. $-1$. This is a trivial solution. Unlike in
the previous case, dividing the exponent by two again will not yield
a square root of one, but rather a square root of negative one.
Thus, pick a new $x$ and try again.
The result is neither of the above. This is a non-trivial solution.
All that remains is to factor $N$ by applying fact 1.

In other words, the algorithm can be stated as:

Compute $k = ed-1$
Determine the exponent of $2$, $t$, in the factorization of $k$,
i.e. factor $k$ into the form $k = 2^t r$ with $t > 0$ and $r$ odd.
Pick a random $x\,|\,2 \leq x < N$
Compute the sequence
$s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$
Determine the first index $i$ such that $s_i \neq \pm 1$ and
$s_{i-1} = 1$

If no such index exists, choose a new $x$ and try again.
Otherwise, let $p = \gcd(s_i - 1, N)$ and $q = \frac N p$.

Done.

The attack relies on the fact that you can easily generate numbers that
are congruent to one modulo $N$. Additionally, it is easy to take the
square root of these numbers by dividing the exponent by two. There is a
chance that taking this square root yields a non-trivial square root of
one modulo $N$, which allows you to easily compute a factor of $N$ by
using the euclidean algorithm. This is a probabilistic algorithm,
in that it relies on the solution being non-trivial.  If no non-trivial
solution is found, the algorithm needs to start over with a new $x$.

The chance of obtaining a non-trivial solution is an important
consideration when using this algorithm. So to determine this
probability, consider an approach which picks random $x$ modulo $N$.
$x^e$ for some exponent $e$, then, is also random. Also note
that, for any given modulus $m$, the set of integers are evenly
distributed modulo $m$ among the set of positive integers less than $m$;
i.e: $$P(x^e \equiv 1 \bmod{m}) = P(x^e \equiv m-1 \equiv -1 \bmod{m})$$
The proof for fact 1 requires the solution of a system of two
equations, each of which is “picked” from two possible equations. There
are four possible systems of equations, and each is equally likely because
of the equal distribution of numbers mod $m$.  Therefore,
the probability that the $x$ satisfies any one of these system is
$\frac 1 4 = 25\%$. Since two of these systems yield non-trivial
solutions, the probability of a non-trivial solution given a random $x$
is $50\%$. This probability is improved by continuing to calculate
square roots in the case that $\sqrt{x^e} \equiv 1 \bmod{m}$. However,
since this number is related to the previous number in the sequence, one
can no longer make a strict randomness argument that the next term in
the sequence also has a $50\%$ chance of being non-trivial. You can say,
though, that:
$$P(\exists \, \text{non-trivial solution in $s$}) \geq 50\%$$ for the
definition of $s$ given in the algorithm description above. Therefore,
the generation of a constant, finite number of sequences from random
values of $x$ can provide an arbitrarily high probability of yielding a
non-trivial solution.

Since computation of the entire sequence $s$ does not guarantee a higher
probability of finding a non-trivial solution, it is reasonable to
wonder why you should bother computing the entire sequence. However, it
is easy to get the entire sequence “for free” when computing
$x^{\frac k 2}$. By partially factoring $k$ into $2^t r$, $s$ can be
recursively defined as:

$$\begin{aligned}
s_t & = x^r \\
s_i & = s_{i+1}^2\end{aligned}$$

Note that this recursive definition defines the sequence back-to-front,
so in the process of computing $s_1$, one also computes all other terms
of the sequence. This squaring is the same computation the
pow-mod operation
would do anyway, so there is no added complexity in computing
the additional terms of the sequence.

Here, then, is code (in python) that performs the above partial factorization:

# Returns a tuple (r, t) | n = r*2^t
# Complexity O(lg n)*
def remove_even(n):
    if n == 0:
        return (0, 0)
    r = n
    t = 0
    while (r & 1) == 0:
        t = t + 1
        r = r >> 1
    return (r, t)

This can be implemented in $\Theta(\lg n)$ time. This implementation
does repetitive shifting, so in the worst case runs in
$\Theta((\lg n)^2)$ time. An implementation could achieve optimal time
by iterating through the bits of $n$ instead of doing repetitive shifts;
however, this is more difficult with python longs so this approach was
used for clarity.

This code will generate terms of the sequence $s$ until it finds a
nontrivial square root of one modulo $N$:

# Returns a non-trivial sqrt(1) mod N, or None
# Arguments:
#     x: random integer 2 <= x < N
#     k: multiple of lambda(N)
#     N: modulus
# Complexity O((lg n)^3)
def get_root_one(x, k, N):
    (r, t) = remove_even(k)
    oldi = None
    i = pow(x, r, N)
    while i != 1:
        oldi = i
        i = (i*i) % N
    if oldi == N-1:
        return None #trivial
    return oldi

In the worst case, this computes $x^k$ using the square-and-multiply
method, which is $O((\lg N)^3)$. As stated earlier, the probability of
the function returning a value (vice ‘None’), is at least $50\%$ for
random $x$.

Finally, here is some code to actually factor the modulus, given a valid
RSA key:

import random
import fractions

# Returns a tuple (p, q) that are
# the prime factors of N, given an
# RSA key (e, d, N)
def factor_rsa(e, d, N):
    k = e*d - 1
    y = None
    while not y:
        x = random.randrange(2, N)
        y = get_root_one(x, k, N)
    p = fractions.gcd(y-1, N)
    q = N // p
    return (p, q)

This algorithm runs in probabilistic polynomial time (ZPP). For example,
the probability of this algorithm succeeding after 14 iterations or less
is larger than $99.99\%$. Computing $k$ is $O((\lg N)^2)$, the
probabilistic portion is $O((\lg N)^3)$, and the euclidean algorithm to
compute the greatest common divisor is $O((\lg N)^3)$ as well.
Therefore, the entire algorithm will run in (probabilistic)
$O((\lg N)^3)$ time.

Finally, here is an example of running this algorithm to factor an RSA
modulus:

# A 98 and 99 bit prime.
p = 633825300114114700748351602573
q = 316912650057057350374175800819
N = p*q

print("RSA Modulus (p,q, N):")
print((p, q, N))

# A valid keypair mod N
e = 262139
d = 9451846527955896036458759652560972624637617897909079398699

print("Factoring N...")
print(rsa.factor_rsa(e, d, N))

This runs quite quickly, and demonstrates the algorithm does correctly
factor N. Note that the order of the factors changes from run to run,
depending on which root is found first. The order of the two factors
does not matter, though, so this is algorithm is sufficient for the
purposes of attacking a shared modulus cryptosystem.

To return to the original problem, if Bob shares his first private key,
and all his keys share a modulus, then Mallory can factor the modulus
using this algorithm. Once
the modulus is factored, she can compute $\phi(N)=(p-1)(q-1)$. With
knowledge of $\phi(N)$, computing the modular multiplicative inverse of
the other public keys (i.e. the corresponding private keys) is a simple
application of the extended euclidean algorithm.


Is this the mathematical equation for the Vigenere Cipher Is this the mathematical equation for the Vigenere Cipher or something else and if something else what is it?

Where t is the letter of plain text and n is the position of t within the text and c is the ciphered character.

For 't' and 'c' taking a as 1 and z as 26.

((t + n) > 25 -> c = (t + n) - 25) ^ ((t + n) <= 25 -> c = (t + n))

NO, the question does not contain the mathematical equation for the Vigenere Cipher with plaintext t and ciphertext c in thet set $\{1\dots 26\}$ (with the letter a as 1 and the letter z as 26), and displacement (or key) n, for two reasons:

the best interpretation I can make of the expression given is by considering -> to be the $\implies$ mathematical symbol, and ^ to mean logical XOR (or perhaps logical OR), that is one of the left thing or the right thing holds (possible meanings of the word one are equivalent in the context); but even with these assumptions, for n of 1 (meaning next character, circularly) the expression given maps the plaintext y (coded by t of 25) to the ciphertext a (coded by c of 1) instead of the desired z (coded 26);
the expression given does not parse (to me) as a mathematical equation.

With the original formalism, the Vigenere Cipher with plaintext t and ciphertext c in $\{1\dots 26\}$, and displacement n in the set $\{0\dots 26\}$, a correct expression would be:

((t + n) > 26 -> c = (t + n) - 26) ^ ((t + n) <= 26 -> c = (t + n))

and a passable mathematical equation would be:
$$t\mapsto c=((t+n+25)\bmod 26)+1$$

If we use the set $\{0\dots 25\}$ for plaintext and ciphertext, we get the nicer
$$t\mapsto c=(t+n)\bmod 26$$

or in the original formalism the expression

((t + n) > 25 -> c = (t + n) - 26) ^ ((t + n) <= 25 -> c = (t + n))


Are TLS 1.2 AES-CBC and AES-GCM Authenticated Encryption ciphersuites? In the answer of the following post: Why was AES CBC removed in TLS 1.3?, I quote the following from the chosen answer:

  After the Lucky13 attack (a timing oracle caused by MAC-then-encrypt),
  it was thought that TLS should change ordering of the operations.
  Changing order of the operations would have affected the backwards
  compatibility with previous implementations so it was after all
  thought that it is more practical to switch to authenticated
  encryption only.

In the answer, it is assumed that AES-CBC in TLS 1.2 is not Authenticated Encryption (reference to the last part of the quote: it is more practical to switch to authenticated encryption only.

My questions:

When can I consider a ciphersuite an Authenticated Encryption?
Is AES-CBC in TLS 1.2 an Authenticated Encryption (it uses MAC-then-Encrypt construction).
Do padding attacks in AES-CBC render it considered non-Authenticated Encryption cipher?

When can I consider a ciphersuite an Authenticated Encryption?

To cite from Wikipedia: Authenticated Encryption:

  Authenticated encryption  ... is a form of encryption which simultaneously provides confidentiality, integrity, and authenticity assurances on the data.

Note the focus on simultaneously.

  Is AES-CBC in TLS 1.2 an Authenticated Encryption (it uses MAC-then-Encrypt construction).

Since the authentication tag in the form of MAC is added before and not during encryption it can not be considered authenticated encryption. This allows the padding oracle attacks because this means that the authentication tag can only be verified after decryption.


In which public key encryption algorithms are the private and public key not reversible? The RSA public key encryption system has the characteristic that the public key and the private key can be reversed. That is, information encrypted with the public key can be decrypted with the private key, but the keys are themselves symmetric, such that it's also possible to use them the other way around and information encrypted with the private key can be decrypted with the public key.

This is not inherent with public key cryptography, however. The  Paillier cryptosystem, for example, does not have this feature: the private key cannot be used to encrypt data that can then be decrypted with the public key.

Are there other public key systems that do not have this property?

Are there other public key systems that do not have this property?

A more cogent question might be "are there any public key systems other than RSA that does have this property?"

In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public and private keys, and you eschew the CRT optimization on the private key side).

I'm familiar with a number of proposed public key systems, and nothing comes to mind:

Other factoring-based systems: Rabin-Miller and Pallier - nope; although Rabin does come close, but with a fixed public exponent of 2, it can't really be used as a private exponent (and it's not quite reversible either).
Discrete log; nope.  They (in my experience) have a private key as an integer $e$ and a public key as the value $g^e$ (or $eG$, if you're using a group with additive notation).  Given that you can compute the public key from the private one, you can't swap them and remain secure.
Lattice based systems; nope.  They internally have more variants than the discrete log problems, however in general, the private key is some secret sauce that makes solving the lattice problem easy (at least in the cases that the system cares about), hence you can't swap them.
Code based systems; nope.  The private key is the secret sauce to make the error correction problem easy, hence you can't swap them.
Multivariate systems; nope.  The private key is the secret sauce to make solving the multivariate equations easy, hence you can't swap them.
Isogeny based systems; nope.  The private key in this case is a subgroup of the elliptic curve, while the public key is the isogenous elliptic curve that the isogeny maps the curve into (while mapping the subgroup to the neutral element).  Again, it doesn't make any sense to swap them.
Hash based signatures; nope.  In this case, the public key is a hash, while the private key is the series of values that are hashed together (generally in a big tree structure) to ultimately form the hash.  It makes no sense to swap the public and private keys.

I can't think of any other public key systems that haven't been broken...


Isn't the use of public key encryption a redundant step in Encrypting File System, which doesn't improve the security of the File Encryption Key? With EFS, we know that a symmetric key, File Encryption Key (FEK), is used for encrypting files. The FEK is then protected by encrypting it with the public key of the user that can be recovered by decrypting with their corresponding private key.
The private key is again encrypted with the user's log-in password. My argument is, if the FEK is ultimately being protected using the user's log-in password, then the use of public key encryption is a redundant step which doesn't improve the security of the File Encryption Key (FEK) at all. Am I right or I'm missing a point?

[Or] I'm missing a point?

Actually there are at least two reasons why you would want to involve public:

First using public key allows you to rather precisely map permissions into keys. So suppose you create a file, how do you get the new file key to everyone who should have access to it? Public key encryption solves this readily. Or suppose you remove access to a file for somebody, you obviously need to pick a new file encryption key, so that that person doesn't have access anymore even if they accessed in the past. How do you communicate the new key? Public key encryption.

Second reason is mostly historic. EFS was mostly designed for corporations and governmental use. They already had smart cards deployed or saw the obvious usefulness of smart cards. But these smart cards typically don't support symmetric key encryption, but only public key encryption, so if you wanted to integrate smart card based authentication into the process, you'd have to involve public key encryption at some point.


RSA PSS security advantage To my humble opinion, please correct me if I'm wrong, RSA-PSS (PKCS#1 ver 2.1) advantage over RSA as described in PKCS#1 ver. 1.5 is in its security proofs. Does this proof and the advantage is still there even if the "salt" in the RSA-PSS scheme is constant over all messages, or it conditioned in generating a random salt each and every signature? That is, does the security proof of RSA-PSS assumes random salt over messages?

Even if we make RSASSA-PSS deterministic by fixing its seed, it remains with a security proof in the Random Oracle Model per Full Domain Hashing (Jean-Sébastien Coron, On the Exact Security of Full Domain Hashing, in proceedings of Crypto 2000). We can't say the same for RSASSA-PKCS1-v1_5, because a lot of the message representative is fixed.

In practice, a better argument to use deterministic RSASSA-PSS rather than RSASSA-PKCS1-v1_5 is that vulnerable implementations of verification of RSASSA-PKCS1-v1_5 abound, when I know no vulnerable implementation of RSASSA-PSS verification (regardless of randomization), and this is less likely to happen accidentally.

However a practical argument against RSASSA-PSS is that it requires careful specification of the hash and the mask generation function: even if the later is almost universally MGF1, that could be with another hash (e.g. stuck to SHA-1) depending on implementations.


Attribute-based broadcast encryption with respect to ABE What is the exact difference between attribute-based encryption (ABE) and attribute-based broadcast encryption (ABBE)?
Is ABBE equivalent to broadcast encryption on top of ABE?

At first, the abbreviation “ABBE” is used by Zhou et al. in [2] as a name for his ABE scheme. Zhou builds on top of a CP-ABE scheme which in addition supports “constant” ciphertexts (named CCP-ABE). From this perspective ABBE is a specific ABE scheme based on CP-ABE supporting constant ciphertexts.

However, in a more general way, I see ABE in the context of Broadcast communication as:

A merge ofthe notion of ABE and Broadcast Encryption. Broadcast related use-cases have special requirements which you have to take into consideration not only when applying ABE.

There are broadcast-enabled ABE schemes which build on top of KP-ABE[1,3] or CP-ABE[1,2,2a]. More or less broadcast-enabled ABE schemes face the same challanges and thus focus on similar properties/aspects.

Some often recurring aspects in ABE-based broadcast scenarios are:

Size of the ciphertext: a constant message size is often advantage. In addition the message size itself is of interest.
Access Structure: The ciphertext size depends on the embedded access structure. The access structure is important not only when thinking about how to enforce revocation.
General communication and storage overheads are more of importance in Broadcast scenarios - compare [2a].

[1] Attrapadung et al., 2009: Conjunctive Broadcast and Attribute-Based Encryption.

[2] Zhou et al., 2010:  On Efficient Ciphertext-Policy Attribute Based Encryption and Broadcast Encryption, Source: http://eprint.iacr.org/2010/395

[2a] Zhou et al.2015: Efficient Privacy-Preserving Ciphertext-Policy Attribute Based Encryption and Broadcast Encryption

[3] Sun et al., 2013: A Key-Policy Attribute-based Broadcast Encryption.


How (generally) do modern schemes deal with an adversary with the capacity to either instantly, or over time, corrupt a majority of parties I'm curious about the honest minority case and what cryptographers have and are currently using to get around this. My motivation is primarily the MPC space, but I'm sure there are other subfields that encounter it.
Some thoughts of mine include:

It seems that a high threshold Shamir Secret Sharing Scheme or just a vanilla additive sharing scheme would be required to operate on inputs while protecting privacy in a dishonest majority setting, however this does nothing to mitigate the fact that the adversary could easily compromise correctness.
I know SPDZ technically handles the dishonest majority case, my limited understanding of SPDZ is that they basically MAC everything and anything to accomplish this, but their approach also only provides safety from prying eyes and not any kind of probabilistic or computational guarantee of correctness.

I'm curious, is there some impossibility result in this area that I am just not aware of? It feels like there ought to be, because an adversary with that kind of control should be able to change the inputs of her puppets to compromise the output. Maybe if we limit the adversary to corrupting parties until after their inputs are initially submitted/distribute/broadcast we can say something of value?

There is a model, typically called proactive security (and sometimes also called a mobile adversary), that considers the case that parties can be corrupted and later uncorrupted. Time is divided into epochs and security holds as long as the appropriate threshold of parties is honest in each epoch. In the dishonest majority case, this means that unless all of the parties are corrupted in a single epoch, security is preserved. These protocols work by rerandomizing secret sharing and enforcing correctness.


Non-Degeneracy of the Weil pairing In this YouTube video, Dan Boneh mentions that if both points are defined on the base field then the pairing is degenerate.

Why is that? And specifically is this true if I use the Weil Pairing?

(I write a more extensive answer with the background of all this; the result you are looking for is Theorem 3. A proof would be too long for this site, you can consult standard textbooks.)

Let $E$ be an elliptic curve over $\mathbf{F}_p$ and $P \in E(\mathbf{F}_p)$ be a point of prime order $r \ne p$. So $r$ divides the order of $E(\mathbf{F}_p)$, and suppose further that $r^2$ does not divide the order of $E(\mathbf{F}_p)$. For any extension field $K$ of $\mathbf{F}_p$, we let $E(K)[r]$ be the group of all points $Q \in E(K)$ such that $rQ = \infty$. Note that $P \in E(K)[r]$, so $\langle P\rangle$ is a subgroup of $E(K)[r]$.

Theorem 1. The group $E(\overline{\mathbf{F}_p})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

Corollary. There is an integer $k > 1$ such that $E(\mathbf{F}_{p^k})[r]$ is isomorphic to $\mathbf{Z}_r \oplus \mathbf{Z}_r$.

In the following, we let $k$ be the smallest such integer (called the embedding degree), $K = \mathbf{F}_{p^k}$, and $E[r] = E(K)[r]$. Thus all the points of $E[r]$ have coordinates in $K$.

Then the mathematician's Weil pairing $e_r$ is a map from $E[r] \oplus E[r]$ to $\mathbf{F}_{p^k}^*$ with the following properties (among others), which makes it different from the cryptographer's pairing.

Bilinearity. For all points $P,Q,R \in E[r]$ we have
$$
\begin{align*}
e_r(P+Q,R) &= e_r(P,R)\times e_r(Q,R), \text{and} \\
e_r(P,Q+R) &= e_r(P,Q)\times e_r(P,R).
\end{align*}
$$

Alternacy. For all points $P \in E[r]$, we have $e_r(P,P) = 1$.

Non-degeneracy. For all points $P \in E[r]$, if $e_r(P,Q) = 1$ for all points $Q \in E[r]$, then $P = \infty$.

The property of alternacy of the Weil pairing makes it unsuitable for cryptography, since in cryptography we require $e(P,P) \ne 1$. So the Weil pairing needs to be modified.

Theorem 3. Let $P,Q \in E[r]$. Then $e_r(P,Q) = 1$ if and only if $Q$ is a multiple of $P$.

Corollary 1. A point $Q \in E[r]$ has coordinates in $\mathbf{F}_p$ if and only if it is a multiple of $P$.

Corollary 2. The group of $r$th roots of unity in $K$ is cyclic of order $r$.

In the following, let $Q$ be a point of $E[r]$ which is not a multiple of $P$. This implies that $Q$ (which has coordinates in $\mathbf{F}_{p^k}$) does not have coordinates in $\mathbf{F}_p$. Let $G = \langle P\rangle$, and let $G_T$ be the group of $r$th roots of unity in $K$ (both groups are cyclic of order $r$).

We define the modified Weil pairing $\hat{e}_r$ as a map from $G \times G$ to $G_T$ such that $\hat{e}_r(P,P) = e_r(P,Q)$. Then $\hat{e}_r$ is a suitable cryptographic pairing: its bilinearity follows from the bilinearity of $e_r$, and its non-degeneracy (in the cryptographic sense) follows from Theorem 3 since $Q$ is not a multiple of $P$.

There are many ways to do this in practice, one is to let $p \equiv 2 \pmod 3$ and such that $(p+1)/6$ is prime. In this case the curve $Y^2 = X^3 + 1$ has $p+1$ points (it is supersingular) and we can choose a point of order $r = (p+1)/6$. It can also be shown that in this case, we have $k = 2$. Since $p^2-1$ is a multiple of $3$, there is a primitive $3$rd root of unity in $K = \mathbf{F}_{p^2}$, call it $\zeta$. Then for a point $P = (x,y)$, the point $Q$ is $(\zeta x, y)$.


Would it be secure to use random numbers from random.org in a cryptographic solution? Random.org provides true random numbers through an unsecured web service. Since these numbers would be transmitted in plaintext could they still be considered useful as true random numbers while maintaining security in a cryptographic solution?

At first I was thinking if a large pool of them was obtained then a small subset of them could be used randomly to make the fact they are known of less use. Then I realized that no matter how many random numbers were obtained this way, it would still be a smaller number set to explore in attempting to crack the cryptography.

Update: Random.org supports SSL over HTTPS, but are not encouraged for use in cryptography.

The more I think about it, the less I would be willing to use Random.org for any sort of cryptographic application. My reasons are listed below.

See Q2.2, the groups listed are not cryptographic groups and potentially (or probably) don't have cryptographers on their evaluation teams
They specifically say not to use it for cryptography
It is closed source. So, I would have no way of knowing if they properly mutex their RNG so that only one person is drawing from it at a time. There are other implementation issues that I (or someone/some group much smarter than I could check for).
Using this would require an internet connection for all randomness.
Current CS-PRNGs are much faster and options are available which suffer from none of the weaknesses listed above.
The RNG could change at any time without me knowing.

That said, these reasons don't necessarily answer the question. They only give insight as to why I personally wouldn't use Random.org for cryptography. Would it be secure to use Random.org in  cryptographic solution? Possibly. There really isn't enough information to really know.


How to recover small messages from textbook RSA? In the answer to the question Random unique key per message, safe to use key as IV? it was claimed that one can recover a random 128-bit textbook-RSA encrypted value using about $2^{64}$ steps.

How and why does this attack work?

Disclaimer: I did not come up originally with this attack, but rather it was first described in "Why Textbook ElGamal and RSA Encryption
Are Insecure" by Boneh, Joux and Nguyen (PDF).

This answer will give a summary of the attack, similar to what is documented in Introduction to Modern Cryptography by Katz and Lindell.

First for the actual attack:
Let $c=m^e\bmod N$ be given as well as $(N,e)$ and let $m<2^l$ for some $l\in\mathbb N$. Then there exists $m=r\cdot s$ with $r,s<2^{\alpha\cdot l}$ for some $1/2<\alpha<1$ with decent probability:

Set $T:=2^{\alpha\cdot l}$.
For all $r$ from $1$ to $T$ compute and store $x_i=r^e\bmod N$.
Sort the pairs $(r,x_i)$ by the second component.
For all $s$ from $1$ to $T$ check (e.g. using binary search) whether $c\cdot s^{-e}\bmod N=x_i$ for some $i$, if so return $r\cdot s \bmod N$ as the message $m$.

(If $s^{-e}$ cannot be computed, then $s$ shares a non-trivial common divisor with $N$, and so one can trivially factor $N$ by calculating $\gcd(s,N)$.)

Now for the run-time of this algorithm:
One needs about $2^{\alpha\cdot l}$ modular exponentiations for step 2, $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step three and about $\mathcal O(l\cdot 2^{\alpha\cdot l})$ for step four. So overall one does get away with "little more" than $2^{\alpha\cdot l}$ steps. Given that there's at least some chance (a few percent) that $\alpha=1/2$ will work, this would result in an attack with about $2^{l/2}$ run-time.

Note that steps 1 to 3 above don't depend on the ciphertext $c$, so they can be done in advance, and the resulting table reused for several ciphertext.

As for why this attack works, note that we effectively brute-force factor the message by exploiting the homomorphic property of RSA and that $c=m^e=(rs)^e=r^es^e\bmod N$.


Converting raw ECC private key into ASN.1 DER encoded key I created a random integer array of 32 bytes to use as my private key for secp256k1 curve.

const uint8_t secret[] = {0xb2,0x9a,0xc6,0xbd,0xc7,0x3d,0xc4,0xe1,
                          0x85,0xa7,0x3c,0x96,0xf8,0x1c,0x58,0x43,
                          0xe2,0xbf,0x2d,0x68,0xe5,0x6f,0xf6,0xae,
                          0x4f,0xe7,0x51,0xcd,0x9d,0x47,0x00,0xfa}

I want to turn this hex array into a ASN.1 DER encoded key so I can further use it with my hardware which expects the keys to be ASN.1 DER encoded.

Can you point me in the right direction on how to achieve this ?

Edit , I found an encoded key-pair, maybe I can pick up from this. Does the array below contain both public and private key parts ?

 keyPairData[] = { 0x30, 0x81, 0x87, 0x02, 0x01, 0x00, 0x30, 0x13,
    0x06, 0x07, 0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x02,
    0x01, 0x06, 0x08, 0x2A, 0x86, 0x48, 0xCE, 0x3D,
    0x03, 0x01, 0x07, 0x04, 0x6D, 0x30, 0x6B, 0x02,
    0x01, 0x01, 0x04, 0x20, 0x78, 0xE5, 0x20, 0x6A,
    0x08, 0xED, 0xD2, 0x52, 0x36, 0x33, 0x8A, 0x24,
    0x84, 0xE4, 0x2F, 0x1F, 0x7D, 0x1F, 0x6D, 0x94,
    0x37, 0xA9, 0x95, 0x86, 0xDA, 0xFC, 0xD2, 0x23,
    0x6F, 0xA2, 0x87, 0x35, 0xA1, 0x44, 0x03, 0x42,
    0x00, 0x04, 0xED, 0xA7, 0xE9, 0x0B, 0xF9, 0x20,
    0xCF, 0xFB, 0x9D, 0xF6, 0xDB, 0xCE, 0xF7, 0x20,
    0xE1, 0x23, 0x8B, 0x3C, 0xEE, 0x84, 0x86, 0xD2,
    0x50, 0xE4, 0xDF, 0x30, 0x11, 0x50, 0x1A, 0x15,
    0x08, 0xA6, 0x2E, 0xD7, 0x49, 0x52, 0x78, 0x63,
    0x6E, 0x61, 0xE8, 0x5F, 0xED, 0xB0, 0x6D, 0x87,
    0x92, 0x0A, 0x04, 0x19, 0x14, 0xFE, 0x76, 0x63,
    0x55, 0xDF, 0xBD, 0x68, 0x61, 0x59, 0x31, 0x8E,
    0x68, 0x7C };

ASN.1 is a way of defining structures for data, and DER is a binary encoding of those structures. But they aren't describing any structures by themselves. Saying that something needs to be ASN.1 / DER encoded is like saying that the key needs to be represented in XML without specifying the tags or tree structure.

What you are required to generate is a PKCS#8 (inner) encoded private key. The SEC1 document link that I provided before defines the inner SEQUENCE in there. The PKCS#8 inner structure is used to identify the type of key. Most of what is in SEC1 was copied to X9.62. And yes, it clearly contains the optional public key. If you look for ways to encode your private key to PKCS#8 you'll find a lot more information. It's for instance the default encoding for OpenSSL, but most other libraries will use the same.

I can generate the same in Java (ECPrivateKey.getEncoded() for curve "secp256k1") but without the optional - and in my opinion spurious - public point included. You can see the structure you've provided in the Lapo online ASN.1 decoder. Yes, it clearly includes the public key as optional BIT STRING at the end (appending it yourself means adjusting the length encodings of the SEQUENCE's though).

If your structure lacks a public key, I would first just try and import it; it's pretty easy to compute the public key from the private key and parameters: just point multiplication with the base point G. Likely the device is capable of doing that.

You will generally want to create a "named" curve where the domain parameters are given by an OID (as in the example you've been given). It is more likely that explicit domain parameters are rejected by devices that only operate on a limited set of curves.

I've however encountered HSM's that require you to provide the unnamed parameters. In that case you may need to construct your private key using the explicit parameters and then encode...


Communication Complexity of Equality comparison (Catrina and de Hoogh) I was reading secure MPC protocol for finding a secret representation of whether a secret value equals zero, from Catrina and de Hoogh (summarized here).

In the paper, the communication complexity costs are measured in terms of "invocations of a primitive in which every party sends a share ... to the others" (page 3). The paper shows a way to do equality-to-zero testing in a constant number of rounds. This seems to require the following costs:

Generating a secret random number r, as well as secret representations of its lower $k$ bits by calling PRandM (Protocol 3.7, step 1). This requires $k$ invocations (see Table 1).
Making a secret value public. (Protocol 3.7, step 2). This requires $1$ invocation.
Generate a public product of two secret numbers by calling MulPub. This is done $2k$ times. (Protocol 4.2, steps 4 and 9) This requires $2k$ invocations.
Generate a secret product of two secret numbers. This is done $k-1$ times. (Protocol 4.2, step 5) and requires $k-1$ invocations.

(I am assuming Protocol 4.2 is how KOr from Protocol 3.7 is implemented.)

What does an invocation mean? Does it mean $O(n^2)$ data complexity? Does this mean the total communication complexity is something like $O(kn^2)$?

The SPDZ protocol, shows that the multiplication of secret values to generate a secret value (Cost #4) can be moved to a pre-processing phase by generating Mulitplicative Triples. Can Costs #1 and #3 also be moved to a pre-processing phase?

I was pointed to Catrina and de Hoogh here as an implementation of secure equality-to-zero test that can be used in a SPDZ-like environment. By SPDZ-like environment I mean each secret number $a$ is represented by each party having a 'share' of that number $a_i$, such that $\sum a_i = a (\mod p)$ for some large prime (or exponent of a prime) $p$. Is Catrina and de Hoogh the most computationally efficient constant-round protocol currently out there that does a secure equals-zero test of a secret value to generate a secret result?

What does an invocation mean?

The communication cost of opening 1 secret-shared field element.

Since the protocols of Catrina and de Hoogh are mostly independent of the underlying MPC protocol, this cost can vary. In SPDZ, for example, the trivial opening algorithm requires $O(n^2)$ field elements to be sent across the network in all, but it can also be done in $O(n)$ (see p25).

  Can Costs #1 and #3 also be moved to a pre-processing phase?

Step 1 just generates random bits, so can be done as preprocessing. Step 3 consists of two parts: the first (line 4 of Protocol 4.2 in the paper) can be preprocessed, while the second (line 9) depends on the inputs, $[a_i]$, so must be done online.

  Is Catrina and de Hoogh the most computationally efficient constant-round protocol currently out there that does a secure equals-zero test of a secret value to generate a secret result?

There's a paper by Lipmaa and Toft with a constant-round equality test with less communication than Catrina and de Hoogh's. However, it has higher local computation costs. I don't know of a computationally more efficient protocol.


Is the logic for how the enigma machine worked documented somewhere? I know that there is a formula to calculate the result of any input but is the logic of how the machine actually worked documented?

I have seen schematics for the circuitry and even a how to make your own at home site.  But has the logic been broken down?  Is there source for a virtua Enigma Machine that works by replicating the logic of the machine instead of just using the math?

Is the logic for how the enigma machine worked documented somewhere?

Yes!

If you're really interested in "diving in deeper" (pun intented), I would like to advise you to check out:

"The Cryptographic Mathematics of Enigma"
Dr. A. Ray Miller
NSA. Center for Cryptologic History. USA. 1996. 3rd edition 2002
"Funkpeilung als alliierte Waffe gegen Deutsche U-Boote 1939-1945."
Arthur Bauer
ISBN: 3-00-002142-6. The Netherlands, 1997. German. p. 33.


Fixed primes in discrete logarithm The discrete logarithm problem is to find $z$ when the inputs are $g,h,p$ where $g^z\bmod p$.

Supposing if you fix $p$ then does the problem become any easier to attacks and is there a $(\log p)^c$ complexity algorithm?

The best algorithm for computing discrete logarithms are based on families and variations of methods known as "number field sieve" and "function field sieve". They all share a common structure. In particular, they are divided in several phases, only the last of which depends on the value whose discrete logarithm must be computed: all the previous steps require only the order of the field.

I did some research. I do not know about the computational complexity of each step, this would involve some more research but can probably be found in some of the articles and surveys of Antoine Joux. However, I'll focus on the case which seems to be your target: discrete logarithm in prime order field. For that case, the actual record is a discrete log in a field of order $p$, with $bitsize(p) = 530$. You'll find Here the report on this record. The computation is divided in five phases: polynomial selection, sieving, filtering, linear algebra, and actual computation of the discrete logarithm. Among them, the sieving is by far the dominant cost: the report indicates it took approximately 50 core-years on a 2-GHz Intel E5-2650. This phase depends only on the order $p$ of the field. The report mention that once the four first phases have been performed, "Computing one individual logarithm required a few hours". Therefore, Compared to the overall time, computing discrete logarithms is extremely fast once the precomputation has been made (with the order of the field only).

Although I do not know the theoretical complexity of this last step, I'm pretty sure that this is still not polynomial time (id est, $O(\log^c p)$ for some $c$), even if it is only a negligible cost in the total computation.


Cracking RSA with small plaintext I read a CTF writeup about cracking 4 primes RSA numbers from here:
Given $p, q, r,$ and $p+q+r$ are prime numbers.

The challenge encrypts the flag with a modulus $N=(p∗q∗r)∗(p+q+r)$
and gives the output $n=pqr, k=p+q+r$. To totally break the
cryptosystem, we would want to find the totient of the modulus
$\varphi(N)=(p−1)(q−1)(r−1)(p+q+r−1)$
but we can simplify this when the encrypted message $m$ is small enough.
If we have $m<k$, we can instead find $\varphi(k)=k−1$, and find $e^{-1}\bmod{\varphi(k)}$, and
solve!

But how can they replace $p*q*r*(p+q+r)$ with only $(p+q+r)$ and somebody explains that part?

We have given $c = m^{17} \bmod (N=pqrk)$ with $k = p+q+r$
We can write this as $$m^{17} =  c + \ell (pqr)k$$ for some integer $\ell$.
Now consider this as $$m^{17} =  c + (\ell pqr)k$$
if $m < k$ you can find the $m$ if not information is lost and the answer is not unique.


Reference for the Tortoise and Hare algorithm by Floyd? Can someone please point me to a book or paper that describes the Tortoise and Hare algorithm by Floyd?

I know there are ample websites out there, but for reference purposes, I need a book or paper to point to.

Quoting Wikipedia:

  The algorithm is named after Robert W. Floyd, who was credited with
  its invention by Donald Knuth.3[4] However, the algorithm does not
  appear in Floyd's published work, and this may be a misattribution:
  Floyd describes algorithms for listing all simple cycles in a directed
  graph in a 1967 paper,[5] but this paper does not describe the
  cycle-finding problem in functional graphs that is the subject of this
  article. In fact, Knuth's statement (in 1969), attributing it to
  Floyd, without citation, is the first known appearance in print, and
  it thus may be a folk theorem, not attributable to a single
  individual.[6]

Now looking up reference [4], yields the Handbook of Applied Cryptography, which indeed contains a description as Note 3.8 (PDF version). However the Handbook also attributes the algorithm to Knuth as Wikipedia does, so

  Knuth, Donald E. (1969), The Art of Computer Programming, vol. II:
  Seminumerical Algorithms, Addison-Wesley, p. 7, exercise 6

is the reference you are looking for with the Handbook citing it as (PDF, reference 692)

  D.E.Knuth , The Art of Computer Programming – Seminumerical
  Algorithms, volume 2, Addison-Wesley, Reading, Massachusetts, 2nd
  edition, 1981


(Whitebox Crypto) Using ChaCha20, is it safe to reduce the nonce length in a single block cipher? I am willing to write a Whitebox Crypto unit using ChaCha20 algorithm (Bernstein, D. 2008) for an input consisting of a single block. The fact it is going to be a single block cipher is of special importance here, as otherwise, the simple algorithm below wouldn't apply.

The principle is quite simple and reuses some logic from Chow et al: transform all inner block (formed by a series of 8 quarterround() functions looped 10 times) into a lookup table that takes the nonce as input. Notice that here, again, I am not considering more than one block of input, otherwise what I am proposing here wouldn't make sense, as a second round of the algorithm would have different x[0]..x[3].

In other terms, this is what I am trying to do. As in RFC 7539, instead of:

      chacha20_block(key, counter, nonce):
         state = constants | key | counter | nonce
         working_state = state
         for i=1 upto 10
            inner_block(working_state)
            end
         state += working_state
         return state
         end

I am willing to do something like:

      chacha20_1st_block(nonce):
         return lookup_tables(nonce)
         end

precomputing lookup tables where the counter is always 0 (or any other constant), and dimensioning the nonce such as the table size doesn't get too long, complementing the other bits with zero. For instance, if we consider nonces consisting of 13 bits, it is possible to generate 8192 tables containing 16 words of 32 bits, or exactly 512kB. Other sizes may be obtained by adjusting the nonce size.

I'm afraid I am making obvious questions here, but:

Am I considerably reducing the complexity of finding the original key this way?
Am I increasing attack chances?

EDIT 1:
I left an implementation of the algorithm above in https://github.com/balena/chacha20-whitebox.

Am I considerably reducing the complexity of finding the original key this way?

No. If key was only used as input of chacha20_block(key, counter=0, nonce) when preparing the lookup_tables, then finding the original key is demonstrably at least as hard as breaking chacha20 (the algorithm) in its intended usage.

  Am I increasing attack chances?

Depends comparing to what, and under what threat model. Most obvious issue: the nonce becomes predictable with sizable probability.

  I'm looking for ways to increase the nonce length without exploding the memory size.

If we stick to producing the same results as chacha20_block(key, counter=0, nonce), modeling that only as a strong PRF of nonce, then demonstrably memory size in bits is at least: number of possible nonces × output width in bits.

On the other hand, it is possible to increase the nonce length. One trivial way is to have a normal-width nonce with only the low-order bits changing.

With some increase in memory, it is possible to use arbitrary and normal-width nounces, and even to hide their value until use: in the black box store F(nounce) where F is a public PRF such that collision among actually used nounces does not occur (either make F wide enough to have little collisions for random nounces, or restrict actually used nounces to avoid collision); and at each use compute F(nounce) and use the output to decide which tabulated value should be output.

Note: I'm not seeing the whole thing as true white box cryptography, because the would-be box is so severely limited in what it can compute. It is more like a One Time Pad with true randomness replaced by strong-pseudo randomness generated by a cryptographically strong PRNG which key is known to only one side. I see nothing this can achieve that plain symmetric crypto with diversified keys does not also achieve, with the later having the advatage of not requiring massive storage.