How does the length of the plaintext affect the cipher strength? Let the block length 64-bit, 256-bit key, cipher text accordingly - 64 bits. What is the strength of the block cipher, if any unknown attacks, which could reduce its strength. We can only brute force.

Let $M=\{0,1\}^{64}$ be the plaintext space, $C=\{0,1\}^{64}$ be the  ciphertext space and $K=\{0,1\}^{256}$ be the keyspace. Then:

$\forall m\in M\ \exists\ k_1,\dots,k_n\in K \colon E(m,k_1)=\dots=E(m,k_n)=c$.

That is, for fixed message and some keys.

How can we use this fact to reduce the cost of a brute force attack?

I'm still a little unsure what your question is, but I'll try and answer what I think you're asking. If it isn't, please clarify your question or comment below.

Let us assume that $E_k$ is an ideal block cipher$^{[1]}$, and so acts like a random permutation of $2^{64}$ elements.

  Given $(m,c)\in M\times C$ find $k\in K$ such that $E(m,k)=c$. How long will this take?

In total there are $2^{64}!$ permutations of $2^{64}$ elements, but we are only interested in the ones that map $m$ to $c$. As such, we are actually looking at how many ways there are to permute the remaining elements, so there are $(2^{64}-1)!$ permutations.
 So, of the $2^{64}!$ permutations we expect $(2^{64}-1)!$ will map $m\to c$, meaning we expect that
$\frac{(2^{64}-1)!}{2^{64}!}=2^{-64}$ of keys will be suitable. So, it should take around $2^{64}$ key guesses.

  Given $(m,c)\in M\times C$, how many $k\in K$ are there such that $E(m,k)=c$

Since there are $2^{256}$ keys, and we expect to find a suitable $k$ with probability $2^{-64}$ trials, we expect there to be $2^{256-64}=2^{192}$ possible keys.

  So, how many trials should it take to find the correct key?

The important thing to notice here is that, no matter how many trials you run, with just one plaintext-ciphertext pair there will still be lots of false positives, and you will have no way of knowing which is correct. The obvious solution to this is to take more $(m,c)$ pairs, but how many? Suppose we have $n$ distinct $(m,c)$-pairs. Then, a false-positive key must fix these $n$ points, leaving it a permutation of $|M|-n$ points. Following the same logic as above, that means the probability of hitting a false-positive key is
$$P = \frac{(2^{64}-m)!}{2^{64}!}
    = \frac{1}{2^{64}\times (2^{64}-1)\times\cdots\times(2^{64}-m+1)}
$$
We want $P\ll2^{256}$, since at this point we can reasonably assume that even in all $2^{256}$ keys there isn't a false positive. As such, $5$ pairs would be sufficient.

I leave it to the reader to consider how long such an attack would take$^{[2]}$.

The assumption on $E_k$ is an ideal cipher is important. For example, the function given below certainly cannot be modelled as a random permutation, but finding a preimage pair $(m,k)$ is trivial for any $c$.
$$E(m,k)=\begin{cases}
  m & k=0
\\0 & k\neq0
\end{cases}$$
Hint: If $E(m_1,k)\neq c_1$, then we do not need to calculate $E(m_2,k)\stackrel{?}{=}c_2$. So, how many times do we calculate $E(m_2,k)$? How about $E(m_3,k)\ \dots$


Improving the security of this tag So we have the protocol:

$Bob \to Alice \Rightarrow m\ ||\ h(m, ``secretTag")$

With above scenario, a message is passed to Alice with an authentication tag to prove that the message was sent by Bob.

What is a better way of doing the tag? How could I incorporate a key into this?

A suggestion has been to use Digital signatures or HMAC, how are these better?

Please read the article on HMAC. What you are trying is exactly what is described in the chapter design principle:

  The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with $MAC = H(key ∥ message)$. However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC ("length-extension attack"). ...

There are only two differences to your idea:

Reverse the order of message and key/tag
The idea of having a "tag", where I can only assume it is the usual case as with passwords: Low entropy, unsuitable to be used as a cryptographic key.

So basically you should just use HMAC (if that fits your needs), but put your tag into a password-based key derivation function first, e.g. PBKDF2, scrypt or bcrypt. That key can then be used for HMAC.

Digital signatures on the other hand also offer non-repudiation, and HMACs don't because both the sender and the receiver know the same symmetric key and thus could both have created the HMAC.


Encryption Oracle Avoidance I have a case where it may be possible for an adversary to deduce the plaintext inputs that went into creating a AES-128-GCM encrypted message (there is good IV diversity across the encrypted messages, however)
This opens up the potential to expose a GCM "oracle" to the adversary who may additionally be able to adaptively modify the inputs to the encryption function and observe the GCM encrypted outputs. I'm thinking about adding a random string of bytes of some fixed length to each encrypted message in order to prevent this (since an attacker would no be able to guess the random bytes that were appended and would therefore not know the full plaintext for a corresponding ciphertext). Some questions:
1) Can someone provide a "rule of thumb" around how much randomness should be appended to each message of a given length.
2) Does one need to take particular care around how the random byes are added an removed from the message
3) Are there any other methods one can employ in order to avoid exposing the encryption "oracle" described above?

GCM is authenticated encryption. As such, it is secure against chosen-plaintext attacks and against chosen-ciphertext attacks. Thus, there is no problem whatsoever with the adversary having access to an encryption oracle. It will not help it at all to break any of the encrypted messages.


Is solving a modular linear equation a hard problem when the coefficient is not an invertible element? Assume that we have a linear equation like this:

$$ax=b \pmod n$$

when $x$ is the unknown, and $a$ is not an invertible element in $n$.

is finding $x$ a hard problem?

(by solving I mean finding an $x$ that satisfies the equation)

Calculate $g = GCD(a, n)$ and $n^\prime = n / g$. If $b \not\equiv 0 \pmod g$, then there is no solution.

Divide whole equation by $g$ giving you $a^\prime· x_0 = b^\prime \pmod{n^\prime}$ and solve for $x_0$. Then solutions for $x$ are $x_0 + k· n^\prime$ for $k = 0, 1, ..., g-1$.


What is a cyclic group of prime order q such that the DLP is hard? On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this:

  Let $G = \langle g\rangle$  be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : \{0, 1\}^∗ \to \mathbb Z_q$ and $H_2 : \{0, 1\}^∗ \to G$ be distinct hash functions viewed as random oracles.

What, specifically, is that group he mentions? Are there many ways to construct such a thing? If so, is there any that is easy to implement, yet hard to attack? Or am I looking for some kind of library? Moreover, how should one make such an $H_2$ that can be viewed as a random oracle?

Cyclic group of prime order q such that the DLP is hard

A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) hard, applicable to large $q$ (in the order of a thousand bits), is to pick $q$ as a random prime of appropriate size such that $p=2q+1$ is prime, and random any integer $g$ with $1<g<p-1$ such that $g^q\bmod p=1$.

The $q$ elements of the cyclic group $G$ are $g^i\bmod p$ with $0\le i<q$, under modular multiplication modulo $p$.

The search of $q$ can be greatly sped up by using sieving techniques removing $q$ such that either $q$ or $2q+1$ is divisible by a small prime. The search of $g$ is fast as is (on average two attempts are enough; it is common to use $g=2$, and towards that goal pick another $q$ and $p$ if $g^q\bmod p\neq1$).

It is conjectured that the DLP is hard, that is: given $y=g^x\bmod p$ for unknown random $x$ in $\mathbb Z_q$, it is computationally infeasible to find $x$. The current public record for solving such problem is for one instance of a 768-bit $p$. Current recommendations for a decade of security are 2048 or 3072 bits, but 1024 bit is still widely used. Standard groups with $p$ of a slightly special form making modular reduction easier are given in RFC 2409 and RFC 3526.

One way to obtain a speedup without sacrificing security (conjecturally) is to reduce the size of $q$, within some limit, with $q$ a divisor of $p-1$. That's a Schnorr group. See section 3.6.6 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, and their algorithm 11.54. Using a 256-bit $q$ for 2048-bit $p$ is believed to be about as safe as using a 2047-bit $q$, and recommendable. 160-bit $q$ is often used when $p$ is 1024-bit. Execution time is about in proportion to the bit size of $q$, and roughly in proportion to the square of the bit size of $p$.

Slowness is a often concern! Common algorithms to compute $y=g^x\bmod p$ perform like $3(\log_2(p)/w)^2\log_2(x)$ multiplications of $w$-bit words and additions of the $2w$-bit result. For a software implementation using 32-bit words, 2048-bit $p$ and 2047-bit $x$, we are talking over 25 million muladds. Careful implementations using assembly language shine, including the GNU Multiple Precision Arithmetic Library (which has wrappers in interpreted languages, including gmpy2). Also: be aware that side channel leakage, including by timing, is a security concern depending heavily on the implementation of modular exponentiation.

There are other constructions using an Elliptic Curve over a finite field, giving another large speedup without sacrificing security (conjecturally); and yet other less common techniques. In the following I'll stick to a $G$ a subgroup of $\mathbb Z_p^*$ of prime order $q$, with $p=r\cdot q+1$; and to $r=2$ (the simple technique discussed initially) unless otherwise noted.

Construction of H1

What's wanted is a hash with output in $\mathbb Z_q$, (conjecturally) secure in the random oracle model (that is: computationally undistinguishable from a random function with the same input and output domain, knowing the definition of $H_1$ except some arbitrary constant part of that public definition).

One problem is, usual cryptographic hashes have limited width; the widest in common use is SHA-512, and a 2047-bit $q$ is nearly 4 times as wide. If we processed the message $\alpha\in\{0, 1\}^*$ using SHA-512, no matter how we post-process the result, a negligible fraction of the elements of $\mathbb Z_q$ would be reachable (less than $2^{-1534}$); and in order for $H_1$ to be secure in the random oracle model, it must be computationally impossible to recognize elements in $\mathbb Z_q$ belonging to that fraction. Another issue is that usual cryptographic hashes have each of their output bits about evenly distributed for random input, but a random element of $\mathbb Z_q$ expressed as a bitstring of same size as $q$ has its high-order bit quite biased towards 0, unless $q$ is just below a power of two.

