Is this problem on $\mathbb{Z}_p$ really hard? I just want to know if there's something obvious that renders this hard problem useless. Not a full cryptoanalisys. Any hint on whatever is welcomed.

We will work with the Ring $\mathbb{Z}_{p}$, $p$ prime.

Now, we define a function $f:\mathbb{Z}_{p}\times\mathbb{Z}_{p}\mapsto\mathbb{Z}_{p}$,
as $f\left(a,b\right)=\frac{-a\,b+a+b+z}{a+b-1}$, $z\in\mathbb{Z}_{p}$, $z$ is a public constant value.

Next, we define a series as follows:

$a,b\in\mathbb{Z}_{p},\ s_{0}=a,\ s_{1}=b,\ s_{n}=f\left(s_{n-2},\ s_{n-1}\right)$

And for a given element of the series, $s_{n}$, a value $r_{n}=f\left(s_{n},a\right)$

The question is, taking into account that the function $f$ is not
associative, how difficult is, knowing $b$ and $r_{n}$, recover
the value of a secret $a$. As an example of sizes let's say $n=256,\ p\sim2^{256}$.

This problem leads to a public key cryptosystem described here:

https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv

Daniel Nager - daniel.nager@gmail.com

TL;DR: No, that problem is not hard.

Synopsis: After remapping of $\Bbb Z_p$ by an involution $x\to\overline x$, the function $(x,y)\to\overline{-f(\overline x,\overline y)}$ is mostly associative. We massage it into an Abelian finite group $(\mathcal S,\boxplus)$. This makes $\overline{r_n}$ a linear function of $\overline a$ and $\overline b$ with known scalar coefficients, allowing to efficiently solve the question's problem.

Define $\delta$ and $\hat z$ in $\Bbb Z_p$ with $\delta=(p+1)/2$ and $\hat z=(-3\,\delta^2-z)\bmod p$. The reason will become apparent later, for now consider $\hat z$ as an arbitrary fixed public element of $\Bbb Z_p$.

Define $l$ as the Legendre symbol $l=\displaystyle\biggl(\frac{\hat z}p\biggr)$, and define $m=p-l$.

When $l=+1$, define $\omega$ as a particular solution of $\omega^2=a$ in $\Bbb Z_p$, e.g. the odd one in range $[1,p)$.

Define the set $\mathcal S$ as:
$$\mathcal S=\begin{cases}
\{\infty\}\cup\Bbb Z_p&\text{when }l=-1\\
\{\infty\}\cup\Bbb Z_p-\{0\}&\text{when }l=0\\
\{\infty\}\cup\Bbb Z_p-\{\omega,p-\omega\}&\text{when }l=+1
\end{cases}$$

Define internal law $\boxplus$ in $\mathcal S$ as:
$$x\boxplus y=\begin{cases}
y&\text{when }x=\infty\\
x&\text{when }x\ne\infty\text{ and }y=\infty\\
\infty&\text{when }x\ne\infty\text{ and }y=-x\\
(x+y)^{-1}(x\,y+\hat z)&\text{otherwise}
\end{cases}$$

$(\mathcal S,\boxplus)$ is¹,²,⁶ a finite Abelian group of $m$ elements with neutral $\infty$. With the convention $-\infty=\infty$, the opposite $-x$ of $x$ in group $(\mathcal S,\boxplus)$ is² computed as in $(\Bbb Z_p,+)$ when $x\ne\infty$.

Define scalar multiplication $\boxtimes: \Bbb Z\times\mathcal S\mapsto \mathcal S$ as:
$$k\boxtimes x=\begin{cases}
\infty&\text{when }k=0\\
(-k)\boxtimes(-x)&\text{when }k<0\\
\bigl((k-1)\boxtimes x\bigr)\boxplus x&\text{otherwise}
\end{cases}$$
and for all $x$ in $\mathcal S$ and integers $k$, $k'$, it holds²:
$$\begin{align}
(k\boxtimes x)\,\boxplus\,(k'\boxtimes x)&=(k+k')\boxtimes x&\text{and}\\
k\boxtimes (k'\boxtimes x)&=(k\,k')\boxtimes x&\text{and}\\
k\boxtimes x&=(k\bmod m)\boxtimes x
\end{align}$$

For $x$ in $\{\infty\}\cup\Bbb Z_p$ define $\overline x=\begin{cases}
\infty&\text{when }x=\infty\\
\delta-x&\text{otherwise}\\
\end{cases}$.

Define $\hat{\mathcal S}$ as the set of $\overline x$ for all $x$ in $\mathcal S$. It holds $\hat{\mathcal S}=\mathcal S\iff l=-1$.

A function $f:\hat{\mathcal S}\times\hat{\mathcal S}\mapsto\hat{\mathcal S}$ compatible⁴ with the question's $f$ can²,⁵ now be defined as:
$$f(x,y)=\overline{-(\overline x\boxplus\overline y)}$$

The «restricted commutativity»³ property that $f\bigl(f(x,y),f(y',z)\bigr)=f\bigl(f(x,y'),f(y,z)\bigr)$ is a consequence of the associativity and commutativity of $\boxplus$ , and the fact for all $x$ in $\mathcal S$ it holds $\overline{(\overline x)}=x$.

Define:
$$\begin{align}
\hat s_0&=\overline a\\
\hat s_1&=\overline b\\
\hat s_n&=-(\hat s_{n-2}\boxplus\hat s_{n-1})\text{ when }n>1\\
\hat r_n&=-(\hat s_n\boxplus\hat s_0)\\
\end{align}$$
and for all $n$ it holds²: $\hat s_n=\overline{s_n}$ and $\hat r_n=\overline{r_n}$.

From this we can efficiently compute² integers $u_n$ and $v_n$ in $\Bbb Z_m$ such that:
$$\overline{r_n}=(u_n\boxtimes\overline a)\,\boxplus\,(v_n\boxtimes\overline b)$$

This allows² to solve for $a$ given $b$ and $r_n$, knowing parameters $p$, $z$, $n$. That's significantly easier than a discrete logarithm problem. When $\gcd(u_n,m)=1$, the unique solution is $$a=\overline{(u_n^{-1}\bmod m)\boxtimes(\overline{r_n}\,\boxplus\,(-v_n\boxtimes\overline b))}$$

Notes:

¹ : In particular, $\boxplus$ is² associative!

² : Proof is left as an exercise to the reader.

³ : See document linked in the question.

⁴ : When $l\ne-1$ one of the input of $f$ can be excluded from $S$; assimilate it to $\infty$.

⁵ : $\delta$ and $\hat z$ are chosen such that $\overline{(x+y-1)^{-1}(-x\,y+x+y+z)}=-(\overline x\boxplus\overline y)$.

⁶ : This group has been identified there, if not named.


Pseudorandom Generator Behavior Assume I have an encryption scheme $E(k,m) = (P(k,r), G(r) ⊕ m) $ and given that $G$ is a PRG , $P$ is a PRP and $r$ is a random n-bit nonce.

My question is:

  If I run this encryption twice with the same message but different r
  (due to nonce behavior), will I get the same c?

I know that PRG is deterministic, but in this case, the $r$ always changes.

Please help!

If I run this encryption twice with the same message but different $r$ (due to nonce behavior), will I get the same $c$?

No.

Lets split this question into the two elements of $c = (c_1, c_2)$ where $c_1 = P(k,r)$ and $c_2 = G(r) ⊕ m$. Then lets start with $c_2$ where the message is actually "encrypted".

A good PRF will return a stream of bits indistinguishable from random. It should be a different stream each time the seed is different. However, two random streams will still have approximately half the bits identical, purely because of chance.

So lets minimize the size of $m$ to a single bit, and set $m$ to zero. The resulting stream of bits may start with a zero or one for $r=x$ or $r=y$ with $x \neq y$ . Say that they both start with $0$ or $1$ then the result of $c_2 = G(r) ⊕ m$ will be $0$ or $1$ as well.

Of course the chance that $c_2=c_2'$ is reduced by 50% for each bit added to $m$. But $c_2$ can be identical for the right combination of nonces.

The fact that $c$ consists of the permuted nonce as well confuses the matter. The $c_1$ will always be different because $P(k, r)$ will always be different - it is a permutation after all. This has however nothing to do with the message $m$ or the security of the scheme.

However, it does mean that the only answer possible is no given your scheme; if $c_1$ is never the same then $c$ is obviously never the same as well, even though $c_2$ is not affected.

Note that $G(r)$ can only be secure if $r$ behaves as a secret, i.e. has enough entropy. The size of $r$ is maximized by the size of the PRP. Basically this scheme is a stream cipher if and only if $r$ contains enough entropy. In that case $P(k, r)$ will be a form of key wrapping.


Given $g,g^t$ in an RSA group modulo $N=pq$, is it hard to compute $g^{t^{-1}}$? Suppose we have an RSA groug $G=\mathbb{Z}^{*}_{N}$, where $N=pq$ , where $p,q$ are primes. Let $g$ be a random element of $G$ and $t\in \mathbb{Z}^{*}_{N}$. Having $g$ and $g^t$, it seems to be very hard to find $g^{t^{-1}}$, supposing discrete logarithm problem (DLP) is hard. My question is that is this really hard?

In a prime order group, let's say in $\mathbb{Z}^{*}_p$ , $g^{t^{-1}}$ = $g^{p-2}$ : here we don`t have to face DLP, so finding $g^{t^{-1}}$ is easy.

I know that I am not exactly answering your question, but I am pointing you in a potentially interesting research direction. Your question is not standard in the area of discrete log and Diffie-Hellman problems since you are considering a cyclic group of order $p\cdot q$ where $p$ and $q$ are primes. (Typically, we like looking at group of prime order.)

Your question is actually asking whether you can reduce this problem to solving the discrete log problem. I don't have any answer to that, but it reminds of an old paper by Biham, Boneh and Reingold that shows that the Diffie-Hellman problem modulo $N=pq$ (for Blum integers) is actually equivalent to factoring. This isn't the same thing, but there's something similar. The paper is here: https://omereingold.files.wordpress.com/2014/10/cgdh.pdf.


calculating a group element in a discrete log problem An encryption scheme is based on the DLP: $c = a^x mod ~b$, where $x$ is hard to find. How hard is it to find $a$, given all the other values, $c$, $x$ and $b$?

Would this make the problem easy to solve?

$c^{1/x} = (a^x)^{1/x} mod ~b$

An example would be great to better understand.

If you know the factorization of $b$, it's easy.  One way would be to compute $x^{-1}$, the multiplicative inverse modulo $\phi(b)$, and then compute $c^{x^{-1}} \bmod b$

If you don't know the factorization of $b$, it's hard; in fact, it's essentially the RSA problem.