We can solve the size problem by concatenating several independent hashes, which we can obtain using HMAC-SHA-512 with different public arbitrary keys; and one method to approximate the right distribution in $\mathbb Z_q$ (beyond computational detectability) is generating at least (say) 128 more bits than in $q$, followed by modular reduction modulo $q$ (assimilating bitstrings to integer per big-endian convention).

With that method and $q$ of 2047 bits, we need $\lceil(2047+128)/512\rceil=5$ concatenated HMAC-SHA-512. For message $\alpha\in\{0, 1\}^*$ the hash could be
$$H_1(\alpha)=\big(HMAC(\text{0x01},\alpha)\|HMAC(\text{0x02},\alpha)\|\dots \|HMAC(\text{0x05},\alpha)\big)\bmod q$$

Note: when using $q$ of up to 384 bits, which is fine if $p$ is still large enough, we won't need the complexity of concatenating multiple hashes.

Construction of H2

What's wanted is a hash with output in the group $G$ constructed in the first section, (conjecturally) secure in the random oracle model. But there's a catch!

The quote in the question precisely matches section 3.1 of Joseph K. Liu and Duncan S. Wong's Linkable ring signature: security models and new schemes, in proceedings of ICCSA 2005, which I located by asking Google Books for distinct hash functions viewed as random oracles. Right after the question's quote is:

  Assume that for any $\alpha\in\{0, 1\}^*$, the discrete-log of $H_2(\alpha)$ to the base $g$ is intractable.

The reasonable way to interpret this additional requirement is that knowing the definition of $H_2$, and given $\alpha$, one should be computationally unable to find $x$ with $g^x=H_2(\alpha)$.

Adapting Poncho's great suggestion so that it works regardless of $r$, for 2048-bit $p$ we can use
$$H_2(\alpha)=\Big(\big((HMAC(\text{0x11},\alpha)\|\dots\|HMAC(\text{0x15},\alpha))\bmod(p-1)\big)+1\Big)^r\bmod p$$

This works by generating a random element $u$ of $\mathbb Z_p^*$, and computing $v=u^r\bmod p$. The result is in $\mathbb Z_q$, because $v^q\equiv{(u^r)}^q\equiv u^{rq}\equiv u^{p-1}\bmod p\equiv 1\pmod p$, with the last step using Fermat's little theorem. With $u$ essentially uniform on $\mathbb Z_p^*$, $v$ is essentially uniform on $G$.

I wish I had proof of my intuition that, for general $r$, solving  $g^x\bmod p=v$ for $x$ is hard including with knowledge of $u$; and that we could get away with generating $u$ in $\mathbb Z_q^*$ rather than in $\mathbb Z_p^*$. Poncho proved both for $r=2$.

Words of caution: Many papers on ring signatures and e-voting that I have attempted to follow have lost me; I was often left wondering what exactly is assumed and proven about security, and what that means in practice. Some use a bilinear pairing; while there are libraries for that, I advise to dive into this stuff only if all the math above has been striking one as evidence.

I'm sure that only a small fraction of the voting population can form an informed opinion on these topics. I conclude that using such methods for voting goes straight against a major goal: that voters trust the result.


Can you use a hash as a password? There are several methods of making a strong password, making it longer is one of them. now we also have hashing algorithms which have outputs of 512,
so i wonder, would it be safe to basiclly use a simple password like dog, and then use the for example 512 bit hash output as the password.

EDIT: out off all the answers i think i thought out something that would be secure so consider the following: if i write a program which hashes a word with a number that comes out of a cryptographiclly secure pseudorandom number generator(having a minimum of 5 hashes, and then use the out put as a password, for example: i use the word dog as word, then number generator provides me with a random number of 5 or higher which defines how many times it needs to be hashed. in this case, we got the numer 30 for example, then we hash the word dog 30 times with a secure hash function. then this would be a secure password against dictornary attacks right? because if they dont know how many times you hashed it, then trying a dictornary attack should become a much harder task to achieve, and for brute force: trying to crack  a 512 bit password with letters and numbers should be madness, and if you use a salt along side of it, it should become really secure. so if someone is able to write something like this, and combine it with a secure and encrypted password vault, then it should be a pretty powerfull tool for password creation and management. so this is basically the idea, feel free to point out things i missed or possible weaknesses :)

I'd say the key thing that you need to spell out to answer this question is this:

What information does the attacker have?

This ties to one of the basic concepts of cryptography, called Kerckhoffs's principle: "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."  (I recommend you read that page and take its lessons to heart, along with the security through obscurity entry as well.)

So if we apply Kerckhoffs's principle to your proposal, we would assume that:

The attacker knows that your password is the hash of some secret word that you choose, but not which word;
The attacker knows which hash function you used to hash this word, and how to compute this hash function.

Then we trivially conclude that this isn't any safer than just using the word as the password.  And since "dog" is a very common word in the English language, it's an obvious one for an automated attacker to try.

I'd say that in your question you are doing something that most laypersons do when they propose password rules or schemes like this one: you're assuming that the attacker won't know or guess the rule you're using to generate your password.  But:

You just told your idea to the whole Internet.
Even if you hadn't, there's a good chance that an attacker might think of the same idea.

So really, the best passwords are random passwords, because there's no rule that an attacker can use to predict them.

EDIT: Funnily enough, a few days before this question, Duo Labs published a security analysis of OEM PC software updaters (press release; PDF report), that contains this gem (p. 16):

  Unfortunately, the encryption utilized is RC4 with the pre-shared key “e8fded24af79202d7da48adefe4a3a04”, which is the MD5 hash for “Asus Live Update.” As this layer of encryption boils down to simple obfuscation that can be dealt with on the fly, it provides no security value.

This is almost perfectly analogous to the question's proposal:

Pick a secret passphrase ("Asus Live Update");
Hash it with a standard hash function;
Use the resulting hash value as an encryption key.

And yet the researchers, just from seeing the hashed value, managed to guess the passphrase and the hash function used to obfuscate it.  So there we have it, a documented real-life failure of the strategy.


3DES CFB vs CFB8 modes What is the main difference between CFB and CFB8 modes in 3DES?  Is it only a change in block size from standard 8 byte to 1 byte when doing 3des and XOR? I cant find any pseudocode for this CFB8 mode?  any pointers?

The main difference between CFB-1(CFB) and CFB-8 is the size of shifting.
To understand this -
$C_i = top_x(res_{i-1})\oplus P_i$
$res_0 = Enc_k(IV)$
$res_{i} = Enc_k(shift_x(res_{i-1}\oplus P_{i-1}))$
$P_i = top_x(res_{i-1})\oplus C_i$
Note that in order to decrypt $C_i$, you will need $P_{i-1}$ which can only be found by decrypting $C_{i-1}$. Hence, this cannot be parallelized.
Here $x$ is the shift size which is 1 in CFB-1 and 8 in CFB-8.


A generalisation of Shannon's theorem of perfect secrecy The proof I'm struggling with is the following:

Let $\mathcal{E}$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, \mathcal{E}] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, \mathcal{E}]$ of an adversary $A$ (in a standard attack game) over cipher $\mathcal{E}$ is defined as:

$SSadv[A, \mathcal{E}] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, \mathcal{E}] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are trying to prove is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

Assume for the sake of contradiction that $|K|<(1-\epsilon)|M|$. We will define an adversary which has semantic advantage greater than $\epsilon$. Let $S=\{D(k,c)|k\in K\}$, where D is the decryption function of our cipher $\mathcal{E}$. We define our adversary A with the following characteristics:

$m_0,m_1\in M$ are chosen randomly
The predicate $\phi$ is chosen randomly with equal probability from either $\phi_1$ and $\phi_2$, which we define below
If $m_0\in S$ and $m_1\not \in S$, then $\phi_1(c)=\phi_2(c)=0$.
If $m_0 \not \in S$ and $m_1 \in S$, then $\phi_1(c)=\phi_2(c)=1$.
If both $m_0$ or $m_1$ are in S, then $\phi_1(c)=1$ and $\phi_2(c)=0$

(Note that while such a predicate function exists, it might not be an efficient one, ergo the part of the problem statement allowing for computationally unbounded adversaries.)
We have the following:
$$Pr[φ(E(k, m_1))]=Pr[\phi=\phi_1]Pr[m_0 \in S\; \text{and } m_1\in S]+Pr[m_0\not\in S \text{ and } m_1\in S]$$
$$Pr[φ(E(k, m_0))]=Pr[\phi=\phi_2]Pr[(m_0 \in S\; \text{and } m_1\in S)]$$
Note that both probabilities are implicitly conditioned on S, which depends on the message the challenger encrypts and sends to the adversary. Also, $Pr[\phi=\phi_1]=\frac{1}{2}$, since we chose our predicate function randomly. Moreover, in the first case $E(k,m_1)\in S$ trivially, and in the second case $E(k,m_0)\in S$, yielding that
$$Pr[φ(E(k, m_1))]=\frac{1}{2}Pr[m_0 \in S]+Pr[m_0\not\in S]=\frac{1}{2}\frac{|S|}{|M|}+1-\frac{|S|}{|M|}$$
$$Pr[φ(E(k, m_0))]=\frac{1}{2}Pr[(m_1\in S)]=\frac{1}{2}\frac{|S|}{|M|}$$
So that $SSadv[A, \mathcal{E}] = 1-\frac{|S|}{|M|}$. Now $|S|\leq |K|$ by definition, and so by our assumption at the beginning $|S|<(1-\epsilon)|M|$. Therefore, $SSadv[A, \mathcal{E}]>\epsilon$, which is a contradiction, meaning that $|K|\geq (1-\epsilon)|M|$ as desired.


MD5 theoretical question Ok, so this is a very possible stupid question, but one of those things that has sat at the back of my mind for a while.

We all know that MD5 has issues, and these have been known for about a decade.  So this is theoretical.  I'm not considering using it for anything.

Question is this.  If MD5 generates a 32 digit number in hex, given that 32 is finite, and we can hash longer and longer values, didn't we know from the offset that MD5 had to have collision issues?

Basically all hash functions have this "problem". Pretty much all are finite in length.

The real problem happens when collisions can be generated in less work than brute force. Due to the birthday problem with an $n$-bit hash function we would expect to see a collision after computing $n/2$ digests. If $n$ is large enough (say $n=160$) we would not expect any realistic adversary to be able to generate collisions.

A hash function is broken when someone can demonstrate collisions in fewer than $n/2$ operations.


openssh ed2215 private key format i have generated an ed2215 private key as follows:

$ ssh-keygen -o -a 100 -t ed25519 -f id_ed25519

and it looks like

-----BEGIN OPENSSH PRIVATE KEY-----
...
-----END OPENSSH PRIVATE KEY-----

where ... is truncated data.

although it feels like base64, i see that each truncated line has at most 64 characters, where regular base64 encoding does not hold that charactristics.

what is the format (or encoding) of the private key? (if i have the private key in byte array, which transformation do i need to apply before i write it to a file that coincide with openssh output)

although it feels like base64, i see that each truncated line has at most 64 characters

It is base64 encoded. Remove the -----BEGIN OPENSSH PRIVATE KEY----- and -----END OPENSSH PRIVATE KEY----- and the new lines ("\n") and then you can parse as per
https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/PROTOCOL.key?annotate=HEAD . Quoting that file:

This document describes the private key format for OpenSSH.

1. Overall format

The key consists of a header, a list of public keys, and
an encrypted list of matching private keys.

#define AUTH_MAGIC      "openssh-key-v1"

    byte[]  AUTH_MAGIC
    string  ciphername
    string  kdfname
    string  kdfoptions
    int number of keys N
    string  publickey1
    string  publickey2
    ...
    string  publickeyN
    string  encrypted, padded list of private keys

2. KDF options for kdfname "bcrypt"

The options:

    string salt
    uint32 rounds

are concatenated and represented as a string.

3. Unencrypted list of N private keys

The list of privatekey/comment pairs is padded with the
bytes 1, 2, 3, ... until the total length is a multiple
of the cipher block size.

    uint32  checkint
    uint32  checkint
    string  privatekey1
    string  comment1
    string  privatekey2
    string  comment2
    ...
    string  privatekeyN
    string  commentN
    char    1
    char    2
    char    3
    ...
    char    padlen % 255

Before the key is encrypted, a random integer is assigned
to both checkint fields so successful decryption can be
quickly checked by verifying that both checkint fields
hold the same value.

4. Encryption

The KDF is used to derive a key, IV (and other values required by
the cipher) from the passphrase. These values are then used to
encrypt the unencrypted list of private keys.

5. No encryption

For unencrypted keys the cipher "none" and the KDF "none"
are used with empty passphrases. The options if the KDF "none"
are the empty string.


AES CBC with fixed or predictable IV, what are the risks? I am making a call with parameters from application "A" to a web application "B".
Parameters are in the query string of the URL. They don't need to be hidden.
But I want to be sure that nobody can change the parameters.
And web application "B" must ensure that the query comes from application "A".

So, I encoded the parameters in AES with CBC. I know that HMAC is best for this kind of situation.
But AES with CBC is the only one algo that the 2 applications have in common.

The security of the system relies on the fact that nobody in application "A" can choose arbitrary plaintext to be encrypted
(to avoid request with modified parameters). Parameters are not an input for the users.

I would like to know the risk if I use a fixed IV or a predictable IV?

It seems that the risk is a chosen plaintext attack.
With this article:
https://stackoverflow.com/questions/3008139/why-is-using-a-non-random-iv-with-cbc-mode-a-vulnerability,
I understand how chosen plaintext attack can lead to reveal the content of the ciphertext.
But I don't mind if the content of the ciphertext is discovered.

What are the other risks?

Can someone build unauthorized request?
CWE-329 says yes. But does that only imply the reusing and adaptaptation of blocks of older messages?
Or does the attacker can build his own request with whatever plaintext he wants?

Does the secret key can be discovered?
From Wikipedia it seems that chosen plaintext attack can reveal the secret key, but I don't understand how.

You are hoping to get integrity protection by applying CBC mode; the problem with this is that CBC mode isn't great at providing integrity protection.

One way an attacker can exploit this, if he guesses what the plaintext is, he could modify block N of the plaintext to anything we wants by changing block N-1 of the ciphertext.  This will modify block N of the resulting plaintext to be exactly what the attacker picked; this also has the side effect to setting block N-1 of the plaintext to be something random.  However, the attacker might not care about what block N-1 is (alternatively, he might just hope it results in an innocuous value).

Also, if an explicit IV is given (so that the attacker can freely modify it), he can modify the IV to make the resulting first block of the plaintext be anything he wants, without any other changes anywhere in the resulting plaintext.

Given that you do have a CBC mode primitive, the obvious thing to try is to implement CMAC; this would involve taking the plaintext message, padding it out, computing the CBC mode encryption of that padded message (with a fixed IV), and throw away the entire encrypted message except for the last block.  Then, you'd send the original plaintext message, along with that last encrypted block.  On the receiver side, it would take the received plaintext message, pad and encrypt it in exactly the same way, and see if that results in exactly the same last block.