What if AES-128 key / text length is more or less than 16 characters In this example ( https://kavaliro.com/wp-content/uploads/2014/03/AES.pdf ), the AES-128 key and text are 16 characters each, but how would this example be explained if the key or text was more/less than 16 characters? How would this change the procedure that creates the encrypted text?

AES is not a method of encrypting messages with passwords.  It is a pseudorandom permutation family, which is not designed to be used directly by applications.  Rather, a PRP is a very specific technical concept that cryptographers use to design methods of encrypting messages, called authenticated ciphers, like AES-GCM—and that cryptographers could use to derive keys from passwords, though usually we use other password-based key derivation functions like PBKDF2-SHA256 or scrypt or argon2id that don't involve AES.

For example, you could use scrypt to derive a 256-bit key $k$ from your password, and then encrypt your message $m$ using the authenticated cipher AES-GCM under the key $k$—or the even better authenticated cipher crypto_secretbox_xsalsa20poly1305 from NaCl which doesn't involve AES at all.

Don't use the letters A-E-S directly in your application; use an authenticated cipher.  The keywords above should lead you to plenty of followup reading material.


Vigenere ciphers : Need help for math analysis I've been learning about Vigenere ciphers and then thought of another method to Encrypt and decrypt that.

This's my method to encrypt :

I have a msg : "messages from father to his son"
I have a key : "home"
And the cipher text : "tsewmkwk fxse krhtjr mv lzl gvv"

I've created the Mathematics algorithm for the encryption, but get stuck for the decription.
This's what I've made fro encryption :

msg : "messages from father to his son"
key : "homemess ages fromfa th ert ohi"

So, I include the msg as part as the encryption method.
And,

my problem is :

How is mathematical/cryptanalysis method for implement this procedure below ?

msg : "tsewmkwk fxse krhtjr mv lzl gvv"
key : "homemess ages fromfa th ert ohi"
to get it back to "messages from father to his son" ?

May be somebody can help me, I'm not clever enough to make an equation.

EDIT :

As I know, the vigenere equation basically like this :

Ci = Ek(Mi) = (Mi + Ki) mod 26

with E is the encryption and K is the key for the Encryption. And you know that the decryption from that encryption is like this :

Mi = Dk(Ci) = (Ci - Ki) mod 26

right ?

Now, I recreate the encryption using this formula :

C_i=E_k (M_i )=(∑_(i=0)^k▒(M_i+K_i ) + ∑_(i=k+1)^m▒〖(M_i+K_i))〗 mod 26

But, that's my problem is you can see my stupidity to create the equation. But I can convert the equation to the programming but not the opposite. I want to make the equation for analysis report. May be this add the unclear problem, and please don't tell me how to encrypt or decrypt that. May be a point to the basic math can enlighten me a little.

Thanks...

First, you decrypt the first four characters. The plaintext you find is the key for the next block of four characters, so after this you can decrypt the next block, finding the key for the block after that, and so on.

This means you will need a case distinction: one case for the first $|K|$  characters (where $|\dots| \stackrel{\text{def}}{=} \text{the length of $\cdots$}$), and one case for the rest of the text. Mathematically, you could write this down as follows:

$$C_i = \begin{cases}i < |K| & M_i + K_i \pmod{26}\\
i \geq |K| & M_i + M_{i - |K|} \pmod{26}\end{cases}$$

For $i<|K|$ we take the standard Vigenère formula. For the rest, you take the ciphertext one keylength back as key. Note that my formula assumes you start with $i=0$; if you start with $i=1$ you'll need $\le$ and $>$ instead.

Then, decryption is done similarly:

$$M_i = \begin{cases}i < |K| & C_i - K_i \pmod{26}\\
i \geq |K| & C_i - M_{i - |K|} \pmod{26}\end{cases}$$


Timing attacks against RSA, DH and AES I have been reading about “Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension” by Wing H. Wong. I was wondering if this attack is feasible while signing with RSA and, if yes, how?

Also, how this kind of attack is applied with DH?

Talking about timing attacks in general, in which way AES is affected and how to solve it? (I mean, with RSA the "problem" is at multiplication level, while for AES where is the problem that makes the cipher implementation key or data dependent?)

The seminal paper on timing attacks is Paul C. Kocher, ‘Timing Attacks on Implementations of Diffie–Hellman, RSA, DSS, and Other Systems’, CRYPTO 1996, Springer LNCS 1109, 1996 (alternate link in case you hit a paywall).  This is also the standard reference, and it's quite approachable—I recommend reading it.  Here's a coarse high-level overview.

The basic idea for RSA and DH is to measure how long modular exponentiation takes as a function of a secret exponent.

How do you do this with RSA encryption?  Find an automated system that decrypts and sends an answer back to you, and send it a long sequence of messages, and measure how long it takes to decrypt each one.  Any timing variation in the crypto computation itself—once you've isolated noise from the network and other sources—is likely to be dominated by the timing variation in modular exponentiation to compute $m = c^d \pmod n$ for secret $d$, in naive RSA implementations.  (Here $n$ is the public key, $c$ is the ciphertext representative, and $m$ is the padded plaintext representative for (say) RSAES-OAEP, or secret key seed for RSA-KEM.)

How do you do this with RSA signature?  Find an automated system that signs and sends a signature back to you—not a signature on any document you want, only a signature on documents that the legitimate signer wants to sign.  For example, an HTTPS certification authority like Let's Encrypt will do this.  Send it a long sequence of requests to sign, and measure how long it takes to sign them.  Again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $s = h^d \pmod n$ for secret $d$, in naive RSA implementations.  (Here $h$ is the message hash, and $s$ is the signature.)

How do you do this with Diffie–Hellman?  Find an automated system that performs DH key agreement with a static key, and ask it to do a long sequence of key agreements with public keys of your choice.  Once again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $k = B^a \pmod p$ where $a$ is the static secret and $B$ is the attacker's ephemeral public key.

How do you do this with AES?  It's a little different, and the Kocher paper doesn't go into much detail beyond a casual mention.  The standard reference here is Daniel J. Bernstein, ‘Cache-timing attacks on AES’, Document ID: cd9faae9bd5308c440df50fc26a517b4, 2005-04-14.  It is also fairly approachable.  The coarse high-level overview is that the time it takes the CPU to load an element of an array depends on whether that position in memory is already cached.  By studying which elements of the S-box are typically not cached at some point in the computation yielding $S[k_i \oplus p_i]$, and studying which plaintext bytes $p_i$ cause the computation to take the most time, we can deduce the key byte $k_i$, and repeat for all the others.

There are also side channel attacks on other parts of RSA-based cryptosystems than modular exponentiation, such as Bleichenbacher's attack on PKCS#1 v1.5, which exploits side channels for the bytes that make up valid padding of a secret message representative to enable an adversary to decrypt or sign messages without the private key.  This side channel may manifest as a different error message, or as variation in the time it takes to respond, which extended the idea to RSAES-OAEP (paywall-free preprint), the successor to PKCS#1 v1.5 encryption.  Attacks in this class of side channels, padding oracle attacks, apply in other contexts as well, such as the Lucky Thirteen attack on CBC modes of block ciphers in TLS.

And there are, of course, other variations on the theme of timing attacks: e.g. exploiting cache-sharing in hyperthreading to recover keys from one hyperthread in another on Intel CPUs via the L2 cache, flush+reload attacks to recover keys via the L3 cache, cache-timing attacks that thwart naive RSA timing countermeasures, acoustic cryptanalysis using a microphone to hear variations in the spectrum of sound produced by secret-dependent timing in crypto algorithms, and so on.


Can OTP be made practical by using stretched hash algorithms? One of the main reasons for not using OTP in everydays life is that it is highly impractical - for encrypting 4GB of files we need a 4GB key that needs to be exchanged secure.

I've had an idea on how to get past this problem and want the opinions of experts (thats you!) about it. The main goal is to maintain the advantages of a OTP: Having perfect secrecy as the encrypted data can be decrypted to anything of the same length.

The main idea is to use a stretched hashing algorithm for deriving the OTP from a given password. This stretched hash iterates and adds the hash of the previous data to its content to create a new hash for the next data chunk making it unique.

This is my designed implementation in pseudo code.

Method createOTP ( CLEARDATA, PASSWORD, ALGORITHM )
    set OTP to empty
    set LASTSALT to derivation of given parameters
    While length of OTP smaller than length of CLEARDATA
        set LASTSALT to stretched hash of PASSWORD and LASTSALT using ALGORITHM
        set OTP to OTP and LASTSALT
    End While
    set OTP to OTP with length of CLEARDATA
    Return OTP
End Method

I do understand that the amount of possibilities is drastically reduced by using a hash algorithm. It should be impossible to verify that a given password is correct though as all passwords create an OTP with a different outcome producing possible legit words. The amount of computing power is also an advantage as the creation of such a big key can take a lot of time and is memory expensive.

You are creating a key stream using a hash function. This is often called a stream mode of operation (although it doesn't seem to be a well defined term). This is a known method of creating a key stream.

An OTP requires the key stream to be completely random. This is because it would otherwise be possible to brute force the key. If you can brute force the key then the scheme obviously does not provide perfect secrecy; meaning the scheme is not an OTP.

Problem is that it is extremely unlikely that there are two passwords that would provide a stream for which the resulting plaintext makes sense. So if you find the password you're pretty certain that you've hit gold. The longer the decrypted plaintext is, the more sure you are that the password is correct.

  It should be impossible to verify that a given password is correct though as all passwords create an OTP with a different outcome producing possible legit words.

Seems contradictory to the last paragraph. It's not correct.

  The amount of computing power is also an advantage as the creation of such a big key can take a lot of time and is memory expensive.

Perfect secrecy is the notion that the scheme cannot be broken regardless of the amount of resources.

Instead of using a hash function we normally use a block cipher such as AES. If you combine that with a counter then you have AES-CTR. CTR is an extremely common way of building a stream cipher.


Unpredictability and non-secret IVs There are two main properties of an initialization vector (IV): Randomness and Predictability. In most cases, the IV is not kept secret and known to anybody.
Say for CBC mode, we need to ensure that the IV is unpredictable because of (adaptive) chosen plaintext attack. So, since the IV is already known, how does predictability address the attack? Rather, why would one still need to predict the value of the IV when it is usually known? I am confused and hope to understand better, thanks.

In an adaptive chosen plaintext attack, the adversary is given the opportunity to query an oracle for encryptions of messages of the attacker choice.  In a CPA attack against CBC, for each query the oracle chooses a fresh IV at random, CBC-encrypts the adversary's message with that IV, and returns the IV-prefixed ciphertext.

One consequence of this is that the adversary only learns the IV that was chosen to encrypt their plaintext after they've made the query.  This is what "non-secret but unpredictable" means in this context.

Predictable IVs would mean that the adversary is able to learn what IVs will be used before choosing the messages to query for.  In that case the adversary can cancel the effect of the IVs by XORing their binary complements to the first blocks of the messages they query.  For example, if the adversary knows that the next IV will be $\mathrm{IV}_i$ they can query for the encryptions of $\overline{\mathrm{IV}_i} \oplus P_i$ (for a one-block plaintext $P_i$), and they get:

$$
\begin{align}
C_i &= \mathrm{IV}_i \| E_k(\mathrm{IV}_i \oplus \overline{\mathrm{IV}_i} \oplus P_i) \\
C_i &= \mathrm{IV}_i \| E_k(P_i)
\end{align}
$$

So they've basically tricked the oracle into revealing what $P_i$ encrypts to with an all-zero IV.


Hash 22 byte secret into 512 bit hash: Full entropy? Does it make sense to hash a 22 byte secret (which may not have full entropy since it is chosen by the user) into a 512 bit hash (using Keccak-512)?

More precisely, will the 512 bit hash have full entropy even though the input is only 22 bytes?

Yes, the 512-bit hash (using Keccak-512 or the like) of 22 bytes (176 bits) entered by a user (or from whatever source) has the full entropy of the input (that is: at most, 176 bits of entropy; much, much less for a user-specified 22-character string) for any practical purpose; and not as much entropy as there are bits in the hash's output. Argument that there is no reduction of the original entropy: odds that among the $2^{176}$ 176-bit strings, any two hash to the same value, are only $\approx 2^{-161}$, making the operation theoretically reversible (including for every input) with overwhelming odds. Arguments that entropy is not increased to the hash's width: the number of possible outcomes is no more than $2^{176}$ 512-bit values, which are fully determined by the specification of the 512-bit hash; and no deterministic process can increase entropy.

In fact the reduction in output entropy compared to input entropy remains mostly negligible for input of 63 bytes (or less); or more generally for input of at most $n-1$ bytes for an $n$-byte hash. Argument: even though the transformation is no longer reversible for every input, it still is expected to be reversible for a large majority of inputs.

This justify Owlstead's suggestion of using a narrower hash, such as SHA-224 or SHA-256, since the output will be smaller but have almost the same entropy.

However it makes only limited sense to hash a user-specified string: since the input is chosen by a user, it is vulnerable to guessing, and replacing that input by its hash won't solve that issue. For this purpose it should be used a key stretching mechanism, such a scrypt (or the more common but much weaker PKBDF2). Key stretching does not increase entropy, but greatly increases the difficulty of brute-force search (about: by the ratio of effort spent for stretching, to the effort necessary to decide is the stretched key is correct; that can be $2^{30}$ in some realistic situations, like a password-protected document).


What is the correct way to choose the start parameters for NIST tests? I had an idea of creating a pseudo-random binary sequence with that code:

import random as rd
p=[]
k=10**6
for i in range(k):
  p.append(rd.getrandbits(1))

s=''
for i in p:
  s+=str(i)
a=p.count(0)
b=p.count(1)
f = open('s.txt', 'w')
f.write(s)
f.close()

And on the stage of testing it with NIST tests there came a question of choosing right parameters for launching them. If I set the length of the sequence for this file for 100000 and number of bitstreams for 1, will it mean that from this file i will have only first 100000 bits tested as one sequence? Should the data in file be separated in some way?

I have also checked this question on crypto.stackexchange, but to be honest it didn't help me. Reading the official docs for NIST package didn't bring no understanding of bitstreams parameter too.

I will be very grateful if you explain me, how to set number of bitstreams parameter correctly and explain the meaning of it in this situation and the way the input data should be given to the tests.

Yes, the NIST tests are a little opaque.  You'll find that the input file size should be (no. bitstreams) * (no. bits for testing).   That means the input file will be automatically partitioned into (no. bitstreams) fragments, and the test suite run that times.  Yo don't have to do anything.  That creates the output histogram and the final P value assessments. It's typical to pick 10 streams.

So an input file should be at least 1MB in size.  A good rule of thumb is 1 Byte * (no of bits for testing).  But you won't get any meaningful P values for RandomExcursions and RandomExcursionsVariant until you go to a 10MB input as in ./assess 1000000.  However, these two excursion tests don't generate P values until the input is >100MB.

Note1.  The above input sizes are for binary files as I find them easier to manipulate.  You can modify accordingly for ASCII representations. The tests work the same way.

Note2.  Given that you're being Pythonic, the generator is the Mersenne Twister.  It will pass with flying colours, even though academically it has some weaknesses in the very higher dimensions. If it doesn't, it's a code problem.


Perfect secrecy with n-time key How can you encrypt $n$ messages with the same key, and have the same theoretical security you'd have encrypting a single message with a one time pad? For example, how can you encrypt two messages with the same key, and have that same theoretical security?

I think for $n=2$, something like $E(M) = (K_1M + K_0) \mod p$ should work, for prime p, $0 \leq M \leq p-1$, and each part of the key $K_i$ randomly chosen so $0 \leq K_0 \leq p-1$ and $1 \leq K_1 \leq p-1$.

This seems like the sort of thing that may have already been worked out or proved impossible, but I couldn't find it.

What you need for this is something called an $n$-wise independent hash function (like "pairwise independent" but $n$ instead). Such a hash function has the property that when applied to at most $n$ different inputs, its outputs are completely random. These can be constructed efficiently; e.g., a random polynomial of the appropriate degree works. What you actually defined with $E$ in your question is a linear polynomial with random coefficients and this is pairwise independent. There has been significant research on how to construct these, how to construct such functions that are almost independent, and so on.

Having said all of the above, you don't really gain anything cryptographically with this, since the size of the key still needs to be larger than the size of everything you compute. So, you may as well use the one-time pad each time. However, there are other applications that such functions are useful (mainly in complexity, but they are also sometimes used in crypto).


DHKE choice of private keys In some literature it is written that the private key should be chosen random from

{2,3, ..., p-1}

and in some it says

{2,3, ..., p-2}

I guess p-1 is a weak private key, but why is that so?
The calculation would be:

A = k pub, A = αp-1 mod p

$p-1$ is certainly a weak private key, in that it forces the shared secret to be a constant value as:

$a^{p-1} \bmod p = 1$

(This is known as Fermat's Little Theorem; no relation to Fermat's Last Theorem)

Hence, if either side uses $p-1$ as there private key, then both sides would arrive at the value of 1, and that's not great for security.


Need help cracking a Vigenère cypher with a period of 2 How do you crack a long Vigenère cypher when the key is unknown? I have tried frequency analysis, but I'm not making any progress.

Cracking a Vigenere cipher usually involves the below 3 steps:

The Friedman Test - The first thing you need is the length of the key (approximately at least). You can do this by finding the Index of Coincidence (IoC). Since Vigenere cipher is a polyalphabetic substitution cipher, its IoC should be near 0.038 for a given piece of cipher text. This is pretty nice webpage about IoC, its significance and how to calculate it. Once you have the IoC calculated, you can find the length of the key from the IoC by using the formula given in this document.
Splitting the text and Frequency Analysis -  Once you have the key length (say $l$), split the entire cipher text into multiple rows with $l$ columns. Now, each column here can be taken as a shift cipher. Frequency analysis can be used for an individual column to figure out the shift for that column. For example, if the frequency of the letter 'c' is the most in a column, then it is probably substituted for 'e' and so the shift here will be 2. Since the shift is 2, the key for this particular column is the letter 'b'. Likewise there will be $l$ shift ciphers with $l$ individual keys for each column or shift cipher. These $l$ keys will make the actual key of the Vigenere cipher.
Using the key to decrypt the entire text - After we compute the key, we can use it to shift the remaining of the text in each column (as is done in the encryption method of the Vigenere cipher). We will then combine the rows to get back the plaintext.

Note that you might have to perform the 2nd step multiple times since Frequency Analysis might not always give the right answer on the first shot.

Alternatively, after the first step, you can use the length of the key here to decrypt your cipher text in an automated way if you don't want to go through the hassles of step 2 and 3.

Hope this helps!


Public-key format for ECDSA as in FIPS 186-4? What is the public-key format for ECDSA as in FIPS 186-4, and where is it formally defined?

In particular, are there variants beyond Cartesian coordinates? Is that a pair of bitstrings, or a pair of integers, and with exactly what ASN.1 decoration (if any)? Would the point at infinity have a valid representation (I know it is not a valid public key)?

I ask because I find various formats around (in an X.509 public key certificate there is typically a bitstring including a header and Cartesian coordinates, but some code use point compression); I'm not even sure ANS X9.62:2005 would address my question; and I can't find the answer in ISO/IEC 14888-3:2016.

As said in comment, I believe you might find answers in the SEC1v2 document, which is used in many implementations (OpenSSL, Go, mbedTLS etc.) as a reference regarding that matter and which spares you the pain of reading all the many RFCs on that topic.

Now regarding the actual facts, if I generate a private key with OpenSSL:

openssl ecparam -genkey -out testsk.pem -name prime256v1

And then print its public details:

openssl ec -in testsk.pem -pubout -text

I get the following:

read EC key
Private-Key: (256 bit)
priv:
    00:ca:4e:db:94:a6:e5:a4:5f:3b:9e:f6:34:cf:22:
    5e:10:eb:7f:60:8d:56:d6:2a:e9:1c:08:4e:ee:c0:
    38:21:bd
pub:
    04:f3:13:94:7a:db:02:6b:c1:1f:3a:50:c4:04:07:
    d1:12:12:6a:b2:90:e8:c8:48:7a:4b:3c:f6:8a:7e:
    3b:4e:fe:67:e7:69:bd:74:b6:32:3c:26:ea:66:43:
    81:e6:74:d2:aa:db:1c:a6:44:03:fc:7a:72:90:28:
    20:bf:1d:3d:89
ASN1 OID: prime256v1
NIST CURVE: P-256
writing EC key
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAE8xOUetsCa8EfOlDEBAfREhJqspDo
yEh6Szz2in47Tv5n52m9dLYyPCbqZkOB5nTSqtscpkQD/HpykCggvx09iQ==
-----END PUBLIC KEY-----

Which, once decoded from ASN1 corresponds to:

SEQUENCE(2 elem)
    SEQUENCE(2 elem)
        OBJECT IDENTIFIER1.2.840.10045.2.1ecPublicKey(ANSI X9.62 public key type)
        OBJECT IDENTIFIER1.2.840.10045.3.1.7prime256v1(ANSI X9.62 named elliptic curve)
    BIT STRING(520 bit) 000001...1000

So my public key is actually a sequence of two tags:

firstly, another sequence, which is constituted of the details of my object, which is an ecPublicKey and is made for the curve prime256v1 (aka P-256) as per their "decoration" (aka OID).
secondly, the bit string corresponding to the EC public key point at hand, which is either compressed or not (this can be determined depending on its length, here as you can see we have $\frac{520}{8}=65= 2\cdot \frac{\log_2(q)}{8}+1 $, so no compression).

And as you pointed in comment, those points are encoded as explained in SEC1v2 section 2.3.3, and the exercise of converting the bit string into actual coordinates is explained in section 2.3.4


Can I determine if a user has the wrong symmetric encryption key? We're using the Objectivity/DB object database with a custom encryption plugin that encrypts serialized objects on disk. Encryption uses AES with a shared secret key held by all users. I would like to be able to provide some guidance to users if they enter the "wrong" shared encryption key (as in "I think you mistyped the encryption key. Please try again"). My first thought would be to use authenticated encryption to verify the decrypted data, but...

Because of constraints imposed by Objectivity/DB's storage manager, our encrypted data must be the same size as the unencrypted data, preventing us form using an authenticated encryption scheme. So, if the user supplies an incorrect shared key, the decrypted data is "gargabe", but is the right size and object references etc. point off to (often) segfault land. Thus, the user experience is a hard crash instead of a "oops, please retype your password". Not ideal.

Our current thinking is to store the HMAC of a known string (e.g. "This should decrypt"), encrypted using the shared secret key. We can test this hmac against the one produced with the users' key to verify the key is "correct" before continuing with deserialization of the unencrypted data from the database. Obviously this HMAC would have to be visible to anyone, before they make use of their secret key.

I'm concerned that this scheme exposes something that shouldn't be. Does using an HMAC in this way expose our encryption scheme (or worse, information about the shared key)?

I really don't have an answer (other than saying that storing a hash of the password is good as any other way of solving your immediate problem; there are other ways, but they all allow an attacker to run a dictionary attack on the database).

On the other hand, I do have these comments on what you're doing:

If getting decrypted gibberish will really crash your application, well, I suspect that you might want to consider better error handling.  There are reasons other than "the user gave us the wrong password" for getting bad data (the database server might have gotten a hiccup, the encryptor might have used the wrong password when writing the database record, perhaps an attacker might sprinkle random data over your database); I think you might want to have better error reporting than "Memory fault: core dumped"
Your requirement that there be absolutely no ciphertext expansion limits what you can do; it gives problem to most common encryption modes.  In particular:

If we encrypt the same record value twice to two different fields, does those show up as the same encrypted value?  If so, an attacker will be able to realize that they share a common value (even if he doesn't immediately know what that value is).  Common encryption modes handle this by including a randomization value (IV) as a part of the encrypted data; however, you can't explicitly include an IV in the record.
If we write (and encrypt) a record value A, and then later update that record to be a value B, can an attacker who sees both encrypted records deduce the relationship between A and B.  Common encryption modes handle this as using an IV as well; again, that's not available to you.
If we write (and encrypt) a record value A, is an attacker able to modify that record so that when we read it, it decrypts to a value B (where B has some attacker-chosen relationship to A)?  Common encryption modes handle this by either by being an authenticated encryption mode, or by using an explicit MAC -- neither works for you.

Given these potential problems, you probably should think about what are the security requirements, and how you can meet them.


what is contained in a public key certificate Public key certificate is a digitally signed document which verifies the sender is indeed the person. May I know how can the receiver tell the sender is indeed the person solely based on information on the public key certificate? What are contained in the certificate? Does a public key certificate contain the same information as in any certificate?

You actually don't trust the certificate by itself. A certificate is like a diploma that a company (or a domain, e.g. www.crypto.com) obtained from some trusted party, called CA, or Certificate Authority. This diploma states that www.crypto.com is allowed to communicate with you using the public key written in the diploma.

But, as you mentioned, www.crypto.com could generate that diploma to itself, then why should you believe them that the public key written in that diploma is realy theirs and not belongs to some man-in-the-middle attacker?

Here comes the signature part in the diploma. The CA attaches to that diploma a digital signature on www.crypto.com's public key, and you, as their client, verify that indeed, the signature is valid (you do so by applying the CA's verification key on the signature). By definition, nobody can forge that signature and trick you, i.e. to make a valid CA's signature on a fake www.crypto.com's public key.

A crucial key point here is that there exists a 'chain of trust', i.e. you'll believe www.crypto.com only if some CA that you trust tells you to believe it. By default, every browser (and operating systems) is bundled with a list of trusted CAs.


Can i modify data "protected" by a CRC16? There are 100 bytes with a CRC16.  However I only know the first 50.

I want to change byte 5 from a known value X to another value Y, and fix up the CRC16 to be valid - without knowing bytes 50-100.

This is possible with the TCP checksum, because it's just  addition.  But CRC16 is a polynomial.  Is it still possible?

Yes, it is possible. And quite efficient, too.

$\DeclareMathOperator{\crc}{crc}$CRC is linear, meaning $\crc(x \oplus y) = \crc(x) \oplus \crc(y)$, where $\oplus$ is bitwise exclusive-or.

Suppose there's a message $m$ and we're given $\crc(m)$.

Linearity means we can effectively compute the difference in the CRC digest by computing the CRC of the difference. For example, $m \oplus 1$ is the message with the right-most bit flipped — that's how XOR works. Because of linearity

$$\crc(m \oplus 1) = \crc(m) \oplus \crc(1)$$

So by computing $\crc(1)$ and doing a little bitwise arithmetic, we can find the CRC digest for the message if we were to flip the rightmost bit... without knowing the original message at all.

The same principle applies to your question. If you know the first byte of the message is (for example) 15 and you want to change it to 8, then compute $15 \oplus 8 = 7$ and pad that value with zero bytes on the right so it lines up with the first byte of the message. Let the padded value be called $d$. Then compute $$\crc(m) \oplus \crc(d) = \crc(m \oplus d)$$ which will be the forged CRC value. The reason you right-pad with zero bytes is $x \oplus 0 = x$ for any $x$: XORing a value with zero doesn't change it.

Here's what $m \oplus d$ looks like, if it helps clarify:

$$
\begin{array}{ccc}
                 & 15 & \text{unknown bytes} & (\leftarrow m) \\
          \oplus & 7 & \text{00 00 00 ...}  & (\leftarrow d) \\ \hline
                 & 8 & \text{(same) unknown bytes} \\
\end{array}
$$

(I realize using decimal instead of hex here may look a little weird, but oh well.)

The original message's first byte was 15. We wanted it to be 8 instead. We found $15 \oplus 8$ to be 7, so that's the value we right-pad with zeros, because the zeros won't affect the rest of the message. Linearity lets us pull off the trick. Of course, this technique works for any number of bytes, not just the first one.

(By the way: the need to right pad the difference with zero bytes is why we needed to know the length of the original message.)

Note: fgrieu's comment below about some CRCs having a weaker property is relevant, but doesn't materially affect the attack (set $z = 0$ in his comment to use the same attack essentially).


Meaning of "Security can be reduced to a problem" I'm studying reductions in cryptography and confused about the way people use the word "reduction".
My question is almost the same as a past question, but what I want to ask is slightly different.

A lot of papers or articles (e.g. Wikipedia "Reduction (complexity)" or "The Algebraic Group Model and its Applications" by Fuchsbauer et al.) say that a reduction $R$ from a problem $P$ to a problem $Q$ is an algorithm such that for every adversary against $Q$, $R$ uses it as a subroutine to solve $P$ correctly.
In other words, if $P$ can be reduced to $Q$, $Q$ is "no less hard" than P.

In a security proof of a protocol $\Pi$, we often assume the hardness of a problem $P$.
In this proof, for every adversary $\mathcal{A}$ against $\Pi$, we show that there is an adversary $\mathcal{B}$ against $P$ whose advantage is (essentially) no less than $\mathcal{A}$.
I think this is a reduction from $P$ to $\Pi$ and this means $\Pi$ is no less hard than $P$.
More formally, breaking $\Pi$ is no less hard than $P$ and since we assume $P$ is hard breaking $\Pi$ is hard.

However, some people say "the security of a protocol $\Pi$ can be reduced to the hardness of $P$" in this case.
I think this is the wrong way of using the word "reduction" since we actually reduce $P$ to breaking $\Pi$.
Others say "the security of a protocol $\Pi$ is based on the hardness of $P$", and I think this is true.

Am I right or wrong?
Thanks in advance.

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you describe (using $Q$ as a subroutine/oracle to solve $P$) is the most common in cryptography (it is known as a Turing reduction).
I will notate this $P \leq Q$.

Note that reductions often have a little more detail than what you describe, specifically some bounds on the amount of resources that the reduction $R$ has access to.
If $R$ is all powerful then "hard languages" reduce to "easy languages", because $R$ can just ignore the subroutine/oracle it has access to and solve the problem directly.
This is seen as a boring formalization, so we generally want to force $R$ to be too weak to solve $P$ directly (having it be polynomial time is generally sufficient). This is mostly interesting when discussing properties of complexity classes under reductions though.

Now I'll quickly highlight that reductions are intrinsically about the existence of algorithms.
$P \leq Q$ can be interpreted as saying:

  If there exists an algorithm for $Q$, then there exists an algorithm for $P$

i.e. $P \leq Q$ can be parsed as the logical statement:

  $$ \exists \text{ algorithm for }Q\implies \exists \text{ algorithm for }P$$

With this in mind, let us look at the sentence you highlight:

  The security of a protocol $\Pi$ can be reduced to the hardness of $P$

What does it mean for a protocol to be secure? Normally "There doesn't exist an algorithm to break the protocol" (I will notate the problem of breaking the protocol $\Pi$ as $B_\Pi$. Similarly, what does it mean for a problem to be hard? "There doesn't exist an algorithm to solve the problem".
Ignore the word "reduced" in the above sentence quickly.
The goal of a reduction in cryptography is to prove "If the problem $P$ is hard, then the protocol $\Pi$ is secure", i.e. a statement of the form:

$$\not\exists\text{ algorithm for } P\implies \not\exists\text{ algorithm for }B_\Pi $$

This doesn't match up with our prior definition of reduction though.
We can look at the contrapositive of the above statement to get the equivalent statement:

$$\exists\text{ algorithm for }B_\Pi\implies \exists\text{ algorithm for }P$$

This is then written as $P \leq B_\Pi$.

Solving $P$ (complexity-theoretically) reduces to breaking the protocol $\Pi$
The inability to solve $P$ (i.e. hardness) implies to the inability to break (security) $\Pi$

We could read this later statement as defining a "cryptographic reduction" $B_\Pi \leq_{cr} P$, where this stands for a statement of the form:

$$ \not\exists\text{ algorithm for }P\implies \not\exists\text{ algorithm for }B_\Pi$$

But then this would be fundamentally dual to the complexity-theoretic reduction, i.e. we would have that $P \leq B_\Pi$ and $B_\Pi \leq_{cr} P$. Under this notion of reduction the authors' statement becomes correct, but it is the "reverse" direction that we expect from complexity theory.

This is all to say that for "reduce" in the sense of complexity theory, what they write is technically incorrect (but can be trivially fixed by appealing to the contrapositive). This is such a basic step that it is quite common to do it implicitly, but to formalize things in terms of complexity-theoretic reductions there is an intermediate step which must be made explicit.


How does one calculate a primitive root for Diffie-Hellman? In the Diffie-Hellman key exchange, one of the steps involves calculating a primitive root of a prime number $p$. How would one go about doing so, considering that $p$ could be very large?

Is there some sort of algorithm or equation?

In the general case, for proper security with Diffie-Hellman, we need a value $g$ such that the order of $g$ (the smallest integer $n \geq 1$ such that $g^n = 1 \mod p$) is a multiple of a large enough prime $q$. "Large enough" means "of length at least $2t$ bits if we target $t$-bit security". Since $n$ necessarily divides $p-1$, $q$ divides $p-1$.

We normally want to know $q$, so $q$ is generated first, then $p$. Namely, we create a random prime $q$ of size $2t$ bits, then we produce $p = qr+1$ for random values of $r$ until we hit a prime. This is what is done for generating DSA key parameters, which have the same structure than Diffie-Hellman key parameters (see the DSA standard). Note that producing a random prime $p$ would already yield a "large enough" $q$ with overwhelming probability (but we wound not know the value of $q$, only that it is very improbable that the largest prime factor of $p-1$ is smaller than $2t$ bits).

Then, to get the "generator" $g$, we can just use any random integer modulo $p$: the probability that $q$ is not a divisor of the order of a random non-zero integer modulo $p$ if $1/q$, i.e. so small that you will not hit it in practice (the overall security of Diffie-Hellman relies on the practical impossibility of obtaining events which are billions of times more probable than that). Nevertheless, some people get nervous in the face of probabilities, and will feel safer if we test the generator. The procedure then becomes: create a random integer $u$ modulo $p$ and compute $g = u^{(p-1)/q} \mod p$. If $g = 1$, then try again with a new random $u$ (this is the very improbable event that you will not get in practice); otherwise, it can easily be shown that $g$ has order exactly $q$, and thus is a good generator for Diffie-Hellman.

Another method is to get a very large $q$, i.e. generate $p$ such that $p = 2q+1$ and $q$ is prime. We then call $p$ a "strong prime". It can be seen that the order of a random non-zero integer $g$ modulo $p$ is either $1$, $2$, $q$ or $2q$; order $1$ is possibly only with $g=1$, and order $2$ is possible only with $g=p-1$. Any other integer modulo $p$ will be fine for Diffie-Hellman. In particular, you can use $g=2$ as generator, which can yield a bit of a computational speed-up.

But really, the fastest way to get $p$ and the generator is to abstain from generating them. There is no security issue with Diffie-Hellman (or DSA) if you reuse previously generated $p$, $q$ and $g$; several people can share these values for their respective key pairs and this does not weaken the system in any way. So you can pick up "standard" values, e.g. the ones described in RFC 2409 (section 6.2) or RFC 5114 (sections 2.1 to 2.3).


Profile Complexity LFSR I try to understand how Complexity of an LSFR calculated.

For example I have a bit sequence 110101 and it's profile 1 1 2 2 3 3.

Is there any easy way in order to produce the profile?

Given any $n-$bit sequence $(a_1,\ldots,a_n)$ with $a_k \in \{0,1\}$ you can use the Berlekamp Massey algorithm (which is conveniently recursive) to obtain minimal degree characteristic polynomials $C_m(X)$ where $C_m(X)$ is the output polynomial of Berlekamp Massey, when its input is $(a_0,\ldots,a_m)$ with $1\leq m\leq n.$

The linear complexity profile of $(a_1,\ldots,a_n)$ is simply the sequence $d_1,\ldots,d_n$ where $d_m$ is the degree of $C_m(X)$.

If you have $n=2^k,$ then there is a much faster algorithm to compute just $d_n$ due to Richard Games and Agnes Chan, the so-called Chan-Games algorithm, which of course can be used to obtain $d_1,d_2,d_{2^2},\ldots,d_{2^k}$ but not the complete profile. This has complexity $O(n \log n)$ while Berlekamp Massey has complexity $O(n^2).$

There are other fast algorithms for cases such as $n=m 2^k$ where $m$ is odd which use various generalisations of the coding theoretic result also known as Blahut's Theorem, which is that the linear complexity of a sequence is the Hamming weight of an appropriately defined and normalized finite fourier transform of the sequence.


Could the reversibility of adding function be considered a weakness to secp256k1? I have just started studying cryptography and secp256k1. I just wonder that adding two points can be easily reversible when the generator point is publicly known.

I mean that if $Q=\operatorname{adding}(P, R)$ then we can calculate $P$ as $\operatorname{adding}(Q, R)$, am I right? Would this be considered a weakness? I am not sure if there exists a known reverse function for doubling as well, Something that could recover P with having Q from $Q=\operatorname{doubling}(P)$.

Anyways, what point is the major strength of secp256k1? Does that rely on the functions we choose for adding and doubling? Or maybe it relies on the nature of the $IF$ statement we use in the calculations?

Taking any arbitrary functions $Q =f(P)$ and $Q=g(P, R)$ and then performing the multiplication function as long as the multiplication function is Surjective and Injective over the field $F_p$, will we get the same level of security?

If $Q=\operatorname{adding}(P,R)=P+R$, then $P$ can be computed from $Q$ and $R$ as $P=\operatorname{adding}(Q,-R)=Q+(-R)$ where $-R$ is easy to compute from $R$ (just change the $y$ coordinate of $R$ from $y_R$ to $p-y_R$ where $p$ is the order of the prime field). This property follows from $\operatorname{adding}$ being a group law.

If $Q=\operatorname{doubling}(P)=P+P=2\times P$, then we can efficiently compute $P$ from $Q$. One method is to use that $P=\displaystyle\frac{n+1}2\times Q$ (where $n$ is the order of the curve's group). This property follows from $n$ being odd.

Neither property is considered weakness, because it follows from having a group (of odd order), which is necessary for the applications thought, including ECDSA.

By definition of secp256k1, for that curve $p=2^{256}-2^{32}-977$ and $n=2^{256}-432420386565659656852420866394968145599$.

  What is the major strength of secp256k1?

It forms with point addition a group of known 256-bit prime order $n$ with a generator $G$, such that we do not know an algorithm requiring much less than $\sqrt n$ steps to compute $a$ from $a\times G$, for random $a$ in $\Bbb Z_n^*$ (Discrete Logarithm Problem).
Note per comment: $G+G=2\times G$ in a group noted additively becomes $G*G=G^2$ in that same group noted multiplicatively. Similarly $Q=a\times G$ in a group noted additively becomes $Q=G^a$ in that same group noted multiplicatively. This is why solving either equation for $a$ is called the Discrete Logarithm Problem in the group considered.

More strongly, we know no algorithm requiring much less than $\sqrt n$ steps to tell sizably better than random if a triple what obtained as $(a\times G,b\times G,c\times G)$ or as $(a\times G,b\times G,ab\times G)$ for random $a$, $b$, $c$ in $\Bbb Z_n$ (Decisional Diffie-Hellman assumption).

secp256k1 is preferred over simpler groups with the same properties, notably Schnorr groups, because a point can be expressed much more compactly and the group law is much faster. secp256k1 is preferred over other groups with the same properties also built by point addition on an elliptic curve over a prime field, notably secp256r1, because the special form of $p$ for secp256k1 allows slightly faster calculation, with no known decisive drawback.

  Does that rely on the functions we choose for adding and doubling?

Yes it has to do with the group and its law, that is the functions we choose for adding and doubling.

  Taking any arbitrary functions $Q=f(P)$ and $Q=g(P,R)$ and then performing the multiplication function as long as the multiplication function is Surjective and Injective over the field $\Bbb F_p$, will we get the same level of security?

No, even with added constraints making the operation defined by $f$ and $g$ a finite group law. As a counterexample, take the group $(\Bbb Z_p,+)$ for some prime $p$: that defines point doubling $f$, point addition $g$, and we can take any non-zero element as $G$ with $n=p$. Point multiplication reduces to multiplication modulo $p$. That allows construction of the group as stated, yet the DLP is trivial, giving no security: given $Q=a\times G$ we can compute $a$ as $(G^{-1}\bmod p)\times Q$ where $G^{-1}\bmod p$ can be computed by the Extended Euclidean Algorithm.

Note: When restricted to point addition and doubling as in an axiomatic construction from $f$ and $g$, we can compute $-R$ as $(n-1)\times R$.


What are some real-world examples where one-time-pad encryption is used or can be used? I understood that one-time-pad (OTP) encryption ensures perfect secrecy. However, I couldn't find any real-world examples where an OTP was used.
Also, what are some real-world examples where it won't be suitable to use the OTP.

If you want to have the perfect secrecy then it is the only choice. However, it doesn't have integrity and authentication.

If you want to see when it is used, see OTP at Wikipedia, especially the cold war era.

It is not suitable for modern usage, where a lot of messages is sent/received. The drawback is the necessary condition; key length must be at least message length. Also, you must somehow transmit the OTP key securely, not by encryption. You must trust the carrier or you have to carry yourself.

A simple question arises what will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging.

Per comment: There is an interesting question on this site; Is there a companion algorithm for OTP to ensure integrity and/or authentication?, asking the companions for integrity and authenticity since the OTP only provides confidentiality. Clearly, If you send your data only encrypted with OTP, the Oscar, the middle man, can modify the message. Of course, if he has no knowledge of the structure of the data, the modifications are random. In the other case, the results can be catastrophic. Save the man can be converted into Kill the man.

As some said, (most of | sometimes,) the time integrity is more important the confidentiality. You may not need encryption but integrity is almost necessary.


Can we modify any hash function like SHA-1 or MD5 to perform multiple iterations at once to gain calculation speed? Is it mathematically possible to adapt a given hash function (f.e. SHA-1 or MD5) so it performs a known number of iterations at once?

Concrete example would be:

data = SHA1_10000(data)

instead of:

for (i = 0; i < 10000; i++) data = SHA1(data)

while resulting in the same output, but being 10000 times faster.

If you would find something like this, it would probably even point to a weakness in the hash function.

Impossiblity in the random oracle model. Hash functions are often assumed to behave like random oracles (i.e., for every new query they return a uniformly random value, while answering consistently for repeated queries). For a random oracle, the output is not defined before querying the random oracle at the input - so in this model it should be relatively easy to argue that it is impossible to find what you are asking for.


AES ShiftRow Confusion I'm implementing AES and I'm getting confused in the ShiftRows step. So far, my key expansion and SubBytes works and I get the same output as specified by the NIST publication.

For the ShiftRows Steps, if we refer to the test vector below from NIST, the output is incorrect according to this:

Round 1, from NIST page 35:

--------------------------------------------------------------
state:      63cab7040953d051cd60e0e7ba70e18c <-- SubBytes()
state:      6353e08c0960e104cd70b751bacad0e7 <-- ShiftRows()
--------------------------------------------------------------

If we consider the matrix below:

$$\begin{pmatrix}
S_{00} & S_{01} & S_{02} & S_{03} \\
S_{10} & S_{11} & S_{12} & S_{13} \\
S_{20} & S_{21} & S_{22} & S_{23} \\
S_{30} & S_{31} & S_{32} & S_{33} \\
\end{pmatrix}$$

$$\begin{pmatrix}
\texttt{63} & \texttt{ca} & \texttt{b7} & \texttt{04} \\
\texttt{09} & \texttt{53} & \texttt{d0} & \texttt{51} \\
\texttt{cd} & \texttt{60} & \texttt{e0} & \texttt{e7} \\
\texttt{ba} & \texttt{70} & \texttt{e1} &  \texttt{8c} \\
\end{pmatrix}$$

Then the output is clearly different.

$$\begin{pmatrix}
\texttt{63} & \texttt{ca} & \texttt{b7} & \texttt{04} \\
\texttt{53} & \texttt{d0} & \texttt{51} & \texttt{09} \\
\texttt{e0} & \texttt{e7} & \texttt{cd} & \texttt{60} \\
\texttt{8c} & \texttt{ba} & \texttt{70} & \texttt{e1} \\
\end{pmatrix}$$

The state must be written/read along the columns:

63cab7040953d051cd60e0e7ba70e18c $\mapsto$ $
\begin{bmatrix}
63 & 09 & cd & ba \\
ca & 53 & 60 & 70 \\
b7 & d0 & e0 & e1 \\
04 & 51 & e7 & 8c
\end{bmatrix}
$

shift rows $\mapsto$ $
\begin{bmatrix}
63 & 09 & cd & ba \\
53 & 60 & 70 & ca \\
e0 & e1 & b7 & d0 \\
8c & 04 & 51 & e7
\end{bmatrix}
$ $\mapsto$ 6353e08c0960e104cd70b751bacad0e7

See Figure 3 in FIPS SP 197, 3.4 (http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf).


Can I measure entropy through compression only? Say I have a file containing words from the English language.  Not meaningful text, just a repetition of a few words.  The original size is 1559454 bytes and it is compressed by a certain program to 75742 bytes.  (A very good compressor, it seems.)  Can I estimate the entropy of the source producing such file using essentially the byte reduction?

Can I estimate the entropy of the source producing such file using essentially the byte reduction (when compressing the source's output)?

No, at least for Shannon entropy. Entropy is a characteristic of the source, that can't be determined from a finite sample of the output of the source. It's can't even be estimated in practice without information about what the source is, and the question gives no such information.
The best we can is estimate a plausible upper bound of the entropy of the source that generated the file: $75742/1559454$ entropy bit per output bit. That's not a mathematical certainty: it's mathematically possible that a perfectly random source generated that file (the probability is $2^{-8\times1559454}>0$). And that's not a practical certainty either, unless we add a vague hypothesis that the observed characteristic goes on: a device which output consists of the $1559454$ fixed bytes followed by indefinitely many uniformly random bytes is a source with $1$ entropy bit per output bit.
We do not get any lower bound better than $0$. Proof: any deterministic program that indefinitely outputs is a source with zero entropy. And it is trivial to make a deterministic program that indefinitely outputs a sequence starting with the $1559454$ bytes (perhaps, repeated). That's not merely theoretical:

The program which output consists of the repeated sequence of two bytes a  produces output which first $1559454$ bytes matches the problem statement, even for some actual compressor; say, one that never compresses by more than a factor of 20 (that's quite plausible for e.g. an audio compressor).
Even if we restrict to files that could reasonably occur in actual use, it's entirely possible that a program designed to obfuscate a file into english words, written as an (elementary and rather poor) steganography tool, has output that matches the problem statement (for an actual text compressor) when fed as input a file of about $50000$ bytes, including if it is all-zero.

Conclusion: practical procedures that attempt to assess the entropy of a source from its output only are doomed to, at best, give a plausible upper bound of that entropy (and can do so only under the hypothesis that the output tested is representative). Computing a compression ratio is one such method.


Bit padding instead of PKCS#5 padding Padding oracle attacks are a huge nuisance when using CBC mode encryption without authentication. Wouldn't all those padding oracle attacks be avoided if we'd just use bit padding instead? Or is does bit padding also leak information during decryption?

With byte aligned data, bit padding allows the padding oracle attack. Every message has to end in a 0x80 byte followed by any number of zero bytes. You can iterate one byte at a time just like with many other byte paddings.

If you allowed plaintexts that are not a full number of bytes long, the attack wouldn't be possible. (Every plaintext that didn't end in a full block of zeros would decode, so no attack.) However, most real world encryption uses byte aligned data.


File format of an $2048$ bits RSA public key From here, there are $14$ bytes specifying the file format of the key. I am still quite confused about the format bytes. For example, the following public key
30 82 01 0a 02 82 01 01 00 8e a3 d1 c7 9c 86 05 52 3d 70 9a 5b 24 8a 6e ab 8f 5d 8d 9a 44 5f 25 78 c7 ba bd 3a a6 e1 36 b8 55 88 18 d7 ea e8 14 2c 68 8f e7 fe 94 4c f3 fd ad 0b e6 d2 eb 9e d2 66 b4 3a 3b d1 bb 5d d5 2a 53 7e 0f 1d ba ec 03 29 9d 47 50 3b 99 fb 4a 3a 80 a2 23 3e d7 11 e3 de a8 8d ab 7c 90 d0 92 af 36 b8 8b 28 fd 80 ec bc 37 6d 23 44 86 4e 28 19 1d 18 37 af 44 a9 40 b3 f6 e7 6c ad 56 5d 6f ff 3b e3 a5 cc 23 5c 54 2a 47 28 5b 29 f3 45 8e 69 98 ad 57 45 2e 60 bd ac 55 fc 35 e8 47 9f 98 0d f9 ea 9d 55 35 c9 db af 24 d2 bc 18 12 02 53 d6 aa ef 9c c9 11 c9 8e d7 7c 4f 2f 22 0f 66 b1 bf 06 a5 fa 87 22 9f ff f6 20 75 e7 51 87 26 30 c2 e1 a5 30 2c a1 fc 47 a5 f7 a5 38 d3 cc 8d 0e ee 5a 54 ee a2 f9 ff d0 0a 0f 18 7f 94 d2 04 5e 1f 25 ca be 4e 30 c3 40 00 ed a4 ce 58 ab 23 39 2d 02 03 01 00 01
is taken from google's certificate. The first byte $30$ means it is a sequence. Then I don't know what is the meaning from 2nd byte to 9th byte. Can anyone explain to me?
UPDATE: The 2nd byte (82) means that the following 2 bytes give the length of the sequence. The 5th byte tells us that it is an integer. The byte following it tells us the length and the value of the integer (I guess). Then the rest I have no idea.
Also what do the last 3 bytes stand for? I can't find format start with $01$.

You've mostly pieced it out.  This is a DER encoding the the public key, and consists of a sequence of two integers (the first being the modulus, and the second being the exponent).

Here is the breakdown of the encoding:

30

The value 30 is used to signify 'sequence'; this is a container that carries a list of DER-encoded objects.

82 01 0a

Whenever we have an object (including a sequence), we always encode the length of the object (that is, how many bytes are in the DER-encoding of the object, not counting the object type and the length field); here, the 82 signifies that the length itself is 2 bytes long, and that the total length is 0x010a = 266 bytes.

02

Now, we get to the first object in the sequence; the value 02 is used to signify 'integer'.

82 01 01

And this is the length of the integer; again, the 82 signifies that the length itself is 2 bytes long, and that the total length is 0x0101 = 257 bytes.

00 8e a3 d1 c7 ... ab 23 39 2d

These 257 bytes are the actual integer, in bigendian format.  Note that the first byte is a 00; that is required because of the rules of DER encoding.  Specifically, the 02 format encodes an integer, and it is allowed to encode a negative integer (remember, DER is a general format, and is not targetted specifically to encoding public keys).  The rule is that the integer is negative if the msbit of the encoded value is a 1.  We need to encode a positive integer; the top byte of the value we encode is 8e, which has a msbit of 1.  To prevent this from confusing the decoder, we prepend a 00 on top to make the msbit 0.

And, while you didn't ask about the end part, here are the last 5 bytes:

02

This signifies that the second element in the sequence encodes an integer

03

This signifies that this integer is encoded in 3 bytes

01 00 01

This signifies that the encoded integer is 0x10001 == 65537


How would I make a decoder agnostic steganographic file? I would like to make a steganographic file that can be decoded on multi-platforms, now & 20 years from now.

I don't want to do so with software that may be out of date when the message decode is attempted.

How would I do this?

I will assume you're referring to steganography in images.

The most important thing would be to use a color space that is likely to be recognizable 20 years in the future. For this, sRGB is a good candidate. It was created more than 20 years ago, in 1996, and it is still the most popular color space in use. It's safe to bet that, in 20 years, it will not be forgotten. You can use traditional LSB steganography to encode information. As long as the color space is preserved, it should be compatible with whatever future software you are using (or compatible software that is easy to find).


Does the AES Mixcolum Matrix use a fixed or random matrix? I understand how work the multiplication but I'm confused if the matrix to use is fixed or variable.
The site where I read how mixcolums work is this https://math.stackexchange.com/questions/248456/matrix-multiplication-in-aes-mixcolumns-step
Thanks in advance for the replies.

It is fixed.

In the forward direction, it is always:

$$
  \begin{bmatrix}
    02 & 03 & 01 & 01 \\
    01 & 02 & 03 & 03 \\
    01 & 01 & 02 & 03 \\
    03 & 01 & 01 & 02
  \end{bmatrix}
$$

In the reverse direction, it is always:

$$
  \begin{bmatrix}
    0e & 0b & 0d & 09 \\
    09 & 0e & 0b & 0d \\
    0d & 09 & 0e & 0b \\
    0b & 0d & 09 & 0e
  \end{bmatrix}
$$

Note that the multiplication (and additions) done during the matrix multiplication are done using $GF(2^8)$ operations, which are not the same as $\mathbb{Z}_{256}$ (which is what was confusing Frenzy Li)


What is the concrete communication complexity of Commitment schemes? Say you want to commit an $n$-bit plaintext, $x \leftarrow ^ r \{0,1\}^n$.

What is the concrete communication cost, in terms of $n$, of the following:

Data sent by verifier to initialize (applies in Pedersen, may not apply in other schemes).
The commitment
The decommitment

I read this description of the Pedersen scheme. Since the scheme only allows you to commit to values in $Z_q$, I assume that, in order to avoid dealing with enormous primes, in practice you would break up your input into $b$-bit blocks such that $q > 2^b$. It seems reasonable to me to pick $b=128$, $q$ a 129-bit prime chosen such that $p=2q+1$, making $p$ a 130-bit prime. I assume $p$, $q$ and $g$ (the generator) are publicly known and calculated before hand. In this case, the cost of sending 128 bits would be:

Data sent by verifier: $h =g^a\mod p$, a 130-bit number
The commitment: $c = g^m h^r \mod p$, another 130-bit number.
The decommitment: $m, r \in Z_q$, two 129-bit numbers.

So the total communication cost would be $\frac{518 n}{128}$ bits.

Is this right?

If there are other commitment schemes that are better, feel free to give concrete numbers for those instead. However, I would like to commitment scheme to be self contained, so this paper, while it provides very clear explanations of its concrete security, doesn't fit the requirements I need because it requires a common reference string.

The simplest commitment scheme is a hash based commitment; to commit to a value $M$, the committer selects a fixed length value $R$ and publishes $\operatorname{Hash}(R \mathbin\Vert M)$; to decommit, he publishes the values $R$ and $M$.

If the Hash function is collision resistant, then the committer cannot commit to two different messages; if $R$ is long enough, then it is infeasible to recover $M$ from the commitment.

With this in mind, and assuming we're using a 256 bit hash (such as SHA256) as our hash function, and a 128 bit $R$:

Data sent by verifier: none
The commitment: 256 bits
The decommitment: 128+n bits

This is a total of 384+n bits.

I believe that it can be shown that you cannot do better without reducing the practical security of the system below the "128 bit" level


2DES vs. two-key triple encryption, with no decryption step So studying double encryption (double DES) and understanding why it is subject to a meet-in-the-middle attack, I tried to see if the same attack could be applied to a triple encryption with only two different keys and no decryption operation. I.e.:

$$c=E_{k2}(E_{k1}(E_{k1}(m)))$$

where $c$ is the ciphertext, $m$ the plaintext and ${k_1,k_2}$ the two keys.

It seems the normal way is to have encryption-decryption-encryption with either 2 or 3 different keys. However, with only two keys and three sequential encryptions provide any more security than double DES? I guess you could still apply the meet-in-the-middle attack, since there are intermediary values to which you can apply the same attack, but I'm a bit confused to whether it adds more security than double DES?

I guess it would require $2^{56}$ additional operations to perform a meet-in-the-middle attack since there is an extra step compared to double DES?

Additional question:
Does it matter in which order you apply the keys? I.e. is there a difference between encrypting with $k_2-k_1-_1$ vs. $k_1-k_2-k_1$?

All keys in my question are of size 56-bits.

The meet-in-the-middle attack still applies; instead of attack effort $2^{57}$ DES invocations, you just increased it by $2^{56}$ extra DES block encryptions, i.e. up to about $2^{57.6}$ in total: a mere +50% increase. On the other hand, you also made the overall block cipher (your two-key triple encryption) 50% more expensive to use, so the overall security has not changed at all: attacker and defender have been slowed by the same amount.

What would make the construction much stronger is what is down with the true Triple-DES in two-key mode: $E_{k1}(D_{k2}(E_{k1}(m)))$. With the keys used alternately, the meet-in-the-middle is effectively prevented.

You could replace the middle decryption with an encryption: $E_{k1}(E_{k2}(E_{k1}(m)))$. This would still be secure, but no longer backward compatible with "plain DES", for no obvious gain (DES encryption and decryption are identical, save for the ordering of the sub-keys, so converting a decryption block to an encryption block does not seem to imply any implementation advantage).


Lightweight primality certificates for untrusted DH parameters Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run its own expensive rounds of primality testing? By lightweight, I mean not significantly harder than the recommended number of Miller-Rabin rounds on the generation side, and significantly less intensive during verification (after all, there's no point if it doesn't make life easier for the client).

Well, one possibility to generate a moderately lightweight certificate would be to use this theorem:

If we have values $p, q, g$ such that:

$1 < g < p$
$q > \sqrt{p}$
$q \mid p-1$
$g^q \equiv 1 \pmod p$
$q$ is prime

Then $p$ is prime.

So, for a certificate, we would have a list of $(p_i, g_i)$ values such that $p_{i-1}, p_i, g_i$ meet the above conditions (as $p, q, g$), with $p_0$ is the value $p$ we're actually interested in proving, and the final $p_n$ value is a prime small enough to make primality proving trivial (e.g. it may less than 16 bits long).  Each line in the certificate (almost) halves the value of $p_i$, and so the total number of lines is managable.

As for verifying the certificate, it should be fairly obvious, for each line in the certificate, we would check the first four conditions directly, and then step to the next line to verify the last condition; as the last step, you'd do a quick check that $p_n$ is prime.  The expensive part is the $g^q \equiv 1$ condition; if you total it, it's a bit less than a single Miller-Rabin computation (but has the advantage that it is deterministic; if it validates, there is no need to do a second iteration).  Whether this counts as 'significantly less' is something you'll need to decide.

As for generating the certificate, you can't select a random $p$ and try to generate the certificate.  Instead, you would create the certificate (and the prime) from the bottom-up; select a $p_n$, and then at each step, given $p_i$, you would search for a prime value $p_{i-1}$ (and $g_i$, but that's easy), eventually ending up with a $p_0$ value of the desired size.  The FIPS 186-4 Shawe-Taylor algorithm does exactly this (you'll just need to record the intermediate $p_i, g_i$ values).

As a side effect, $g_1$ is an appropriate generator for the DH group (as it generates a large prime-sized subgroup).

On the other hand, I would second Future Security's suggestion to the ECDH instead; that uses less resources, and doesn't have any known 'solve this problem and break the entire group' attacks


AES for 64 bit plaintext I have a 64 bit plain-text that i want to encrypt using AES. But to use AES for 64 bit plain text

i can either add padding bits to it
or use AES in CTR stream mode.

My question is

which approach is more efficient?

Is there any other scheme that i can use to encrypt 64 bit data and is as secure as AES.

There is no such thing as "as secure as AES" when it comes to encryption. This sounds weird, but let me explain. AES is a block cipher. As block cipher it always uses deterministic permutation of the bits in the plain text block. And as it is deterministic it always encrypts the same plaintext block to the same ciphertext block.

It is therefore not IND_CPA secure when used as a cipher. In other words, you can clearly see that the same plaintext encrypts to the same ciphertext; you can therefore distinguish plaintext blocks by looking at the ciphertext blocks. AES is a secure block cipher, it is not a secure cipher by itself.

Now if you would add padding bits then you would still not accomplish IND_CPA security. Padding schemes for block ciphers - such as PKCS#7 padding - are generally deterministic. So that's not going to work in the general case.

CTR mode encryption is considered a secure mode of operation for block ciphers with a block size of 128 bit or more. CTR mode however requires a nonce to operate. So you would either have to generate one and store it with your ciphertext or you would have to use some out-of-band means to generate a nonce (e.g. a number stored elsewhere in a database). This is a good option if you can store some 128 bits of output: simply store a 64 bit randomly generated nonce and 64 bits of ciphertext (which you may have to extend to 128 bits for many API's by right-padding with zero's).

CTR mode doesn't add any integrity protection, so you might want to add this by using an authenticated (AEAD) cipher. This will however add more bits for the authentication tag to the output.

With 64 bits of plaintext it becomes very tempting to simply encrypt with a 64 bit block cipher. This won't provide IND_CPA security, but you may not care if identical plaintext blocks can be distinguished. You could also take a look at Format Preserving Encryption. Triple DES would still be an option for this; in practice it will likely offer as much security as a 128 bit cipher.

Maybe it's a good idea to use public key encryption. This would for instance be the case if you don't want the decryption key exposed during encryption.

I've answered this in the general sense. But you can see that there are many unknowns to us. This is why the question "Is there any other scheme that i can use to encrypt 64 bit data and is as secure as AES." is bunk.

Encryption is not a goal; providing security for your data is. And without a clear definition of your goals, use cases, requirements and threat models any answer may be wrong.

Note that all schemes have limits on how many 64 bit blocks may be encrypted with a single key.


Why is AES considered to be secure? The security of RSA is based on the integer factorization problem, which is a very well defined and understood mathematical problem. This problem must be solved in order to fundamentally break RSA.

What about AES (and others based on the same idea)?
Why is it difficult to break?
Is there any mathematical principle that ensures its security?

AES is deemed secure because:

Its building blocks and design principles are fully specified.
It was selected as part of an open competition.
It has sustained 15 years of attempted cryptanalysis from many smart people, in a high-exposure situation, and it came out relatively unscathed.

Another reason, which is not as good but felt important by many people:

It was designed by non-American cryptographers.

In asymmetric cryptography we often (try to) reduce security to a "known hard problem", a luxury which is not often encountered in symmetric cryptography, but this does not change the conceptual root of the issue: at some level, there is some "problem" for which no efficient solving algorithm is known, despite decades of research. It is not proven that the problem is necessarily hard, or even that there can exist such as thing as a necessarily hard problem, but we are just stumped when it comes to finding a solving algorithm. With AES, the "hard problem" happens to be the AES itself.


How to find a primitive cube root of unity I would like some help to understand how to compute a distortion map and the result of a pairing.

I know that with this equation :
$E : y^2 = x^3 + 1$ over some $\mathbb{F}_p$  we have a distortion map $\phi(x,y) = (\beta x, y)$.
I know that I need to find a primitive cube root of unity $\beta$ such that $\beta^3 = 1$ and it will give me a point in $\mathbb{F}_{p^2}$ with the form $a+bi$ with $ a,b \in \mathbb{F_p}$
But I don't know how to compute this $\beta$.
Could you explain to me how to compute $\beta$ with a small example.

The paper "Pairings for Beginners" shows this example, how does he find $24i+29$ ?

Thank you for your answers

Show the following.

For any prime $p \ne 3$, we have $p^2 \equiv 1 \pmod 3$, and thus a primitive $3$rd root of unity exists in $\mathbf F_{p^2}$.
Assuming $p^2 \equiv 1 \pmod 3$, for any $x \in \mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a $3$rd root of unity, and moreover, all $3$rd roots of unity can be obtained in this manner.
Given a $3$rd root of unity, it is easy to check whether it is primitive.
If $x$ is chosen uniformly from $\mathbf F_{p^2}^*$, $x^\frac{p^2-1}3$ is a primitive $3$rd root of unity with probability $2/3$.


What is a cryptographic "salt"? I'm a beginner to cryptography and looking to understand in very simple terms what a cryptographic "salt" is, when I might need to use it, and why I should or should not use it.
Can I get a very simple and clear (beginner level) explanation?
If you know of any references on the topic, those would also be useful.

The reason that salts are used is that people tend to choose the same passwords, and not at all randomly. Many used passwords out there are short real words, to make it easy to remember, but this also enables for an attack.

As you may know, passwords are generally not stored in cleartext, but rather hashed. If you are unsure of the purpose of a hash-function, please read up on that first.

Now, what the attackers can do is to simply generate a list of common passwords and their corresponding hashes. Comparing the hashes that a site has stored with the table will, if common passwords are being used, reveal the passwords to the attacker.

A salt is simply added to make a password hash output unique even for users adopting common passwords. Its purpose is to make pre-computation based attacks unhelpful. If your password is stored with a unique salt then any pre-computed password-hash table targeting unsalted password hashes or targeting an account with a different salt will not aid in cracking your account's password. A long randomly generated salt (using /dev/urandom) is expected to be globally unique. Thus salts can be used to make pre-computation attacks totally ineffective.

The simplest way to combine the salt and the password is to simply concatenate them, i.e. the stored hash value is Hash(salt||password). The common password password1 now magically becomes, e.g., 6$dK,3gCA%Jpassword1 which is unlikely to be found in a password cracker's table.

The salt can be stored completely in the clear in the database, next to the hashed value. Once the attacker has the database and wants to find the passwords, he needs to generate the pre-calculated table for each salt individually, a costly operation.

Another way to help defend against offline password cracking is to perform password stretching, ie. making a password hash slower to compute for any person, including the log-in service and password crackers. One method used to stretch passwords is achieved by iterating the hash-function many times, i.e. storing Hash(Hash(Hash(Hash…(Hash(salt||password)))…).

Another common idea related to salting is called a pepper. That is, another random value concatenated to the password, such that the stored value is Hash(pepper||salt||password). The pepper is then not stored at all. Both the login server and password cracker need to brute force the unknown pepper value, slowing password hash comparisons for both parties.

From 2013 to 2015 a password hashing competition was held to search for a better password-stretching algorithm. The winner was the Argon2 algorithm. Programmers are recommended to use Argon2 instead of implementing their own algorithm.


Is it possible to find a preimage for a reduced size hash? Given a message $M$ and a 256 bit key $K$, perform HMAC($K$, $M$) with a 256 bit hash function resulting in:

$a$ = 9a58e0eef2effc968d27cd61c47394867ceae43c7a877d59938f8400fe1a0204

Now take every second hexadecimal symbol resulting in a 128 bit hash:

$b$ = a80e2fc6d7d14346ca4ca7d93f40ea24

Assume the attacker knows the HMAC hash function.

Knowing only $b$, is it possible to find a preimage for $M$ or $K$?
Knowing only $b$, to find the original $K$ or $M$,
does an attacker need to repeat the same process (HMAC($K$, $M$) + taking every
second symbol) and perform a brute force search with 2256 different keys to match the hash back to $b$? Or is there a faster way?

We don't really know exactly how hard it is to find preimages of most cryptographic hash functions. Even for MD5 it is only "easy" to create collisions, while finding preimages is still considered "hard".

That said, we can apply statistical tools to estimate a "worst case", if we assume a random oracle for the hash function. In this case, we need in average $2^{255}$  tries to find a preimage to a 256 bit hash. Now, if we are looking only for a partial match (only 128 bits, it doesn't really matter which ones), we can estimate a match in average at $2^{127}$ tries.

Now, hash functions take an arbitrary input and map it to a fixed size output. There are no "preimages for M or K", there are just preimages (an input which maps to the same hash value). So once you found a preimage, you have this input. If the HMAC scheme requires a certain format of the input values for key, message and possibly other information, then you should only test inputs which fit this format.

To your second question: The attacker can not distinguish between the original message/key and any other preimage, if he has only the hash value (since they are the same). This might only be possible with additional information about the message: For example if the message is composed of English words in UTF8, preimages of random bits are not a "wrong preimage". However, in this case he would not even try this random input.

In general, the difference between HMAC and a cryptographic hash function is not that big. The difference becomes important, if the message is chosen from a small set of possible messages. In this case, the attacker can not just test all possibilities and find the real one, but he would have to test all messages with all keys (which should be larger than the hash value space). But in average, he will still find a preimage in 2^{k-1} tries for a k-bit hash value.

As final note: While $2^{127}$ possibilities is too much to brute-force, the security of this reduced hash value is less than the original one. Each ignored bit of the hash value cuts the complexity of finding a preimage by brute force into half. If you consider cutting down to something like every 4th bit of a 256 bit hash value (or any other fixed 64 bits of it), you get into the "possible to find with today's tools"-range. You have to ask yourself if this is worth saving a couple of bits for a potentially longer message, especially if you consider the other message overhead (e.g. IPv4 and TCP headers are each 160+ bits)


Countermeasures to prevent integral cryptanalysis against 4-rounds AES Integral cryptanalysis against 4-rounds AES is practical (Security of the AES with a Secret S-box). I did two experiments in order to find the impact and remove the integral distinguisher  of 4 rounds:

I replaced key addition $\oplus$ with $\boxplus$ (mod 32 bit)
I replaced the sbox with S1 Sbox in Clefia cipher  (same differential and linear probability).

but the integral distinguisher is still present.

Further reading lead me to find that BelT cipher (Finding Integral Distinguishers with Ease) has no integral distinguisher after three rounds.

Questions:

Where is the exploitable integral structure in AES-like?
What countermeasures are taken to remove integral distinguisher?
What is the advantage taken in BelT cipher?

This question may be theoretically interesting.

However, it looks to me strongly likely that the nice diffusion properties of AES using operations of order $4$ ShiftRows) and matrix ($4\times 4$) multiplication on vectors of dimension $4$ (MixColumns) are the reason for the existence of these attacks and changing these properties may well require more rounds for security.

The requirement that these operations be one-to-one, in the absence of a feistel structure, means that the SPN structure may also need to be dumped in order to avoid 4 round integral cryptanalysis.


Roots in modulo field I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ on the curve has two $Y$'s, one even and one odd. Therefore, we only need to store whether the corresponding $Y$ point we are storing is even or odd. So to store the point $(X,Y)$ now, we shift $X$ ridding of its most significant bit and add $1$ if the $Y$ point is odd. Therefore, one can think of the compressed point being $2 \cdot X+B$ ($B$ is the bit we added to tell if $Y$ was odd or even) since the multiplication by $2$ is implied because of the shift. I understand this completely. It's recovering the original point that has me confused.

Since a point on the curve is given by the equation $y^2=x^3+ax+b$, we can find square roots officially in $\mathrm{GF}(p)$. The following from my spec is what confuses me.

If $p$ is prime and congruent to $3$ mod $4$, one of its square roots is $z^{(p+1)/4} \bmod p$ and the other is $p-z^{(p+1)/4} \bmod p$. How would I solve this? What is $z$?

For example, I know how to extract the $x$ point so let's say I simplify the right side of the equation to be $7$ and $p$ is $11$. Would I be trying to solve for the square root that's equal to $7$ mod $11$?

You want to find a point $(X,Y)$ on an elliptic curve $y^2 = x^3 + ax + b$ knowing only $X$ and a single bit indicating whether $Y$ is even or odd. To find $Y$, you use the relation defining the curve: you know that $Y^2 = X^3 + aX + b$ since the point is on the curve. So you compute $X^3 + aX + b$ using your value of $X$ and the public parameters $a, b$, and you want to find values of $Y$ such that $Y^2$ is equal to that value.

If the modulus $p$ is congruent to $3$ mod $4$, that's very easy to do: for any $z$, the square roots of $z$, if they exist, are $\pm z^{(p+1)/4} \bmod{p}$. Indeed, suppose $z$ has a square root, say $a$. Let $g$ be a primitive root mod $p$, and let $a = g^x$. Then $z = (g^x)^2 = g^{2x}$. In turn,

$$(z^{(p+1)/4})^2 = z^{(p+1)/2} = (g^{2x})^{(p+1)/2} = (g^x)^{p+1} = (g^x)^{p-1}g^{2x} = g^{2x} = z$$

which shows that $z^{(p+1)/4}$ is indeed a square root of $z$.


Which concrete applications benefit from Oblivious RAM constructions? The main motivation for Oblivious RAM (ORAM) is that, for instance, in the "cloud" setting a client outsources his data to a server in the form of encrypted blocks. Later on, he wants to perform read and write operation on these encrypted blocks, which apparently may leak information about what data is stored. ORAM now ensures that the server cannot tell which blocks the client is interested in and whether he is reading or writing.

My question is: Are there any concrete examples/attacks, where the access pattern on encrypted data leaks sensitive data?

There is a new paper on the topic, the paper is not publicly available yet; however, its slides are available at David Cash, Paul Grubbs, Jason Perry, Tom Ristenpart - Leakage-Abuse Attacks against Searchable Encryption
.

A short summary of the talk is available at Seny Kamara - Workshop on Encryption for Secure Search & Other Algorithms:

  David Cash also discussed inference attacks. In addition to standard inference attacks, however, he also described attacks where the adversary exploits more than leakage and, in particular, knows or chooses some of documents.  The findings were very interesting. One thing that came out of this study was that the IKK attack—while very interesting in theory—is not really practical. There are several technical reasons for this but I’ll leave you to read David’s paper when it appears if you are interested. This study also looked at a new class of schemes (not SSE/structured schemes) that have appeared in the literature recently and showed that they were vulnerable to adversaries who know and/or can choose documents (though to be fair they were not designed with that adversarial model in mind).


ECC encryption in practice I'd like to encrypt a message using PGP keys, and elliptic curve cryptography as the method.

In practice, using the Erlang :crypto module, but first, I'd like to wrap my head around how I would begin to go about this.

Should I generate an ECC PGP key?
Should I use my normal PGP key and sign using :crypto module using ECC as the method.. if that is possible that is.

Any pointers in the right direction would be appreciated.

First time poster in Cryptography, BTW.

The programming aspect of this question should be asked on StackOverflow, but I suppose you can figure it out all on your own.

Yes, you need to generate ECC keypair if you want to use ECC algorithms. Every type of public-key cryptography suite require specifying algorithms, if your PGP keys are already using ECC algorithms (ECDH, ECIES, ECDSA), then you may reuse those depending on software support as not all libraries and apps support all formats (there are SSH, PKCS-PEM, PGP formats from what I know).

Also note that you should generate different keys for different purpose - don't reuse encryption key for digital signature and vice-versa.


How difficult is it to crack sha256(sha256(pin)) with a 6 digit pin and no salt? My friend forgot the password to his electrum wallet but knows that it's a 6 digit pin. I looked into it and from what I can find electrum uses the sha256(sha256(pin)) to generate the key used to encrypt the private key with AES in CBC mode. What I'm not sure about is whether or not it is feasible to crack this and I want to be sure before I attempt it.

Yes, it is possible to do this. You can just try each and every PIN, decrypt and then verify the private key; i.e. try a brute force approach. If you don't know the format, the toughest thing will be to think of a way to verify that the result is indeed the private key.

With 6 digits there is a maximum of $10^6$, i.e. a million times SHA-256, SHA-256 and then AES decrypt to try. You can just test part of the encrypted private key but with a million options I would not even bother and simply decrypt the key.

You should be able to pipe the result of CBC decryption to the Posix file utility, if it results in anything but unknown data you probably have a private key to test. Beware that the ciphertext may be prefixed with an IV, although if the salt is missing I would be surprised if it was present.


Can MFA codes be predicted if you know what their values were at a previous time? I use an app on my phone that, after scanning a QR code on a website, gives me 6-digit codes which change every 30 seconds. These codes can be used for Multi-Factor Authentication (MFA) on some websites, often in lieu of SMS codes or in-app login confirmations.

Presumably these codes are generated based on the shared secret that only I and the website provider both know - that QR code I initially scanned when setting up the MFA. The idea, as I understand it, is that without that original code you are unable to calculate the 6-digit MFA code that is valid during any given 30 second time period.

I am curious, however. What if an attacker has gained keylogger access to a device I use and is able to regularly capture the value of these 6-digit codes; is it possible over time for the attacker to use this history of codes, along with the time they were used, to derive the original QR code I was given when I set up the MFA in the first place?

Essentially, do I need to occasionally rotate my MFA accounts?

[Is] it possible over time for the attacker to use this history of codes, along with the time they were used, to derive the original QR code I was given when I set up the MFA in the first place?

To answer this one needs to understand how TOTP (the standard in question works). Namely it essentially takes the current time 1 and the pre-shared secret from registration and feeds them into HMAC (usually HMAC-SHA1, but other hash algorithms are also supported) and then takes the returned byte string, converts it into an integer and essentially reduces it $\bmod 10^6+1$ (or however many digits you configured).

Now note that the weakest attacker goal is to predict whether you are generating these numbers at random for each time interval or are using TOTP (e.g. recovering the secret lets you do that). This is called PRF-security in cryptographic terms and luckily has been studied intensively for HMAC. The current best know security estimate for this is found in this paper. It states that one can only distinguish HMAC from a random function (Theorem 1) with probability $\varepsilon'=(2q+1)\varepsilon+q^2/2^c$ when doing $q$ queries (i.e. seeing $q$ different outputs) for a $c$-bit output. The $\varepsilon$ here is the security of the underlying compression function used by the hash function, which is usually assumed to satisfy PRF-security as well. Heuristically it can be assumed that $\varepsilon=q/2^c$ for a good hash function - which includes SHA1 and MD5 even to this day. Plugging things together we get $\varepsilon'\approx q^2/2^c$ and $c$ being 512 for SHA-1 this value is negligible for more than a human lifetime. Now this means that the intermediate TOTP output is indistinguishable from a random string for distinct outputs which means in turn that the codes are indistinguishable from random codes. This is what we wanted to show.

So you might be wondering what the hell all of the above means:

Distinguishing the MFA codes from a randomly chosen code is essentially impossible while the shared secret is unknown to an adversary (even knowing the input time).
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict any future or past unseen codes.
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict the shared secret obtained through the QR code.

  Essentially, do I need to occasionally rotate my MFA accounts?

As explained above, no you don't.

1:Actually it takes the current time minus the unix epoch divided by the base interval duration, e.g. 30s.