The advantages of this approach is that it does give you real integrity protection (in that no one in the middle who doesn't know the keys can modify the message in a way that would not be immediately be rejected, except for deliberate replays); and it does all this using only a CBC primitive.


Break RSA given $N, e$ and lower half of $d$ I have full bits of public key $(n,e=65537)$ but from the private key, I have the lower half bits of $d$.

Can I restore the whole RSA private key from that data and use it for decryption?

If $e$ is small, and if you have $n/4$ least significant bits of $d$, then you can factorize $N$. The attack runs in time polynomial in $e, n$. You can have a look at Boneh Durfee Frankel attack Section 3. So, if $e$ is only 65537, then the attack is certainly feasible.


Can stream ciphers (usually) be "run backwards"? Is it possible to reconstruct the previous output bits of a stream cipher, e.g. RC4, when only the current state is known, or is that computationally hard, or even impossible (due to ambiguous preceding states)?

For Salsa, it's obviously possible, since that even allows for random access.

Is there a formal name for the presence or absence of that property ("backward secrecy")?

With RC4, the answer is "yes, you can efficiently run the cipher backwards, reconstructing previous states".

For stream ciphers, whether you can reconstruct previous states in not typically considered, however for cryptographically secure random number generators (which are a similar primitive), it does come up; the term I've heard is "Backtracking Resistance".

Now, there is one thing to be careful with "Backtracking Resistance"; if the reason you have backtracking resistance is because the function that transitions between the previous state and the next state acts like a random function, then it becomes easier to fall into a short loop than if the transition function is invertable; this is because the you run into a loop if the next state happens to be any of the previous states you have visited.  In contrast, if you have an invertible next-state function, the only state that you might revisit is the initial state.  Because of this increased tendency to fall into short loops, it's typically considered wise if you (at least) double the size of the internal state beyond what the security strength might indicate you would need.


double encryption - One Time Pad Can the security of the encryption system be improved by using double encryption with two randomly chosen keys?

By double encryption I mean using two keys K1 and K2, each 20-bit long, to obtain ciphertext $C = ( M ⊕ K_1 ) ⊕ K_2$.

The answer is we cannot improve the security of the one-time pad in this manner. Intuitively the reason is that the double one-time pad is just a less efficient one time pad.

The security of the traditional xor-based one-time pad is requires that the key $K$ is chosen uniformly at random for each message and that the key is at least as large as the message.

Because the xor operation is associative, we could re-write the double one-time pad as $C = M \oplus(K_1 \oplus K_2)$ or $ C = M \oplus K$, where $K = K_1 \oplus K_2$. Now if $K_1$ and $K_2$ are uniform, it is easy to show that $K$ is also uniform. Assuming the key and the message have length $n$

$P_K[k] = \sum_{x \in \{0,1\}^n}P_{K_1,K_2}[k_1 = x, k_2 = k \oplus k_1] = \frac{1}{2^n}$

In other words $K_1 \oplus K_2$ could be simply replaced by a single uniform key, therefore $K_1$ is enough. Moreover the double one-time pad is inefficient because it requires two xor operations.

Regarding cascade encryption, Maurer and Massey showed that cascade encryption is as strong as the first cipher. Matthew Green's blog post is a nice (easy to read) summary of multi-encryption security.


What does a "cycle" mean in cryptography benchmarks? In this table of the "Crypto++ 5.6.0 Benchmarks", for example, cryptographic algorithm performance is measured in cycles per byte for symmetric ciphers, and in cycles per operation for asymmetric ciphers.

What does "cycle" here mean, exactly? And does one AES or RSA decryption always need the same amount of cycles, or can it be different every time?  (If it's always the same number of cycles for a cipher, then the time needed to decrypt must always be the same for different ciphertexts.)

"Cycles" are CPU instruction cycles. Cycles per byte roughly measures how many instructions, in a given instruction set, are needed to produce each byte of output. They're a reasonably-good relative measure of the performance of different algorithms.

Generally, when you measure an algorithm's cycles per byte, you use carefully controlled conditions. You ensure the system isn't doing anything else, you ensure the code cache is populated, you try to avoid measuring memory speed, and so on.

Some ciphers are dependent on their data. To help control for this, you try to use a large data set and average it out.

You can't measure asymmetric ciphers this way, because they don't operate on bulk data. For them, it makes more sense to talk about cycles per operation, operations per second, or the like.

I noticed on that data set, they have a lower cycles per byte for SHA256 than SHA512. If they had used their CPU's 64-bit instruction set, the results would have been the other way around. So the results are heavily dependent on how the code is compiled (instruction set, optimizations, and so on).


What is the implication for differential privacy if $\epsilon = 0$? In pure differential privacy, the parameter $\epsilon$ represents the desired privacy loss. The smaller the $\epsilon$ is, the more privacy we can obtain. What happens when  we want the privacy loss $\epsilon = 0$. Does that mean we need to keep the data permanently private and we do not answer  any queries from outside ?

Thanks

Yes.

$\varepsilon$-differential privacy with $\varepsilon=0$ implies that the output of the mechanism must be independent of the input -- i.e., it provides no information whatsoever.


Affine cipher and plaintext attacks, how to find the base modulo? Last year, a question concerning plaintext attacks was posted at Mathematics.SE: “Plaintext attacks: affine cipher”.
I have no problem to see how to solve it when we are given two ciphertexts and $(c_1,c_2)$ and their corresponding plaintexts $(m_1,m_2)$. But, when I am to deal with the situation where $p$ is unknown it gets complicated. In this instance, I have three pairs of ciphertexts and plaintexts - $c_i \not =c_j$ for $i,j \in \{1,2,3\}$ and $m_i \not = m_j$ for $i,j \in \{1,2,3\}$. This differs then from the previous question in the sense that I cannot use the method that fkraiem provided given two of the ciphertexts are equal.

To find $p$:
You have $k_1m_1+k_2 \equiv k_1m_2+k_2 \equiv c_2 \pmod p$ so $k_1(m_1-m_2) \equiv 0 \pmod p$. This means that either $k_1$ or $m_1-m_2$ is a multiple of $p$ (this is where the fact that $p$ is prime comes in). $k_1$ can't be a multiple of $p$, because otherwise the encryption function is constant, which is absurd, so $m_1-m_2$ is a multiple of $p$.

Thus my question is this: How would one go about determine $p$ if the ciphertexts are all different?
I am not applying it to any exciting problem other than textbook style number problems.

Well, to start off with, we have:

$$k_1 m_1 + k_2 - n_1 p = c_1$$
$$k_1 m_2 + k_2 - n_2 p = c_2$$
$$k_1 m_3 + k_2 - n_3 p = c_3$$

Where we know $m_1, c_1, m_2, c_2, m_3, c_3$, and we don't know $k_1, k_2, p, n_1, n_2, n_3$.  I chose to use explicit unknown integers $n_1, n_2, n_3$, rather than modulo an unknown $p$, as it makes it easier to justify the operations we'll do.

The first step is to cancel out the $k_2$ unknown; if we take the first equation, and subtract the second equation, this gives us:

$$(k_1 m_1 + k_2 - n_1 p) - (k_1 m_2 + k_2 - n_2 p) = (c_1) - (c_2)$$

or

$$k_1(m_1 - m_2) - (n_1 - n_2)p = c_1 - c_2$$

Subtracting the second and the third equation gives us:

$$k_1(m_2 - m_3) - (n_2 - n_3)p = c_2 - c_3$$

The next step is to cancel out the $k_1$ unknown; to do this, we multiply the first equation by $(m_2 - m_3)$, multiply the second equation by $(m_1 - m_2)$, and then subtract the two.  Doing this (and performing algebraic simplification) results in:

$$((m_2 - m_3)(n_1 - n_2) - (m_1 - m_2)(n_2 - n_3))p =\\ (m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$$

Or, in other words, $p$ is a factor of $(m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$, which is composed entirely of known values (that is, we can compute it).

Hence, the solution is to compute that value, and if it nonzero, factor it, and go through the factors to search for plausible values of $p$.


Are Two Ciphers Better Than One? i.e. RC4 and AES OK It's cringe time (or hopefully not)

I know this is probably a variation of an old and dragged out question or so you may think but let me ask away and hopefully get some insight.

Google a while ago famously changed from AES to RC4 because of BEAST.
RC4 however, is riddled with all kinds of leaks and problems that are well studied. RC4 can reveal a lot of information to somebody who does not know the key. In theory this can be done. In practice this has been done. WEP being the example that springs to mind strongly.

If we use the same 128 bit key to form some kind of AES (block cipher) encryption. In any mode whatsoever, whether that's ECB or more advisably CBC, CFB or whichever (you get the idea). Then we also run the same data through the RC4 (stream cipher) algorithm: do we have a distinctly stronger, much harder to break cipher-text in effect?

It then goes without saying to decrypt, we just decrypt with RC4 then AES.

Would we solve any weakness issues this way? Or is this just a waste of computing time? Any thoughts really appreciated.

There exist several ways to combine multiple, distinct encryption schemes. Applying one after the other as you propose is one option but you could for example do a secret sharing first and then encrypt the shares with different algorithms. Each of those has its advantages and disadvantages. I am not aware of a combiner for this that provably amplifies security but you can manage to build a scheme that is guaranteed to be as strong as the weakest cipher used in the combiner (as long as you use independent keys of course). The drawback is obvious: You need to do about twice the work when combining two schemes and so on. Depending on the combiner you might also pay in bandwidth (See the secret sharing combiner). These are the reasons why folks hesitate to use this in practice although it would give far stronger long-term security guarantees if key sizes are chosen appropriately.


I don't understand Digital Signature Why did we call it digital signature if an attacker can pretend to be Bob?
Bob hashes his message, encrypts the hash with Alice's public key, and sends it to Alice with the original message. Alice receives that message and the signature. She decrypts the signature with her private key, and compares the outcome with the hash of the message.
But why did we call it a signature if a hacker can do what Bob has done?
A hacker can also hash his message, encrypt the hash with Alice's public key and send it to Alice. Sorry guys but digital signature seems similar to asymmetric encryption to me, a hacker can also pretend to be Bob.

bob hashes his message and encrypt it with alice public key

No, Bob would sign it with his own private key.  For some signature methods, this is roughly similar to "encrypting with the private key", however for other signature methods, it's not; hence it is safer to keep a strong distinction between 'signing' and 'encrypting'

alice receives the original message and the signature she decrypts the signature with her private key and she compares the original message with the signature

No, Alice would validate the signature with Bob's public key.  How Alice gets a verified copy of Bob's public key is an important part of this process, however that is generally considered something to be solved by the whatever mechanism is using the signature method.

Why did we call it digital signature if an attacker can pretend to be bob?

If the attacker does not have Bob's private key (and so he cannot generate sigantures that would verify with Bob's public key), and he can't fool Alice into using the attack's public key, the attacker cannot pretend to be Bob.


What is the harm if I publish an encrypted RSA private key publicly? What is the harm if I publish an encrypted RSA private key publicly?  Or in this case, what is the harm if I publish many thousands or millions of them?

Assuming that the private key is encrypted with a typical user password, the passphrase is some combination of password + user ID (which is not necessarily user-selected), some method of key stretching is used, and that it's not obvious what the key is used for, is there any harm?

The reason I ask is because I am wanting to investigate a way to store public and private keys on behalf of web users for use within a web browser.  The private key would be stored at an HTTPS URL that does not describe the user that owns it nor describes what the key would access.  The data stored at the private key URL would be read-only.

The intention is to assume that any private keystore would be eventually attractive enough to be attacked and breached and therefore assuming that keeping the private key files hidden or protected would be poor or insufficient security.

The fact that this private keystore exists would not be treated as private information.  All keys would be accessible by anyone that knows the URL for each.  There would be no key/directory index provided.  The key files may be stored on simple file storage/hosting systems like Amazon S3, but they would always be served over HTTPS.

Please ignore the issue of possible theft of password via keylogging and ignore the issue of possible theft of unencrypted key via direct JavaScript access.

Systems like ssh, for example, often encrypt a user's private key using a password, so that is not new. The fact that they are published on a web server that technically anyone could access is a little different. But, if the password is strong, brute force and dictionary attacks would be impossible. So the system seems secure.

That if, though, is a big if. As CodesInChaos points out, users are bad at picking good passwords. So, lets assume they are still bad at picking passwords. Eventually the URLs will become known, so we can't rely on that for security. An attacker can then download the encrypted private keys and decrypt them since a bad password was chosen.

How does this differ from traditional passwords? Well, in traditional passwords, at least the database and server can be hardened to keep people from getting material that can be used in an offline dictionary attack. Under this system, the URL scheme would be the only thing preventing an offline dictionary attack.


The order of reading bits in blocks Let's say I have a cryptographic algorithm that encrypts on 128-bit blocks and makes 20 rounds. Each round has its own keys (one of 72 keys per round). We read blocks before each round. But we're introducing the bit reading order. We can read from the most significant bit or the least significant bit. But in total we can read the bits before each round at 128! ways. We only need to define 20 random 128-element permutations.

But this increases the keys, you need to store these permutations. Is it a good idea?

For the safety of this algorithm there must be some order of bit reading, we can't always read them according to a typical binary number reading scheme.

But this increases the keys, you need to store these permutations. Is it a good idea?

I wouldn't think so; not so much from a subkey storage perspective, but from a performance perspective.

Storage could be do-able; $\log_2 128! \approx 716.16$; $20$ of these could be stored in $1791$ bytes, although it is likely that you wouldn't store them in a storage-minimal way, but instead in a format that makes it more efficient to perform the 20 permutations.

On the other hand, performance would look to be hideous.  There isn't an obvious way for software to permute 128 bits in a random fashion efficiently; picking each bit up, and depositing it in target position is unthinkably slow.  About the best I can think of would be to emulate a Batcher sort of the 128 bits (with appropriate masks to control when you swap and when you don't) - that's still likely to be slow (especially when you consider you need to do it 20 times).

As for hardware, well, by throwing a large number of gates at the problem, you could make it run reasonably fast - however, there are a lot of better ways to speed up other ciphers if you have a lot of gates at your disposal.

Why do I say performance is important?  Well, if you don't care about performance, it's easy to design things that are quite secure (e.g. 8-AES-256, using 8 independent keys); unless your design has some advantage over that, your cipher would appear to be pointless.


How can non-nothing-up-my-sleeve numbers be used to exploit an algorithm? I was watching Computerphile's "Magic 'Nothing Up My Sleeve' Numbers" video where Dr. Mike Pound reasons that the numbers used to create cryptographic functions should not arouse suspicion or contain hidden properties, because doing otherwise would introduce vulnerabilities into the algorithm.

I'm having difficulty conceptualizing how a nefarious agent, N, would exploit numbers that fail to satisfy the nothing-up-my-sleeve criteria.

The scenario I have in mind goes something like this: N proposes numbers for the basis of a cryptographic function, numbers that contain hidden properties that only N knows about. N goes away on vacation and when he returns to the lab, he finds his team has created a cipher in his absence; he wasn't there for the processes that followed, but what he does know is that his numbers laid the foundation. (I realize the case is probably naive, but hopefully it shows the bridge that I'm trying to build between non-nothing-up-my-sleeve numbers and exploitation.)

How would N's knowledge of what's hidden in these numbers allow him to attack the cipher? How would such an attack play out?

It could be, for example, that this $N$ is a specially crafter prime number, that looks random and safe according to the NIST recommendations, yet discrete logarithms modulo $N$ can be solved considerably more efficiently due to its hidden structure. An attack of this type has been demonstrated last year at Eurocrypt in this paper; it uses a random-looking prime with a hidden structure that makes it especially sensitive to the SNFS algorithm. The team could solve discrete logarithms with respect to a $1024$-bit prime, while the current record for 'normal' primes is 768 bits.


Decrypting small integers under RSA Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ or $c=4$.

  Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Since the RSA problem is assumed hard, we do not know and can't find the factorization of $n$.
We know (from standard RSA) that $m=c^{\left(e^{-1}\bmod\varphi(n)\right)}\bmod n$ fulfills the requirement $c\equiv m^e\pmod n$, but we do not know how to compute $m$ without some extra info or oracle.

Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Yes, but I have no better argument than: among integers $c>1$ independent of $n$, only exact $e^\text{th}$ powers are known to make it easy to solve the RSA problem for arbitrary $n$ too large to factor and odd $e>1$ making $(n,e)$ a valid RSA public key. In addition, there in no such $c$ in the interval $[2,2^e)$,  which with $e=65537$ as in a comment by the OP includes about all commonly used values of $n$, thus of $c$.
Solving $c\equiv m^e\pmod n$ for small $c$ is not necessarily hard for other $c$ and whenever $n$ is hard to factor. Proof by counterexample: $c=2$, $e=65537$, $n=(3^{65537}-2)/29$. I can't factor that $n$, yet it's easy to find the solution $m=3$.
More formally: I'm about as confident about the hardness of the RSA problem than I am about that problem restricted to small $c>1$, provided that $c$ is not a power of $e$, and that factors of $n$ are random distinct primes large enough to make factoring $n$ unfeasible. Yet I'd be quite surprised if we could prove the hardness of that restricted RSA problem on the basis of the hardness of the normal RSA problem.


Is it Ok to reverse the usage of public key and private key Well things like this, my coworker suggest exchange the private key between server and client and using public key to decrypt message privately, his reason is, this is just the same as normal usage, yeah for just encrypt and decrypt message they work the same. But I wonder is there any weakness in it, make it easier to crack?

No, this doesn't generally work:

encryption / decryption could use another padding scheme if it switches depending on what kind of key is used;
if the private key is leaked / made public then the public key can usually be guessed or calculated - this works at least for RSA and IES encryption using DH keys;
the crypto library may not be able to switch around the public key and private key, for instance for RSA may require the CRT parameters and ECC keys are different altogether.

A wild guess: in 60% it would not be feasible, 35 percent it would be completely insecure, 4 percent just less secure and in 1 percent of the time hey, you could be lucky and have something that approaches secure, all depending on the protocol, algorithm and implementation.


Verify that a point is inside a lattice I am wondering if there's a polynomial time algorithm that, given a lattice $\Lambda$ with basis $\mathbf{B}$ and a point $x$ in space, it tells you whether $x$ is in $\Lambda$ or not!

If you compute a base of a the dual lattice, and then check that the inner product of the point and the vector if this base are all integers:
To compute this base it's $\mathbf{B}(\mathbf{B}^{T}\mathbf{B})^{-1}$:
https://cseweb.ucsd.edu/classes/wi12/cse206A-a/LecDual.pdf


Extend OTP on random data? If Alice and Bob both start with a shared OTP $P_0$, which is 256-bytes long, and Alice wants to send a 512-byte message, would it be secure to send the first 256 bytes with standard OTP ((a+b)%256 or the like), then generate another 256 bytes of true randomness ($P_1$), run that through the OTP and send the encrypted form of that. Repeat for the second block of 256 bytes and $P_1$, etc. Bob then decrypts the first 256 bytes with $P_0$ and gets $P_1$ from the second 256 bytes. Rinse and repeat, etc.

Is this secure from a passive Eve? If not, why not?

No, that doesn't work. OTP is secure because knowledge of the plaintext doesn't give you any useful information about the key. This is because the bits of the key (e.g. $P_0$) are never used to encrypt anything else.

If you would somehow reuse the key then leakage of the plaintext would cause leakage of $P_0$. Leakage of $P_0$ directly leaks $P_1$. I.e. instead of perfect security the information encrypted by $P_1$ is now directly dependent on the security of the plaintext and $P_0$.

OTP is only perfectly secure as long as the bits in the key stream are independent of each other. OTP doesn't allow for shortcuts in that respect.


Efficient function/algorithm/method to do modular exponentiation I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you divide?

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python;

def fast_power(base, power):
    result = 1
    while power > 0:
        # If power is odd
        if power % 2 == 1:
            result = (result * base) % MOD

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

The if condition is an attack point for side-channel attacks. One can measure power usage and determine exponent bits. The below image or similar research images can show the idea of the attack.

If you are signing with RSA your private exponent can be revealed. Squaring can be implemented faster than multiplication, in that case, it can also be exploited. Therefore, you need constant timing to prevent this. The python library contains power modulus pow(a,e,n) which is based on repeated squaring and it is not secure. The below version of the repeated squaring method always calculates the (result * base) % MOD and discards it when it is not necessary. This may help mitigate the attack, however, this can be still traced if there is an instrument with enough resolution. Also, during compilation, make sure that this mitigation is not removed by compilers. Compilers, like Cray's CC can discard unused calculations as an optimization by default.

def constant_time_power(base, power):
    result = 1
    while power > 0:
        # else to prevent leak
        if power % 2 == 1:
            result = (result * base) % MOD
        else:
            result_temp = (result * base) % MOD

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

As mentioned above code, taddedhe above can be optimized by compilers with dead code elimination technique since the code contains unused code. Some compilers have pragma directives to disable local optimization. Instead of relying on compiler directives and their bugs, changes, etc., it is possible to use a constant-time conditional copy. The below show this;

def constant_time_power_with_conditional_copy(base, power):
    result = 1
    while power > 0:
        # constant-time conditional copy
        sBit = power%2==1
        result = ((result * base) % MOD)*sBit+(1-sBit)*result

        # Divide the power by 2
        power = power // 2
        # Multiply base to itself
        base = (base * base) % MOD

    return result

The famous GMP library has a secure version mpn_sec_powm of their standard mpn_powm.

  This function is designed to take the same time and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. This function is intended for cryptographic purposes, where resilience to side-channel attacks is desired.

There are other modular multiplications like Barret or Montgomery. They have also constant-time implementations. For example for Montgomery based

2009 Fast and Constant-Time Implementation of Modular Exponentiation by Gopal et al.


What exactly is Let's encrypts chain.pem file? While trying to understand the use or meaning of the fullchain.pem file created by let's encrypt I stumbled upon this post in which fullchain.pem is explained as:

fullchain.pem is a concatenation of cert.pem and chain.pem in one file. In most servers you’ll specify this file as the certificate, so the entire chain will be send at once. Some clients require you to specify the above two files separate. In that case you won’t need

While chain.pem on the other hand is described as

chain.pem contains the intermediate certificate, the certificate from Let’s Encrypt containing the public key which is “coupled” to the private key which signed your certificate (the one above). This intermediate certificate is required for clients to verify your certificate;

But I have troubles really understanding what this means. By this I mean what exactly is intermediate certificate and where does it come from.
I understand the concept of CA's and the fact that CA issue certificates. I understand that the certificate issued by the CA which is put to use is the end user certificate.
I also understand the chain of trust, where there are intermediate CA between the end user certificate and the root CA.
What I can't understand is how let's encrypt can know all the possible intermediate CA between the root CA and the end certificate.
I mean it is possible to know all the CA, that the root CA itself signed. But what if those other CA's created other CA's that ends up issuing the end user certificate, how can this ever be in chain.pem?
Which then begs the question, how can those end user certificate's be ever verified, since it seems the full chain of trust, the full intermediate CA is not known in chain.pem?
Anyone kind enough to help me understand the setup? Thanks!

When requesting a certificate one sends a Certificate Signing Request, containing the information to be signed by a CA, to that CA. The CA responds with the resulting certificate and the chain of certificates back to a root. That chain is the CA's certificate, any intermediate CA certificate(s) that signed the CA, (possibly multiple levels), and the root certificate that signed the top-level intermediate CA certificate (if that's not the same as the CA's certificate in question). In Let's Encrypt's case, there's only the CA certificate and the Root in this chain.
The CA knows everything in the chain because they in turn had requested their certificate from an intermediate CA or root, and they know who they requested it from. So they know the certificate of the intermediate or root, and can include it. Likewise back up the chain.
Root CAs have self-signed certificates. There's no other entity in their certificate chain. These certificates get imported as trusted root certificates by browser vendors (and other entities dealing with the TLS CA system), allowing verification of certificate chains starting at these roots.
Since every time anyone (including a CA) requests a certificate they get back the entire chain it's trivial for a CA to send the chain along with the resulting certificate from a request. Also, certificates are public and all major CAs publish the certificates they issue in "certificate transparency logs", so even without the chain one could (in theory) look up the certificates for each signing entity.


Digital Signature Algorithm signature creation? I was studying DSS from "Cryptography and Network Security" by William Stallings. What puzzled me was the DSS approach figure described in the text. It says it uses Public and Private Keys for creating signature.

But the algorithm for creating signature in DSA doesn't use it.

$$r = (g^{k}\mod p)\mod q$$
$$s = (k^{-1}(H(M)+ x\cdot r)) \mod q$$

Someone please tell me the importance of public key here. Is it needed in verification only?

It depends how you define what a "public key" is.

Typically it is the value of the key itself ($y$), plus information about the group (safe prime $p$, subgroup size $q$, generator of subgroup $g$). For signing a message, you do not need the value of the public key itself. So if you are strict in defining a "public key" to only be $y$, it is not needed to sign (only to verify).

On the other hand, you do need the group description ($p,q,g$) to sign a message, as well as the secret key ($x$). If you are liberal and define "public key" to include the group description, then the public key (or parts of it) is needed to sign.

I am not sure what is meant by PU$_\mathrm{G}$ in the diagram, but I suspect it is the group description? In that case, Stallings is being liberal in his definition of a public key in that it includes the group information ($p,q,g$).

As an aside, even though you do not need the public key, you do need $g$ and $x$ and since $y=g^x$, you do "know" the public key at signing time even if you do not use the value $y$ explicitly.


Security of a cryptosystem where the encryption is swapped with decryption For any given one-key cipher $(M,C,K,E_k,D_k)$, we may modify it into $(M,C,K,D_k,E_k)$. In other words, we swap the encryption function with the decryption in the modified cipher.

Are the two ciphers have the same level of security with respect to known- plaintext attacks?

If we have a plain text attack which takes n pairs of known plain text known cipher text and with expected computational effort T extracts the key K then for the inverted cipher the same attack would work with the same properties would work by swapping the order of the pairs.

More formally if we have an atack function a(c,p)= k where c is a cipher text and p is a plain text, we can trivially construct a'(x,y)=a(y,x) which will work on the swapped cipher. You can extend this to family if known plain text attacks, multiple pairs required, computaitional cost, probability of succsss, weak keys etc. As long as the input is pairs of cipher text and plain text you can swap the pair order and get the same attack propeties on the swapped cipher.


Attack on key exchange with authentication Suppose the honest parties - Alice and Bob - exchange public key in person/via telephone so that attacker can only eavesdrop on the line. Alice has hashed the public key using a collision resistance hash function $H$ before telling it to Bob. Bob will encrypt a random $k$ using $key = H(pk)$ and read it ($E_{H(pk)}(k)$) off to Alice for the authenticated scheme. Later on they both communicate through the internet where the attacker can act as a Man-in-the-Middle attacker. Is this scheme secure? As far as I can see, the attacker can't do anything since he can't either obtain $pk$ (as they use a CRH function) or key $k$(attacker doesn't have secret key from Alice)

No, this scheme isn't secure.

As far as I understand your description you are using the hashed public key of Alice as the symmetric key to a cipher, but as you already just send this hash over the line, the attacker can simply decrypt $k$ himself and thereby $k$ isn't established as a pre-shared key. By the way, there's no way to recover $pk$ from $H(pk)$ and thereby you can't public key encrypt $k$ here.

This can however be fixed in one of two ways: a) you don't hash the public key at all and just let Alice send Bob her public key, which he will subsequently use to asymmetrically encrypt $k$ so only Alice can read it. Or b) you just stay with the hash of the public key (and maybe drop the $k$ which doesn't serve any purpose if the channel is guaranteed to be integrity protecting) and let Alice send her public key over the internet in clear. Bob can verify the public key using the trusted hash of it and if the hash of the received public keys match, he can then use this to encrypt a session key.


Can I combine two PRNGs to make use of more seed data? I have 320 bits of seed data (actually 512 bits of data with 320 bits of entropy, derived from a Diffie-Hellman shared secret and nonces). The PRNG I am using at the moment is the android version of SHA1PRNG. As far as I can tell, it has 160 bits of internal state, and so any entropy over 160 bits would be wasted. Could I create two instances, seeding each with half the data, and combine them somehow? The obvious possibilities would be to alternate which PRNG I pull each byte from, or to XOR the two streams together, but I don't know how that would affect the total entropy.

Why are you afraid of "overseeding" the PRNG? The Java SecureRandom class specifies the setSeed function as:

public void setSeed(byte[] seed)

So just feed the 320 bits (40 bytes) data to the setSeed function and it will supplement the existing seed. Leave the compression into the state to the underlying SecureRandom implementation.

[EDIT1]

Note that the SHA1PRNG implementation simply uses the new seed in a message digest update, and that message digest is SHA-1, hence the 160 bit state.

[EDIT2]

Note that it may depend on the entropy source if the entropy represents 320 bits of true random data. The initial compression of the seed data will make sure that any random entropy from the entropy source is used.

Another reason to combine to PRNG's is when the PRNG algorithm is not fully trusted. In that case it is much better to switch to another PRNG. If one is vulnerable the other one will be vulnerable as well.

It is better to re-seed the PRNG more often if there is entropy to spare.


Ensure Data Integrity In An ECDH Key Excange Been playing around with the inner workings of onion routing and I have a problem. If I wanted to send the 2nd node of a relay network an ephemeral ECC public key, it has to go through node 1, so that node 2 does not know the IP of the client. Once the shared secret is calculated, an encrypted connection from the client to node 2 that essentially proxies through node 1 can be created, so node 1 can't view the info that passes through it from the client to node 2. However, how can node 2 be sure that the ephemeral ECC key it receives from the client via node 1 is the actual key. How can the integrity be verified, to counter MITM attacks?

I dont think that signing the key with a permanent ECC key would work because then the 2nd node would have to use the clients permanent ECC public key to verify the data, and then node 2 would know what the clients IP is, as it would have to be stored together, so that the correct key can be used to verify the signature.

How can the integrity of the key exchange be verifies without using digital signatures?

1. Authentication

  then node 2 would know what the clients IP is

This statement is not necessarily true. If a certificate is given to a web site, then yes, IP or domain name will be known. But if your client is a person, then certificate can create some email address that can be without any meaning to the world.

2. Pre-shared secret

Use a pre-shared secret. For instance, you can use it for HMAC.

If the client has neither a certificate that you trust nor pre-shared secret, you cannot be sure whom are you communicating with: with your client or with a man in the middle.

Update

Key exchange is one of the most important and most complex questions in cryptography. There is no trivial solution.

A) Use secure channel for key exchange. You can exchange key via direct contact with the other party (not realistic), or somebody whom you trust carries the key from you to the other party, or you have a secure physical channel, etc. Here an asymmetric algo can be preferred, because the public key and thus the channel does not need to be confidential.

B) Use some chain of trust. If you trust to some CA (like Google) and trust its sub-CAs, then you can trust that the public key of the other party really belongs to it. If you trust... You know that Google Chrome distrusted certificates issued by Symantec & Co (Thawte, VeriSign, GeoTrust, ...). You heard about DigiNotar and Trustwave. E.g. Trustwave intentionally issued multiple certificates that enabled MITM. On the other side the number of correctly created certificates is estimated of about 99.995%. Besides certificate issuing there are other important aspects like trustworthiness of DNS.

Some may mention quantum approach. But it is actually requires on these two.

As you see, there is no easy solution.


What is an active S-Box? I don't understand what an active s-box is (in reference of design criteria 8 of the DES).

Because according to DES, all 8 s-boxes are used every round. But this is not what active means.

So my question: What is an active S-Box, and what does it mean when an s-box is active (or when two or three s-boxes are active)?

You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal).

Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “passive” and are not considered further).


How to convert a Galois LFSR to a Fibonacci LFSR? I have just found the sequence output by the Galois type LFSR, seen here.

Now I know there exists a Fibonacci-type LFSR capable of outputting this same sequence but how could I find what the first six states of this LFSR would be?

In this answer I will consider the Galois LFSR mentionned at this question: Sequence output by a Galois type LFSR see the image below.

First we assume that the 5 positions of bits are numbered from left to right: 0 .. 4

The Galois representation is as follows:

+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+--->+  1  +---->+  0  +--+->+  0  +--+->+  0  +--+->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

If we iterate the LFSR for 10 rounds we get:

1 0 0 0 0 : initial state
0 1 0 0 0 -> 0
0 0 1 0 0 -> 0
0 0 0 1 0 -> 0
0 0 0 0 1 -> 0
1 0 1 1 1 -> 1

1 1 1 0 0 -> 1
0 1 1 1 0 -> 0
0 0 1 1 1 -> 0
1 0 1 0 0 -> 1
0 1 0 1 0 -> 0

Assuming now that we have a Fibonacci LFSR but we want to know where the tap are.
We will iterate the lfsr and naming the unkowns by letters.
There are two tricks involved to solve this:

a letter is once set and never modified later (as opposed to the Galois version)
using an initial 10000 state will reveal the positions of the taps.

So we have:

1 0 0 0 0 : initial state
a 1 0 0 0 -> 0            (i)
b a 1 0 0 -> 0
c b a 1 0 -> 0
d c b a 1 -> 0
e d c b a -> 1

Then we can solve it.

f e d c b -> a = 1

By (i), we can deduce that position 0 influence on output: all the other positions are null.

g f e d c -> b = 0 -> b

b would be 1 if only position 0 had an influence. Thus Position 1 is also influencing making it back to 0.

h g f e d -> c = 0

c would be 0 if only position 0 and 1 had an influence. Position 2 is also influencing making it back to 0.

i h g f e -> d = 1

d is the value it should be thus position 3 is not influencing.

j i h g f -> e = 0

e is the value it should be as there is the feedback.

If we continue on the next 5 outputs on both models we have the following stream: 01111

To conclude the Fibonacci representation of the LFSR is the following:

+-------------+-----------+-----------+------------------------+
|             ^           ^           ^                        |
|    +-----+  |  +-----+  |  +-----+  |  +-----+     +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |     |     |   |
+--->+  1  +---->+  0  +---->+  0  +---->+  0  +---->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

Here is a small python code to check the equivalence between both.


How to symmetrically encrypt 64bit values? I'm curious about an algorithm that would be good for the following scenario:

32-bit "plaintext" input, taken from a counter
32 or 64-bit "ciphertext" output
It should be possible to decrypt the output with the key (and possibly a few other hidden parameters, like an offset and current counter), and return the original 32-bit counter value
A user never observes the input, but may receive any number of outputs, possibly sequential. Even so, they should not be able to know which indices they have.
It should be difficult to guess other outputs that correspond to valid counter values.

My untrained intuition is that since the key and outputs are larger than the input space, it should be fairly easy to have "good" results, at least for the first few outputs. However, it also seems logical that with enough samples the key and indices could be computed easily, but I expect most instances to use less than 100 values.

My questions are:

Are there any existing algorithms that work for this scenario?
How hard would it be to crack? I.e., compute values that decrypt to valid indices.
How much does the possession of more samples affect the efficiency of cracking it?
What's wrong with a naive approach like:

u64 output = input
repeat 64x
  output = ((output ^ key) + key) rotate-left 37

Assuming addition wraps around 64bit integer boundaries.
It seems as though it would thoroughly mix the random key with a single input, but possessing more than one output could quickly increase the information an attacker possesses, though I wouldn't know how. Obviously it's going to be broken, I'm just trying to learn.
Would using a key-dependent value for the left-rotation, like (((key & 0xFFFE)+1) * 37) be better? How much does it help and why?
What approaches, resources, etc. would you use to both analyze the algorithm, and design a better one?

Are there any existing algorithms that work for this scenario?

Yes, actually, there are a number of 64 bit block ciphers.  The standard wisdom is that they aren't encouraged for general use, because standard block cipher modes tend to start leaking information when you get near the birthday bound (in this case, circa 30 Gbytes); however for your use case, that would not be a concern.

Here are some options:

3DES (aka TDES); this is DES applied three times with three different keys; this has the advantage of being very well studied.
Speck which has parameter sets with 64 bit block ciphers.  This has the advantage of being the fastest alternative, and was designed by people who know that they're doing, and has done through a surprising amount of cryptanalysis.
An FPE cipher (such as FF1, which can handle any arbitrary block size (including 64 bits).  This has the advantage in that they allow the option for a tweak (which is a convenient place to place the "other hidden parameters", should you decide that is an advantage).  It's slower than the alternatives; with FF1, the security comes from the underlying security of AES, plus the provable security of the Feistel structure.

Now, these take keys longer than 64 bits; the common wisdom is that a 64 bit key is just not long enough.

  How hard would it be to crack? I.e., compute values that decrypt to valid indices.

For any of the above, the only practical option an adversary would have would be to randomly guess ciphertexts, and hope to stumble on one that decrypts to a valid index.

  How much does the possession of more samples affect the efficiency of cracking it?

For any of the above, having vast quantities of samples will still make the attack infeasible.

  What's wrong with a naive approach like...

ARX ciphers (actually, any cipher, but especially ARX) are tricky to get right.  ARX ciphers in particular tend not to be great at disrupting differential and linear characteristics (which means any such design would really need to be well studied to make sure that it does).

  What approaches, resources, etc. would you use to both analyze the algorithm, and design a better one?

I'd suggest you go with a design which has already been analyzed; I list three above.


Is this a good choice of a digital signature scheme? This is a concrete instantiation of Rabin-Williams signatures.

Specifically:

The private key is 2 primes $p, q$.
The public key is their product $N = pq$ and is approximately 3072 bits long.
the hash function is Skein-512 with 3072 + 512 = 3584 bits output (Skein allows arbitrary output lengths).
The padding scheme is deterministic full-domain-hashing, using the 3072 low-order bits of the Skein output.
The two high-order bits of the Skein output, which are not otherwise used, are used to select which of the four square roots to output.

Example applications are CA signatures and distribution package manager signatures where signature verification speed is critical.

Questions:

Is Rabin-Williams with 3072 bit keys faster or slower to verify than EdDSA?
Is the scheme I gave secure?  I think that it is an instantiation of a scheme that was proven secure in the random oracle model by Bernstein in this paper.  While Skein is less used than other secure hash algorithms, it was an SHA-3 finalist and underwent a substantial amount of cryptanalysis.

Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points:

in the eBATS benchmarks for a skylake CPU, ronald3072 signature verification (RSA with $e=3$ as an OpenSSL wrapper, by Bernstein) is nearly twice as fast as ed25519 (archetypal EdDSA carefully optimized by Bernstein); I'm too lazy to see if/when Montgomery arithmetic (which does not pay in the context) is used by OpenSSL RSA signature verification; but since there are at least two modular multiplications in that, versus one in RW, the later can only be faster.
in the Crypto++ benchmarks, RW 3072 verification can be extrapolated from RW 2048 verification times 2.25 (erring on the safe side), and is over 15 times faster than the fastest ECDSA signature verification (with pre-computation) quoted.

Even for an implementation using a $32\times32\to64$ multiplier, and classical algorithms, the modular multiplication dominating (properly coded) RW signature verification with 3072 bits key uses $k=96$ words, and about $2k^2$ (less than 20000) multiply-and-add. That can't be very long if coded carefully!

I think the theoretical principle of the scheme is right. Some details (like exactly what Full-Domain-Hashing is used, and perhaps additional constraints on primes) needs to be ironed out. And of course, the principle of rolling one's crypto is debatable (or just should be summarily rejected, in many real-life contexts).

As of implementation: the signature verification is reasonably easy to get right (as long as the correct number of redundancy bytes are checked), and is inherently immune to timing and other side-channel leakage (excluding fault injection), since nothing secret is involved. However lots of things can go wrong in signature generation, including side-channel (timing, power analysis..) and fault-injection attacks (against the later, at the very least, the signature should be verified independently of what generated it before being released).


Is it safe to encrypt data by simply randomizing chunks based on a permutation? Say I want to encrypt the following text: "Today is March the 22nd, 2015". And say want to encrypt 8-byte blocks of data using the following permutation [6,3,0,1,5,7,2,4] to swap characters at those indexes.

[T|o|d|a|y| |i|s| |M| a| r| c| h|  | t| h| e|  | 2| 2| n| d| ,|  | 2| 0| 1| 5]
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

Using the encryption key [6,3,0,1,5,7,2,4], encrypting the first block goes like this:

First index is 6, so move the character at index 6 in the plain text to the first position of the ciphertext.

[i]

Second one is 3, so add the character at index 3 to the ciphertext:

[i|a]

When we finish the first block it looks like this (without the "|"):

[i|a|T|o| |s|d|y]

Then continue to do the same for the other blocks.

If the length if the text is not a multiple of the block size, just pad with some character and remove it after decryption.

I can't think of any type of attack except for brute force. This would basically mean generating all permutations of size n (where n is the block size). For block sizes larger than 1KB, it's basically computationally infeasible to break it.

Can anyone think of any other type of attack?

This is called a transposition cipher. It is the kind of thing that was commonplace before the invention of the computer, and some people were really good at breaking that in mere minutes (e.g. Edgar Allan Poe). In all generality, breakage is done by backtracking (wrong hypotheses on permutation elements leading to "impossible digraphs" that cannot occur in normal text).


What does "bits" mean in the context of hash functions? What does the "bits" in hash functions mean?

I started studying hash functions but I still do not understand what the bits mean.

What does it mean to say that MD5 is 128-bits or that SHA-1 is 160 bits? How is this calculated?

That's referring to the size of the output, or message digest, of a hash function. MD5 outputs an 128-bit hash value. Or: there are $2^{128}$ possible outputs.

In Python:

>> md5("hello, world").hexdigest()
'e4d7f1b4ed2e42d15898f4b27b019da4'

You can see 32 hexadecimal (hex) digits that represent 16 bytes or 128 bits. Here's that value in binary; there are 128 $0$s and $1$s, or binary digits that represent bits:

  11100100110101111111000110110100111011010010111001000010110100010101100010011000111101001011001001111011000000011001110110100100

To calculate, just count them!

Likewise, for SHA-1, you have 160 bits, 20 bytes or 40 hex digits. There are $2^{160}$ possible outputs:

 >> sha1("hello, world").hexdigest()
 'b7e23ec29af22b0b4e41da31e868d57226121c84'

The output size of a hash is directly linked to the maximum security level that can be achieved. The security level is half of the bits if the birthday problem applies for example if the hash is over a string as above. It's the full amount if this isn't the case.

Note that both MD5 and SHA-1 are considered broken for most usage scenarios, so the above calculations do not apply to them anymore. The amount of security offered is much less than the output size would suggest.


Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? Related to this question: Is there any memory trade-off that helps such attack?

Obviously if the field size is very small (say 40 bits) it´s possible, but what if the field size is 160 bits long? or 256 bits?

Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field.

Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because Big-Step/Little-Step will apply to any finite group.  In terms of Elliptic Curves, for practical purposes we can make the assumption that $size(group) \approx size(field)$.

In the precompute phase, we construct a table with the pair of values $(ib, (ib)G)$  for $(0 \le i < a)$.  This table will contain $a$ rows, and takes $O(a)$ time to construct.  Note that this table does not depend on the point $Q$ that we'll end up computing the discrete log on.

In the lookup phase, we compute the points $Q - jG$ for $0 \le j < b$, and look up each of these points in the table.  If we find one of the points in the table, we have $(ib)G = Q - jG$ (where $i$ is the value in the table, and $j$ is the value we used to compute the point), we then know that $Q = (ib + j)G$, and hence we have the discrete log.  This phase takes $O(b)$ expected time (assuming each lookup can be done in constant time using appropriate data structures).

Now, the total time taken is $O(max(a,b))$; to minimize this value, we generally assume that $a=b\approx\sqrt{size(group)}$, thus giving us a squareroot time algorithm.  However, there is no such hard requirement, and if we're going to reuse the table multiple times, it makes sense to increase the value of $a$ (the one time cost) so we can decrease $b$ (the per-discrete-log cost).

However, once we start talking about a group with circa $2^{160}$ members, well, this doesn't work out.  For one, even in the balanced case, we're talking about a table with $2^{80}$ entries; that in itself is impractically large.  If we consider increasing $a$, the table size becomes even more impractically large.

Now, one obvious idea to reduce the table size is to create a Rainbow table.  It turns out that Rainbow tables will work in the way we want (allowing us to build a table that we can use to lookup $i$ given $(ib)G$ values); however, it turns out not to buy us anything.  Rainbow tables allow us to compress the table by a factor of $k$ by increasing the lookup time by that same factor $k$.  That turns out to be the killer; because the lookup phase involved $O(b)$ table lookups.  We can make the table $O(a/k)$ entries long; however the lookup phase will now take $O(kb)$ work; we haven't gained anything that we wouldn't have gotten by making $a$ smaller by a factor of $k$ and $b$ larger by a factor of $k$.


Significance of Gram-Schmidt coefficients in LLL algorithm Let $\{ {\bf v}_1,{\bf v}_2 \}$ be two linearly independent vectors. An orthogonal base $\{{\bf u}_1,{\bf u}_2 \}$ of the vector space $\mathrm{span}\{ {\bf v}_1,{\bf v}_2 \}$ can be computed using Gram-Schmidt Orthogonalization process (GSO) which is summarized by the formulas
$${\bf u}_1={\bf v}_1 \quad\text{and}\quad {\bf u}_2={\bf v}_2-\mu_{2,1}{\bf u}_1 \quad\text{where}\quad\mu_{2,1}=\frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||^2}$$
Geometrically it is given as

In order to get ${\bf u}_2$ i.e., orthogonal to ${\bf u}_1$ project ${\bf v}_2$ onto ${\bf u}_1$ and the length of the projection on ${\bf u}_1$ is given by $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$ and to get the direction we multiply the length by the unit vector $\frac{{\bf u}_1}{||{\bf u}_1||}$ and the $\mathrm{proj}_{{\bf u}_1} {\bf v}_2= \frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||}\times \frac{{\bf u}_1}{||{\bf u}_1||},$ where the length of the projection is $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$. In GSO process $\mu_{2,1}=\frac{\text{length of the projection of \(v_2\) on \(u_1\)}}{||{\bf u}_1||}$ what does $\mu_{2,1}$ represent geometrically?

If $\{ {\bf v}_1,{\bf v}_2 \}$ is the basis of the lattice to solve the shortest vector problem, our aim is to find the orthogonal basis. But orthogonal vectors computed using GSO need not be a basis because $\mu_{2,1}$ need not be an integer.

Since SVP is a hard problem, the LLL algorithm solves approximate SVP. In defining an LLL reduced basis the first requirement is $\mu_{2,1} \le \frac{1}{2}$ (size reduction condition). What does this imply?

Say you have an integer lattice $\mathcal{L}$ with (ordered) basis $B=\{{\bf b}_1,\ldots,{\bf b}_n \},$ ${\bf b}_j\in {\bf Z}^m$, $n\leq m$. As you wrote the first condition of the LLL reduced basis $\{ {\bf u}_1,\ldots,{\bf u}_n\}$ is the process of size reduction. That is $|\mu_{i,j}|\leq \frac{1}{2}$, $j<i$. If you set $M_i=\mathrm{span}({\bf b}_1,\ldots,{\bf b}_i),\ i<n$ then this condition shortens the projection $\mathrm{proj}_{M_i}({\bf b}_{i+1})$, while the second condition (Lovász)  shortens the projection $\mathrm{proj}_{M_i^\perp}({\bf b}_{i+1})= {\bf b}_{i+1}^*$.

References

Phong Q. Nguyen and Damien Stehlé. An LLL algorithm with quadratic complexity. Siam J. Comput., 2009. doi:10.1137/070705702 [PDF]


Why are access tokens so long in general? I was looking at this Nano ID page where they generate a 21 characters long ID and it would take 149 billions years to find a collision, so that seems secure enough.
However I found that most APIs use much longer tokens for authentication. For example, Dropbox uses a 64 characters long token (made of complete alphabet and numbers) and OneDrive uses a 1180 characters long token (also made of complete alphabet and numbers).
So I'm wondering why do they use such long tokens? And related questions, what's an ideal size for a token made of random letters and numbers?

One way of producing a secure token is to sample 256 bits of entropy and encode that into a usable character set (often base64). This will get you the shortest secure token. But by design, this token will be completely opaque - that is, it contains no information so that any use of it will require a lookup into a database.
There are all sorts of engineering trade-offs that you might want to make, balancing a longer token against making them easier to use or validate. For instance, you might want to augment your random token from which you can extract information about: the account id, the customer's region (for geographic sharding), expiration time, etc. These will result in longer tokens, but there is a very low cost associated with slightly longer tokens.


How to build disk encryption system using forward permutations like Gimli? First of all, this is purely a thought experiment. The width of Gimli isn't even a power of two (384 bits), and secondary storage bus speeds aren't even worth using a high performance permutation like Gimli. So from a practical perspective, this is totally pointless.

But it's nonetheless an interesting one. And from it, I have three concrete questions that can be considered:

Can we build a tweakable bijective keyed permutation from just a pseudo-random forward permutation?
Is there a practical disk encryption system using only forward permutation?
How do we interpret the "new conventional wisdom" that "a permutation
is a better unified primitive than a block cipher"?

Gimli paper can be here.

Disclaimer: I'm one of the authors of the said permutation.

Gimli does not aim to be used as a block cipher (in the traditional sense of it: $x \to (\sigma \circ K_{\mathit{add}})^{\mathit{nb}_{\mathit{rounds}}}$ with a block size of 384 bits or similar constructions); it is better to use it with a sponge construction such a Monkey-Duplex/Monkey-Wrap or Farfalle.
An example of such a construction would be the design of Ketje Sr.
No Idea.

  Imagine there's no blockciphers, it's easy if you try :-)

  Joan Daemen at FSE 2017 [abstract] [slides]

(I really advise you to have a look at the slides.)

The idea is here is to have a unique permutation (Gimli? :D) on which you can derive the rest (hash functions, CPRNG, etc.). Sure you can use a Davies–Mayer or Even–Mansour with Merkle–Damgård construction to build a hash function from a blockcipher. But using a sponge construction is more elegant and efficient: you only have one code for the permutation and the design is easier to read (thus understand and verify).


Questions about SHA and SHAKE So I got bored one weekend so I thought I would make a login system in python. I then realized if I wanted to reuse the accounts I made I had to store the account details locally. I realized I had to use some sort of encryption. I looked around for what is best for passwords and I chose to use use a SHA512 hash(I know it isn't encryption, but still). Now a few weeks later I discover about SHA3. I hear this is more secure so implement it in my code. Reading on the tutorial on the SHA3 module I am using to add SHA3 to my code, I see there is such thing as SHAKE. With searching all I can find is Weed growing forums. So I want to know:

What is Shake? Is it like a SHA hash?

Is there an algorithm that is used to make hashes? Or are hashes made some other way?

What is SHAKE?

SHAKE is defined in FIPS 202 (PDF), it is a combination of SHA and KEccak (the original name of the candidate) by naming. What it does is that you give it an (arbitrarily long) input string and it returns you an (arbitrarily long) output string that has the usual properties of a hash (ie pseudo-randomness, collision-resistance, preimage-resistance, ...) while having a highly tunable length parameter which is useful in some applications.

  Is it like a SHA hash?

It basically is SHA-3 (slightly different actually) but without the fixed length restrictions on the output.

  Is there an algorithm that is used to make hashes? Or are hashes made
  some other way?

Technically speaking, you can use any hash algorithm to get hashes. Common choices include SHA3 and SHA-256 if you want something that is fast or Argon2, scrypt, bcrypt or PBKDF2 (in that order) if you want something that is slow.

As I can see from your question, you want to hash passwords. For this application, you really want to use slow hashes to slow an attacker down from trying all the passwords of your users quickly because they probably contain low uncertainity.


What would the Internet be like without public-key cryptography? The functioning of the Internet as we know it nowadays depends very heavily on public-key cryptography, including several key root systems that depend on its asymmetric properties.

But what would it be like to not have that tool? Could a sufficiently advanced but less convenient private-key cryptography system still make up for what public-key cryptography does? Would the Internet still be able to function in roughly the way it currently does?

You can create a public key cryptosystem from any trapdoor function, and you need some form of trapdoor to design a public key cryptosystem. Do you mean "those trapdoor functions, which are currently USED in Internet standards"? The most prominent ones are discrete log of integers, factorization and discrete log in elliptic curves.

If so: Yes, it might be possible to set up new protocols, based on other hard problems, although I can just think of lattice problems atm (SVP,CVP,LWE,etc) and McEliece(based on linear codes). It is easy to use these instead of any factorization-based public key cryptosystem. However, the discrete log problem is a different matter: The group structure does not depend on a specific private key and several (pk,sk) key pairs can operate on the same group. This is required for several primitives, e.g. DH key exchange. I can't think of any hard problem with this, other than discrete log on integers and elliptic curves.

If you want to disallow all known public key cryptosystems (in the sense of all protocols based on trapdoor function)... it would be VERY different. While you could communicate over secure channels with symmetric key crypto, there is no way to exchange a key. If you want to use a key for symmetric encryption, both sides have to know it previously or send it plain.

In this case, some parts of the Internet still would work: You could store a secret key for every single party, with whom you interacted. Based on this key, you can set up a new secure connection again. Authentication might still work with hash functions, etc.

But assuming, you want to visit a website and interact over a secure channel: You have no known secret and have to agree on something. Whatever you send, the routers between you and the website will know. If you can trust ALL of them, you are okay. But any of them could just listen in your secret channel

To sum it up: If the Internet was based on trustworthy infrastructure (providers, exchange points, etc.), it would be similar. However, that would not be the Internet we have today. The current Internet would just not work.


AES-256 will double the size of photo after encryption? I am currently working on my JavaScript project where I am also trying to encrypt attachments with AES-256. Right now I am testing it and I am getting this results.

For photo file which has size about 2mb after encryption I get 3.7MB... Which is cca double that original size.

I want ask you guys if it is OK because what I have heard AES cypher is not like RSA and it is not adding any or not to much additional size. Am I right?

If this help I am using open source AES-JS...

No, AES is a block cipher that encrypts precisely one block of plaintext and results in a block of ciphertext.

The amount of overhead depends on the mode, but it is usually limited to one block for the IV and one block of padding at most. When an authenticated mode is used such as GCM then you may have one block of authentication tag as well.

Adding to that is any kind of meta data to keep the structure intact, salt for password based key derivation etc. You would not expect an overhead more than 100 bytes or so, where AES and it mode only takes 32 bytes max (as padding and an authentication tag usually aren't used together).

So what can cause this overhead? The most likely culprit is encoding of the bytes. Many libraries output base64 instead of bytes if "raw" output is not specified. Base 64 adds an overhead of about 33% (4 characters for each 3 byte, plus one or two padding characters). This would be in line with your result.

Note that "hex" encoding is not the same as "raw" encoding of the bytes. Hexadecimals is a direct representation of each byte value in text using two hexadecimal digits 0-9 and A-F per byte. If you save these two characters they become a byte each, doubling the size in bytes of the ciphertext. Or, if you are unlucky and save in UTF-16 (the braindead default of .NET) you get a quadrupling in size.

It is of course also possible to wrongly implement the AES, even given a high level API. For instance you could read the input data in blocks and then encrypt each block separately. This could in principle more than triple the size (IV and padding or IV and authentication tag). Instead it is wise to look for a streaming option or update function in the library.