What is the role of a circuit in ZK-SNARKS What role does a circuit play in ZK-SNARKS? Is it executed on both the prover's and the verifier's machine? If so, how would you program it to check if one value is greater than another value?

Technically neither party necessarily evaluates the circuit.

The two parties share the description of a circuit $C$, an output value $y$ and potentially some input values $x_1\dots,x_\ell$. the prover than proves to the verifier that they know additional secret inputs $s_1,\dots,s_n$, such that if one were to evaluate the circuit $C$ on inputs $x_1\dots,x_\ell,s_1,\dots,s_n$ the result would be $y$. I.e.,
$$C(x_1\dots,x_\ell,s_1,\dots,s_n)=y.$$

The argument of knowledge property guarantees that the prover must actually know said inputs in order to convince the verifier. The zero-knowledge property guarantees that the verifier learns nothing from the exchange except that the above statement is true. In particular the verifier learn no information about $s_1,\dots,s_n$.


How to best obtain bit sequences from throwing normal dice? Throwing normal dice, one can get sequences of digits in [0,5]. In practice, which is the best procedure to transform such sequences into a desired number of bit sequences?

Thomas' first procedure produces 2 bits per roll with a probability of $\frac23$, i.e. it produces $\frac43 \doteq 1.333$ bits on the average. This can be improved as he describes, but it gets quite complicated soon.

Producing a single bit per roll by taking the result mod two leads to $1$ bit per roll, which is not much worse. Combining the two simple methods like

1 -> 00
2 -> 01
3 -> 10
4 -> 11
5 -> 0
6 -> 1

is quite simple and produces $1+\frac23 = \frac53 \doteq 1.667$ bits per roll. AFAIK, this is the maximum you can get without aggregating the rolls.

You can apply this idea to two rolls and obtain $5$ bits with probability of $\frac{32}{36}$ and $2$ bits otherwise thus getting

$$2 + (5-2) \cdot \frac{32}{36} = 2 + \frac{3 \cdot 8}9 = 2 + \frac83
= \frac{14}3 = 4\frac23$$

bits for two rolls, i.e., $2\frac13 \doteq 2.333$ bits per roll, which is quite close to the theoretical maximum of $\log_2 6 \doteq 2.585$.

For a simple "implementation without computer", note that you can extract 1 bit directly from each roll and need to process the "rest" only (e.g. you can get the bit via $n \bmod 2$ and the rest via $\lfloor \frac{n-1}3 \rfloor$). This makes even combining 3 or 4 rolls using a small table easy.

The exact procedure for two rolls

For simplicity, let's assume, each roll produces a number $n_i$ from the set $\{0, 1, \ldots, 5\}$.

Extract one bit from each roll as $n_i \bmod 2$.
Compute $3 \cdot \lfloor \frac {n_1}2 \rfloor + \lfloor \frac {n_2}2 \rfloor$, which is number $x \in \{0, \ldots, 8\}$
In case of $x = 8$, you're out of luck and get nothing but the two bits from the first step.
Otherwise, use $x \in \{0, \ldots, 7\}$ as the next three bits.

So, most of the time you get five bits. On the average, you get

$$\frac19 \cdot 2 + \frac89 \cdot 5 = \frac{42}9 = 4\frac23$$

bits as stated above.

There are nearly 5.170 bits in two rolls, but you can't extract 5 bits from them on the average without further aggregation.


Asynchronous Ratcheting Tree and modern group key agreements: Why left balanced-tres used? Nowadays the group key agreements are based upon tree-based ones such as Asynchronous Ratcheting tree. Especially the latter one is constructed upon left-balanced tree.

So I keep wondering what benefits has a left-balanced tree from any other binary tree structure to this application?

In the asynchronous ratchet tree construction, intermediate group keys are constructed at each leaf of the tree.  It's important that all parties agree on the exact structure of the tree so that they will all derive the same keys.  An array is the canonical representation of an ordered list of items, and that array can be viewed as a binary tree.  An array of length $2^n$ corresponds to a complete binary tree, while an array of any other length corresponds to a left-balanced binary tree.

You might find the Messaging Layer Security IETF working group of interest, as I believe at least one of the ART paper's authors is involved in the specification efforts.  The current MLS protocol Internet-Draft restates the ART protocol from a more concrete engineering perspective, so it's very helpful for understanding how everything fits together.


PKCS#1: Purpose of `Padding1` in EMSA-PSS encoding method The central part of the RSASSA-PSS signature scheme of PKCS#1 is the EMSA-PSS encoding operation, described in section 9.1 of the standard.
This encoding method makes use of a padding (titled Padding1) which is simply eight zero-bytes (0x00). The concatenation of this padding, the hash of the message and the randomly chosen salt is then hashed once more, forming one part of the final signature - see eg the ASCII diagram on page 39.
Which brings me to my question - what is the purpose of this padding specifically?
The one effect I could think of is that it ensures that - given an empty salt and an empty message - the input to the hash function will not be empty. However this seems dubious as all hash functions I am aware of will work just fine with empty inputs, and the hash - be it of an empty byte string or a byte string containing 8 * 0x00 - will be deterministic in either case.
The purpose of the second padding - Padding2 - is clear to me, as it ensures that the signature has the desired (user-defined) length, while simultaneously being structured such that the salt can be retrieved without requiring prior knowledge of its length.

I conjecture that this salt is essentially a version number for future extensions, tasked with ensuring that signature per another version using a different salt is not a valid signature for the version described.
I can imagine two other roles:

It makes it even less likely that an RSASSA-PSS signature comes to match an RSA-PSS signature of something pre-existing starting with a hash (but there's also the 0xBC for right padding of EM playing that role). Recall that RSA-PSS was introducted by Mihir Bellare and Phillip Rogaway's The Exact Security of Digital Signatures - How to Sign with RSA and Rabin, in proceedings of EuroCrypt 1996; and it's reduction to practice RSASSA-PSS is a slight variation, as explained in notes of section 9.1 of PKCS#1v2.2.
It makes it less untrue that the hash function / random oracle producing $M'$ is independent from the one producing $\text{mHash}$ and the one used inside MFG1, which arguably is a silent assumption in the security argument.


Is it true the longer the key length is the more secure the encryption? Then why don't we use xxxxxxx bits encryption? what stopping us from using a very lengthy key?
I am referring to the encryption we use with SSL

Is it true the longer the key length is the more secure the encryption?

No. Key length does put an upper bound on security, because it determines the complexity of brute force iteration of the key space or factoring, discrete log, etc. for some asymmetric algorithms. However, once you have a long enough key to make brute force attacks impossible, there is no benefit to a longer key alone, you must have a stronger algorithm in general (e.g. more rounds, larger state or block size) to benefit.

For some asymmetric systems, like RSA, it may seem that you can just increase the numbers and call it a day. However, RSA security rests on the encryption and signature algorithms which probably use symmetric encryption and hash functions that have a constant security, limiting that of the whole algorithm.

As a practical example, RC4 allows up to 2048-bit keys but has biases in the initial keystream no matter which size you use. Meanwhile, many ciphers with 128-bit keys are thought to be secure, like AES-128 or HC-128.

  what stopping us from using a very lengthy key?

Diminishing returns, performance costs and increasing complexity.

The effect of key length on performance is most readily apparent in something like RSA, where modular exponentiation takes about $O(n^{k})$ time for $n$-bit numbers ($k > 2$ depends on the algorithm). Longer keys usually mean longer key schedules, which may be more difficult to analyze, require more constants and code, etc. adding to complexity.


Can you distinguish encryption methods from the output? Suppose that you see all IP communication packets between two computers for a day, as they pass through a connecting router, and this amounts to 10MB. You additionally know that all data transmission follows the standard "RSA-1024 plus AES-128" protocol. To be even more specific, suppose you know only one computer is doing RSA decryption, which computer that is, its specific "public key", and that the RSA decryption is only done to re-initiate the AES key after the other computer is (instantly) rebooted.

Could you look at the 10mb and get any information about whether the computer was rebooted?

I wonder if these pseudo-random streams could be "hashed" in some way to help...e.g., maybe 0.03 bits of information is revealed ("Because of this abnormal X-X-X data series in the stream, there is a 60% chance it was rebooted, instead of the normal 50%.").

I know that any revealing (even a tiny part of a single bit as useless as the rebooting of a computer) is against the goal of this encryption, so I ask in a rigorous way for those familiar with these protocols and their outputs. I truly wonder if there isn't some blatant unencrypted "I need to login from scratch, please!" signal in the standard protocols. When a computer loses its AES key, they could be blatant to help the server, or they could rely on the server to use AES first, conclude it's gibberish, and then try RSA. I'm guessing the latter is done, but hoping for confirmation here.

To answer my own question, I do believe that 0.03 bits would be reasonable, mainly due to the timing of the packets. RSA encryption/decryption takes longer, so delayed responses correlate with a reboot (please notice I'm ignoring the actual power-down time and wrote "instantly rebooted" in the problem statement to focus just on the cryptography).

Note: We need more information on the protocol to confidently answer this, but I know nothing beyond the AES and RSA algorithms.  This is why I ask the question.  So, if you must, please just assume the server URL is "https://whatever.ext" or choose a common reasonable protocol.

Well, with standard protocols (TLS, SSH, IPsec), there really is a blatant unencrypted "I need to login from scratch, please!" message.  That's because when they first come up, they don't share keying material with the peer, and so they can't encrypt any messages.  Instead, they perform some sort of key exchange process using nonencrypted messages, and those messages are easily distinguishable.

Now, I suppose it would be possible to define a protocol where this initial message would be indistinguishable from an encrypted message.  However, the details would appear to be rather finicky (you'd have to worry about message timing and message length), and probably end up being expensive.  In addition, reboots are not actually instantaneous, and when you are rebooting, you obviously can't send out any messages.  I can't think of any scenario where the effort would be worth the cost.


Salt for non-stored passwords I have read a lot about the concept of adding a salt to a password and understand that it protects against various attacks, especially the use of rainbow tables. But this kind of attack is based on getting access to the server side stored-password database.
What if the passwords are never stored? Because the salt is, per definition, not secret, it doesn't help to make a weak password stronger (to my mind, only key stretching will help in this case, right?). Hence an application that encrypts only on the client-side (user enters password > KDF > key > encryption) doesn't seem to have any benefit when feeding a salt into the KDF algorithm.
Is it OK to set the mandatory salt parameter of KDF functions (e.g., PBKDF2) to a hardcoded value? Or have I completely overlooked another salt feature?

If you are dealing with encryption using user-provided passwords, the resulting ciphertext might be attacked using pre-computations à la "dictionary attack", which is the same kind of attacks we are trying to mitigate when using a salt to store passwords.
When encrypting with user provided passwords, the KDF is used as a mean to compensate for the poor entropy of the user passwords, but because you cannot consider the salt to be a secret and you have to provide it to the decrypting party in some way, if you use a salt you will not necessarily increase the "entropy" of your password, because an attacker could simply use the same salt to try and brute-force your key.
In the same manner, a dictionary attack against encrypted data would still work by simply using the same parameters and salt as you do, since these are supposed public (and is even easier if you have a known plaintext-ciphertext pair).
So in the end, you should still be worried about making a dictionary/brute force attack as costly as possible and this is possible with modern KDF such as Argon2 or Balloon, where you can set the parameters, which can be publicly known, in such a way that the attack will become more and more time consuming and costly for the attacker.
So effectively, I agree with you that the salt is not necessarily useful for your use-case, since having a larger initial, secret entropy is more important to protect your data.
But still notice that having a single hard-coded salt will be detrimental to you in the sense that it allows an attacker to "pre-compute" its tables or dictionary attacks for all of your ciphertext at once. This means that using a fixed salt makes the act of cracking multiple ciphertexts on average less costly.
So your use-case benefits from using a KDF, (not just a hash function), with a large iteration number to increase the cost of an attack, and benefits also from using a different random salt for each encryption in order to avoid "pre-computation" attacks that can target all ciphertexts at once. This effectively means each ciphertext would require its very own precomputations and thus it boils down to a bruteforce in the end.
PS: notice that dictionary attacks are only useful when the adversary is able to tell easily whether she has found the correct key or not. Which is typically the case in known plaintext attacks, but not always true for all use-cases.
PPS: I'm not mentioning the pepper since you're aware of its existence given your other question. But a pepper is typically useful in that kind of use-case. Note that the salt, when considered secret is basically a pepper.


Can I update sha-256 digest chunk-wise instead of the whole array at once? I'm not sure whether this questions is about SHA-256 algorithm itself or the particular implementation I'm using.

Usually, a hash algorithm implementation has functions, let us call them update and finalize. update feeds another chunk of data, finalize possibly feeds the last chunk and calculates the digest.

Should passing the whole array at once produce the same hash as passing it's chunks one by one? In other words, update(whole_array) vs update(1st_half); update(2nd_half)

TL;DR: As long as the concatenation of all the binary input to the update / final operations, in order is identical then the secure hash function should return the same output hash.

The hash function implementations generally have a buffer the size of the block size. This internal block size is generally hidden to the user. For SHA-256 the block size is 512 bits, 64 bytes or - as SHA-256 is build using 32-bit operations - sixteen 32-bit words.

So what happens is that during update the buffer is filled until it is full, which is then processed by the internal compression function, altering the internal state. Then the buffer is filled again and again until all the blocks have been processed. The last part of the update will leave the buffer empty or partially filled. When a new update is processed the whole situation is repeated, starting with the values in the buffer from the last update (if any).

When the final is called then the input data for the final operation is processed as if it was an update. Then the internal bit padding (a one bit followed by X zero bits) takes place and the encoding of the total length is added. This forms the last one or two blocks which are then processed in order.

So with the description above, it is clear that passing the whole array at once produce the same hash as passing it's chunks one by one. This is because the the same buffers will be processed and the internal state will therefore be updated in exactly the same way. The required padding and total length is the same as well. That's all the input to the block operations within SHA-2 so the final output must be identical too.

If you get a different result then you may have run into encoding issues. SHA-2 processes binary data: bits or - for most implementations - bytes. If you perform a different encoding on a string (e.g. UTF-8 vs UTF-8 with Byte Order Mark) then the input will differ and the hash result will differ as well. In principle, the implementation could be faulty as well, but usually this is not the case; there aren't all that many input variants / edge cases to test and test vectors exist.

Notes:

It depends on the implementation if the final operation can contain input data or not. If it does it is identical to having an additional update with the given data and then performing the final operation with the padding and length encoding.
SHA-224 uses the same block size / 32-bit operations as SHA-256; SHA-512 uses 1024 bit blocks and 64-bit operations internally, and so does SHA-384 and the less common SHA-512/224 and SHA-512/256 hash functions.
SHA-3 uses a different internal scheme (a construction using a sponge instead of a Merkle-Damgard construction) but the description of the buffering and block size is still valid.


Super basic questions to DLP and DH This is a super basic cryptography and I don't get it. My professor only explained it to us on a very abstract level, which I just agreed to without questioning it.
The DLP says it is easy to calculate a^x, but it is not easy to find x with a logarithm if you use a cyclic group. The idea behind the cyclic group is to shuffle the numbers. If you don't do it, you can guess your way to the exponent, because the numbers are ordered and you know if you get a two high or two low number, you can guess in the right direciton.
So very abstract, I do get it. But very concrete, I don't.
What I don't get
I mean, with the DH Alice send g^x and g, Bob sends g^y. So the evil person gets both g, g^x and g^y. And she wants to find log_g(g^x) which gives her x. What is her problem? She knows g and she knows what what the number (g^x) is.
I mean, I don't know how to type this in on a calculator because we only used log_e (also called ln) and log_10 (which is just log on my calculator). If I take my calculator and I type log(100), which is log_10(100), I get 2. Which is the number I looked for. Why can't Eve do the same?
Sorry, this is a very stupid question, but I am too emeberassed to ask anyone else than you ^^

Kudos for the question's critical thinking. Keep on with that attitude!

Eve wants to find $\log_g(g^x)$ which gives her $x$. Why is it a problem? She knows $g$ and she knows what the number $g^x$ is.

The problem as stated in this quote and with $g$ in the set $\mathbb Z$ (the integers) is the logarithm problem restricted to integers, and indeed is easy. Just by looking at the size of $g^x$ (the number of digits in decimal), it's easy to get an idea of how large $x$ is. For example if $g$ is $11$, $g^x$ will have a little over $x$ decimal digits. More generaly, $x$ is $\log(g^x)/\log(g)$, computed over the reals with the logarithm in any base.
In the discrete logarithm problem, $g^x$ is not computed by regular integer multiplications. It's computed in a finite set with group structure. $g^x$ is constrained to be in the same finite set as $g$ is, no matter how large $x$. That makes a huge difference, because Eve always gets a small value, thus techniques based on the size of $g^x$ will no longer work.
The simplest group usable is the multiplicative group modulo a safe prime $p$. In this group, $u*v$ is defined as the remainder of the Euclidean division of $u\cdot v$ by $p$, where $u\cdot v$ is the ordinary product. $g^x$ is defined as usual:$$g^x=\underbrace{g*g\ldots g*g}_{x\text{ terms}}$$
where each $*$ is an operation in the finite set. Note that $g^x$ can be computed with $\approx1.5\log_2(x)$ modular multiplications, rather than the obvious $x-1$.
To convince you things are hard, try with $p=31469$ (small enough that $u\cdot v$ fits 9 decimal digits), $g=3$, $g^x=11292$. How do you get $x$?
One simple method is to try all $x$ sequentially, that has cost $\Theta(p)$ (note that we can move to the next power of $g$ with a single modular multiplication). A better method is baby-step/giant-step, that has cost $\Theta(\sqrt p)$ in work and memory. Yet a better (probabilistic) method is Pollard's rho, which also requires $\Theta(\sqrt p)$ work but reduces memory requirements to $\Theta(1)$, and can largely be parallelized.
Because we use a particularly simple group, there are even better methods. However, with e.g. Elliptic Curve groups, we don't know a much better method that works on computers as we know them. Thus if we use a suitable group with enough elements (e.g. in the order of $2^{256}$), the best way we know to get $x$ requires in the order of $2^{128}$ group operations on computers as we know them.


How secure is using a hash function as Key Derivation Function? I am developing a personal project and I have the following need:
given a randomly generated seed (with enough entropy) I need to generate a number $x$ of Ed25519 key pairs.
These key pairs are not stored. Therefore I need to generate with this seed the exact same key pairs anytime.

To achieve that I have the following algorithm to generate one address number $y$:

I concatenate the seed and $y$ and I calculate the SHA-3 hash: hash = SHA-3(seed+y).
Using this hash I generate an Ed25519 key pair using this hash as a seed: keyPairY = new ed25519KeyPair(hash) (ed25519KeyPair is nacl.sign.keyPair.fromSeed which expects a seed as its argument).

How secure is this kind of algorithm?

This is reasonable as long as (a) you mean some unique encoding of the seed and index $y$ when you say seed + y, (b) you never use the same seed and index for another purpose, and (c) you chose SHA3-256, or SHAKE128-256, or SHAKE256-256, and you are using the standard Ed25519 32-byte pre-master secret seed as the secret.  For (a): if, e.g., the seed is always exactly 32 bytes, you can use concatenation.  If the seed may vary in length, you might consider concatenating $n \mathbin\Vert \mathit{seed} \mathbin\Vert y$ where $n$ is the number of bytes in the seed so that there are no pairs of $(\mathit{seed}, y)$ that might be confounded by concatenation.

Note that the answer is specific to the SHA-3 functions above.  This does not apply to everything that might be called a hash function.  It is certainly not true of GHASH.  It doesn't even apply to SHA-256 unless you impose the additional constraint on the seed and the index that their lengths each be fixed, or that their encodings be length-prefixed.  This is because given $h = \operatorname{SHA256}(\mathit{seed} \mathbin\Vert y)$, it is easy to compute $\operatorname{SHA256}(\operatorname{pad}(\mathit{seed} \mathbin\Vert y) \mathbin\Vert y')$ without knowing the seed—the standard length-extension attack on SHA-256.  If you must use SHA-256 with variable-length seeds and indices (which it sounds like you needn't, but other passersby might read this), it may be simpler to just use it with HMAC to make a PRF, if not HKDF.

Generally, you should consider using something tailored for the purpose unless you have constraints ruling it out: KMAC, if you want a Keccak-based PRF; HKDF, if you must use SHA-2 and you want structured inputs for application and purpose labels.


Is $(f(X), G(X))$ pseudorandom? If $f:\{0,1\}^n \to \{0, 1\}^n$ is a one-way function, $G:\{0, 1\}^n \to \{0, 1\}^m$ is a pseudorandom generator, and $U_m$ is the uniform distribution over $m$-bit strings. Is the joint distribution $(f(X), G(X))$ computationally indistinguishable from $(f(X), U_m)$, for uniformly chosen $X$?

The person who asked the original questions seems to have deleted the account, so here's a full solution for future reference instead of just a hint:

Assume that $G':\{0,1\}^{n-1}\to\{0,1\}^{m-1}$ is pseudorandom and $f':\{0,1\}^{n-1}\times \{0,1\}^{n-1}$ a one-way function. We construct the functions
$f:\{0,1\}^n\to \{0,1\}^n$ and $G:\{0,1\}^n\to \{0,1\}^m$ as follows

$$f(x) = x_1f'(x_{2,\ldots,n}),\;\; G(x)=x_1G'(x_{2,\ldots,n}),$$

where $x_1$ denotes the first bit of the input and $x_{2,\ldots,n}$ the remaining bits. Clearly, $f$ is one-way and $G$ is a pseudorandom generator. As distributions, we then have

$$G(U_n) = U_1 G'(U_{n-1})$$

and

$$f(U_n) = U_1 f'(U_{n-1}).$$

It's then trivial to construct a distinguisher for $(f(U_n),G(U_n))$ and $(f(U_n),U_m)$. The distinguisher gets as input a pair $(x,y)$ and checks whether the bits $x_1=y_1$. If this holds it will return $1$ and if $x_1\neq y_1$ it returns $0$. If the input comes from $(f(U_n),G(U_n))$ we always return $1$ and in the other case we return $1$ by probability $1/2$. The distinguisher therefore has advantage $1/2$, so the distribution $(f(U_n),G(U_n))$ is clearly not pseudorandom.


How can rainbow tables be used for a dictionary attack? I'm putting together a password policy for my company.  I very much want to avoid requiring complex passwords, and would much rather require length.

The maximum length I can enforce is 14 characters.  I can calculate that 14 random lower case characters is stronger than 8 characters using anything on the keyboard.  However I'm suggesting that people use phrases, song titles, things like that.

I don't think I need to protect against someone guessing passwords since our system will lock you out after 5 failures.  I imagine I'm protecting against someone stealing the hashes of our passwords.
Thus I imagine the mode of attack, if there was one, would be via rainbow tables.

I think 14 random lower case characters is reasonably safe against rainbow tables (we have Windows Server 2008 which I understand eliminates the LM compatibility weakness).  However if phrases are used, there are many less possibilities than random characters would have.

Does anyone know if rainbow tables can be designed in conjunction with dictionary words, say by tokenizing them?

Along with this, I believe that NTLM passwords are hashed but not salted - does anyone know if that is true?  If it turns out that they're salted, then I think I have little to worry about.

Finding a decent explanation of rainbow tables was something I struggled with, so firstly I'll cover what they are. I will get to your question in the end. My sources for this are this guide and the wikipedia article.

Why can't I just use a big bucket of hashes?

Firstly the naive way to build a reverse lookup table is this. Let's say we want to generate all the hashes for every 8-digit password in existence, using the set [A-Za-z0-9]. In that case there are 62 unique characters and with that, using the counting function $n^r$ where $n$ is the possible number of outputs and $r$ is the number of choices we can make, then there are $218340105584896$ possible strings in this output space. Navely storing this data we can take a 8 character string as taking 8 bits per character (so each string costs 64 bits) plus a separator character plus the 256-bit output of say sha256, the total cost is then $218340105584896(64+1+256) = 70087173892751616$ bits. Converting that to bytes, i.e. $\frac{70087173892751616}{8*(1024)^3} \approx 8159220$ gigabytes.

Two notes on this:

It only considers exactly 8-character passwords. If you want to consider passwords containing 4-8 entries, you need $62^4+62^5+62^6+62^7+62^8$.
It assumes you're actually going to store that data in raw form. There are probably better ways to handle this.

So the first problem is storage. Above, we simply computed the total output space of a hash function.

What is a rainbow table?

The idea behind rainbow tables is to offset the space issue. To this end, let's define a few things: firstly we have a search domain we'll call $\mathbb{P}$ and a hash output domain we'll call $\mathbb{H}$. Then we have a hash we want to invert we'll define as $\mathcal{H}: \mathbb{P} \rightarrow \mathbb{H}$. i.e. the hash function takes an element of the search domain and produces a value in the hash output domain.

We then introduce a concept called chaining. To do this, consider we could define a function that maps the other way fairly trivially; let's call it $\mathcal{R}: \mathbb{H} \rightarrow \mathbb{P}$. In a rainbow table, a chain starts with a starting value and applies $\mathcal{H}$ then a $\mathcal{R}$ alternately, but always in pairs such that when done you end up with the first and last elements $p_0, p_k \in \mathbb{P}$. This is what you store.

A rainbow table is slightly more complicated than using the same $\mathcal{R}$ for each pair; this has problems relating to collisions. If two chains produce the same value they converge, meaning we waste time spend computing said chains - this is a chain collision. I had trouble visualizing this, so drawing a diagram:

a_1 ----> a_2 ----> a_3 / b_2 --> a_4 / b_3 --> a_5 / b_4 ---> a_6 / b_5
                        |                                         |
b_1 ---------------------                                         -----> b_6.

Instead, a set of functions $\{\mathcal{R}_0, \ldots, \mathcal{R}_{k-1}\}$ are applied, one for each pair of the chain. SO when chains merge using this setup, they always produce the same final value and can then be de-duplicated, saving space - detection of wasted space is also much easier on generation.

Then:

Generating rainbow tables: pick a length $k$ and define the functions $\mathcal{R}_{0}, \ldots, \mathcal{R}_{k-1}$. Then, for a given input $p \in \mathbb{P}$ we compute $c_0 = p, c_{n+1} = \mathcal{R}_{n-1}(r_{n}), r_{n} = \mathcal{H}(c_{n})\;\;(n=0,1,2,\ldots, k)$. These $c$ form a chain $C$. We compute our chains and for each chain we store just the pair $(c_0, c_k)$.
Searching a rainbow table. Now, assume we want to inverse a hash value $h$. To do this we run through this process, starting with $i=k-1$:

Generate chain for $h$ starting at $R_{i}$
Using the end-value of the above chain, search our list of end values for computed chains. If we find a matching end-value, compute its chain term at a time (we can do this because we know the start value). If we find $h$ as say $r_n$ in that chain then the corresponding $c_n$ value is the inverse of $h$. Stop. If we don't find the end value in the chain list, carry on. If we don't find the hash in a generated chain where we did find the chain value, carry on.
If $i \neq 0$ do $i=i-1$ and go back to 1.
If we get here, we haven't found the inverse.

Right so exactly what is the benefit?

It's a space/time trade off. Specifically, the reverse lookup table takes a lot of space. This is a scheme that takes less space, but requires more time per lookup to work. Since the size of a complete reverse table is prohibitive for most people, the increased computational cost is generally preferable. Storage space is reduced massively, but is actually harder to calculate as it depends on $k$, and the $\mathcal{R}$ you use.

Clearly, also, we have different options with rainbow tables in terms of the length of $k$. The longer $k$, the fewer the number of total chains before all elements in $\mathbb{P}$ are covered. However, that also increases the run time of a lookup.

Oh no, now I have no idea how salt comes into this?!

Salt increases the size of $\mathbb{P}$ by increasing the $r$ in $n^r$. This makes both an inverse hash list astronomically big and also increases the size and computation time required for a rainbow table, too.

An attacker then has two options:

Produce a rainbow table specific to a given salt, making it invalid for a different salt.
Produce a huge rainbow table.

And what about slow hashing functions?

So far we've mostly talked about space as a consideration, without regards to the time taken to look up a function. Most cryptographic hashes are designed to be fairly quick, so this is ultimately feasible to do for say MD5.

Now what happens if we choose $\mathcal{H}$ which we know takes approximately a second to calculate each hash? Assuming there are no shortcuts that remove this additional time cost, the giant inverse table will take $218340105584896$ seconds, or approximately $6923519$ years. Your rainbow table is going to take a long time to generate too - assuming you never have collisions and cover the whole domain, just as long as a hash reverse lookup, plus added cost to search, depending on the length of $k$.

Combining both is a fairly effective defense against a rainbow table, making it both specific to a given salt and expensive to generate and use.

Why do password policies mention things like character classes, e.g. must have an upper case, must have a piece of punctuation?

We defined $\mathbb{P}$ as the set [A-Za-z0-9]. If you add punctuation into the mix you increase the size of $\mathbb{P}$ again, and so increase the size of the rainbow table (number of chains needed) again. Password length requirements also do this.

So dictionaries?

The whole premise behind a rather famous XKCD comic is the idea of information entropy. To tread roughshod over a fairly interesting area of science (sorry!) basically what you say is that whilst the total permutations of $\mathbb{P}$ are large, actually, quite a lot of those are totally meaningless to humans and we would not, given a choice, use them. Said XKCD comic was saying that actually, if you make certain judgements about the likely format of passwords, using information entropy as a measure of uncertainty within these formats then longer pass-phrases actually score better than shorter complicated passwords.

There is no reason you cannot produce a rainbow table using a set of reduction functions that takes this sort of assumption into account.

A dictionary is just a simplified version of this guessing - namely you're making the assumption that the thing you are inverting is actually a known dictionary word. You could also generate a rainbow table with known dictionary pass-phrases.

In both cases you are reducing $\mathbb{P}$ which by extension decreases the size of the rainbow table and the time to perform a lookup; however, such a technique is susceptible to the fact your approximate representation of a password just might not be right.

What's the complexity of rainbow tables?

Suppose we want to build a rainbow table to cover a set of $N$ potential passwords.  (In other words, $N = |\mathbb{P}|$.)  Let $t$ denote the average chain length; this is a parameter that you can choose freely, to optimize the cost of the attack.

Then, the cost of building the table is about $1.7N$ hash computations (yes, it is 70% more expensive than a simple exhaustive search on the set). The storage cost is $N/t$ elements of size at least $\lg N$ (but not necessarily much bigger). Attacking a password has cost about $t^2/2$ hash computations, and $t$ lookups (a "lookup" is when you are actually looking for data in the harddisk; it is typically much slower than a hash computation).


OAEP security with variable length hash function I'm implementing a hobby cryptosystem for fun and to increase my knowledge on the subject, and I was wondering if the OAEP construct was still sufficient as an all-or-nothing-transform if variable length hash functions (specifically SHAKE256) are used for the $G$ and $H$ random oracles.

I already found a paper showing that OAEP was functional as an all-or-nothing-transform, but I'd like to use SHAKE256 as a hash function because it allows for arbitrary-length messages.

My current implementation is here. I pad the message to a minimum of 32 bytes, and then then my $k0$ length, or the length of the additional information added, is another 32 bytes.

I'm wondering if this use of SHAKE256 is theoretically secure, or if there is a problem with using a variable output hash function with OAEP. I'm not concerned with side channel attacks, this is a purely educational implementation.

Beware that if $n < m$, then $\operatorname{SHAKE256-}\!n(x)$ is a prefix of $\operatorname{SHAKE256-}\!m(x)$, so the two functions are not really independent random oracles as the usual OAEP theorems posit.

If you set $G(x) = \operatorname{SHAKE256}(0 \mathbin\| x)$ and $H(s) = \operatorname{SHAKE256}(1 \mathbin\| s)$, that should be adequate to (conjecturally) satisfy the hypotheses of the theorems without requiring additional analysis to study the possibility of collisions between the inputs to $G$ and $H$.

Alternatively, if the inputs to $G$ and $H$ are guaranteed to have distinct lengths in your application, then $G(x) = \operatorname{SHAKE256}(x)$ and $H(s) = \operatorname{SHAKE256}(s)$ should work too.  But it won't hurt, and might be safer to avoid mistakes, if you always use a unique prefix, whether it be a 0 bit vs. a 1 bit, or the string G oracle vs. H oracle, etc.


ECDSA Signing and verifying signatures between Python and JS I create a signature on js, here jsrsasign
Signatures are obtained in the format:

3045022045c61e649ca9f6011a8d34ac865c4780421de08ff50ac3dad0da36043b6de478022100b19208d1ec51f6dd6f6b725342618f55f9fc90c96c5b5409998d66774749a0b

Always start with 30 ...
In Python, I use the python-ecdsa library.
In this library, the signature format is

a8c7dd7e9b669b1bc841ddf66bc08b10bc1112fa14fce2a5a2246edf997c577450af6b9edfe373546e17ab7363c097ab468db04ed707fb65992e20eabfd1bf40

Therefore, verification does not occur.
How to bring signatures to one format?

An ECDSA signature is, formally, a pair of integers $(r,s)$. There are two main conventions for encoding these integers into bytes:

Encode both integers into unsigned big-endian, using the same size for both, and concatenate the values. This is the traditional way in, for instance, PKCS#11 and OpenPGP; python-ecdsa apparently uses that format.
Encode the integers as an ASN.1/DER structure (a SEQUENCE of two INTEGER values). This is what is normally used in everything that relates to X.509 certificates, and also in SSL/TLS exchanges. jsrsasign apparently uses that format.

Conversion between these formats can be done, but it is surprisingly tricky to do correctly (it's a parser, after all). It seems that python-ecdsa can also encode and decode ASN.1-based signatures (see the functions sigencode_der() and sigdecode_der(), for instance).


Using Keccak permutation as a block cipher The inverse of Keccak is slow, but if you have a problem where that is not a concern would this be a secure cipher? The encryption function can be made incredibly fast in hardware. Or the reverse if you choose to encrypt using the inverse.

Is there any cryptanalysis of block ciphers that are unbalanced in such a fashion? Inverse being more expensive and having different diffusion properties.

The round constant step (used to break symmetry) in the round function is the only thing that needs to be changed to employ a key schedule.

The nonlinear step is worrisome, they use a simple cellular automaton rule: flip bit if pattern 01 is to its right (and wrap around). This makes invertability cumbersome for an arbitrary odd length input (not possible for even length), but they use it for just a 5 bit input which just makes it a trivial 2^5 S-box - is it a good one? 0* maps to 0* and 1* to 1* for example.

PS: * means repetition, in the case of keccak 1* = 11111

First, this is a slightly silly exercise because most applications are not well-served by a block cipher in particular but rather by things built out of them, such as authenticated encryption schemes.  Probably the most widely used authenticated encryption scheme today built out of AES, AES-GCM, doesn't even use the inverse direction, and would provide better security bounds if AES were a pseudorandom function family rather than a pseudorandom permutation family.  And there are already perfectly good authenticated encryption schemes built out of Keccak, such as Ketje and Keyak, both submitted to CAESAR.

But let's take the exercise at face value and suppose you really do want a block cipher.  The obvious way to get a block cipher out of Keccak is with a single-key Even–Mansour construction analyzed by Dunkelman, Keller, and Shamir.  Specifically, for a $b$-bit permutation $F$ (standard SHA-3 has $b = 1600$, but there are shorter variants, such as $b = 200$ used by Ketje for environments with tight resource constraints), we can define, for $b$-bit keys $k$, the $b$-bit block cipher $$E_k(m) = F(m \oplus k) \oplus k.$$  Since collision-resistance is not relevant to this application, instead of the standard $\operatorname{Keccak-\mathit{f}}[b] = \operatorname{Keccak-\mathit{p}}[b, n_r]$ permutation where $n_r = 12 + 2\log_2 (b/25)$ is the standard number of rounds, we might consider a much smaller number $n_r$ of rounds, as you will find Ketje and Keyak use.

Maybe a 1600-bit key seems excessive for a standard 128-bit security level.  Maybe you could make do with a smaller key, padding it with zeros, $$E_k(m) = F(m \oplus (k \mathbin\Vert 0^{b - 256})) \oplus (k \mathbin\Vert 0^{b - 256}).$$  I haven't done the analysis of a padded-key variant of Even–Mansour; maybe if you read the Dunkelman, Keller, and Shamir paper you'll find an obvious answer.  But we can always derive longer keys from shorter keys using standard functions like HKDF, or even Keccak-based ones like SHAKE256 or KMAC.  So unless you have an amazingly constrained application requiring (a) squeezing out those last few cycles, and (b) a novel Keccak-based block cipher, those cycles are probably not worth the effort to figure out the detailed security analysis!  Thus I leave it as an extra-credit exercise for the reader which will not affect your standard grade.


Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order In regular ElGamal and DSA, we choose large primes $p$ and $q$ such that $p\equiv 1\pmod{q}$, and a group element $g$ of order $q$ by computing $a^{(p-1)/q}$ for some random $a$. This is to prevent smooth group order which can then be factorized, and the discrete log problem can be solved by Pohlig-Hellman algorithm.

How can the same be accomplished for a group of points on an elliptic curve over finite field?

Make sure the group order is not smooth
Find an element of large prime order $q$.

For the curves used in cryptography today, the order of the group of points is typically 256 bits, sometimes 512. Such numbers are within the range of current factoring algorithms (indeed, this is why you don't use 512-bit RSA keys), and so typically the order of the group can be factored and it is easy to see whether it has a large prime factor.

Moreover, standard curves such as the NIST curves or Curve25519 are chosen so that the order of the group of points is either prime (as in the NIST curves) or is a large prime multiplied by a small cofactor ($8$ in the case of Curve25519), so if you use a standard curve you know there is a subgroup of large prime order for you to work in. (It is important that you work in a group of prime order to prevent other types of attacks.)


MD5 - What happens if message is exactly 64bit block size message? Based on RFC 1321 after we recive a message if message size is less than 64 Byte we will append it with a 0x80 and message length + zeroes until it's 64 bit and then generate the digest.

The question is what will happen to exact 64 Byte? based on specification:

  Padding is always performed, even if the length of the message is
     already congruent to 448, modulo 512.

But how is that possible?
You can't append length and other things to it? if it's for example 128 byte
then I think 64 byte message digest would be same as 128 bit digest?

Padding can be expressed as follows:

Append a bit of value 1.
Append between 0 and 511 bits of value 0. The number of bits to append here must be such that the total length after padding is a multiple of 512.
Append the encoding of the length of the message (not counting the padding bits). That encoding always has size exactly 64 bits.

So, if your input has size 448 bits, then:

After adding the bit of value 1, you get a total length of 449 bits.
You will need to add exactly 511 bits of value 0. Otherwise, the final length won't be a multiple of 512. With these extra 511 bits, length is now 960 bits.
With the length encoding, size is now 960 + 64 = 1024, which is indeed a multiple of 512.

The padded input is then split into blocks of 512 bits, processed in due order.

The sentence in the RFC about a length exactly equal to 448 is meant to clarify the process, in that the extra bit of value 1 is always added. That bit is not optional.

Formally, MD5 takes as input a sequence of bits. However, in most situations, we only hash sequences of bytes. In other words, the input length will always be a multiple of 8. The padding process, when expressed with bytes, becomes:

Append a byte of value 0x80.
Append between 0 and 63 bytes of value 0x00. The number of bytes to append here must be such that the total length (in bytes) after padding is a multiple of 64.
Append the encoding of the length of the message (not counting the padding bytes). That encoding always has size exactly 8 bytes. The length is expressed in bits, i.e. it is eight times larger than the length in bytes.

The padded input is then split into blocks of 64 bytes, processed in due order.

This padding procedure is exactly the same as the one defined for bits; it is just expressed here from a byte-oriented viewpoint.


Universal hashing techniques based on matrix multiplication The article here says below, about a universal hashing technique based on matrix multiplications.

"However, there is a little known method based on using a random matrix. It has lots of advantages - it's a universal family"

I tried to hard to find the source paper of the same to dig deeper but could not. Any references about the technique ?

The source of this result, although it can be found in many other places, is the  Wegman-Carter paper 'Universal classes of hash functions'. More specifically, Proposition 9 in page 151.


Is it fair to assume that SHA1 collisions won't occur on a set of <100k strings I'm building a system that has to take file paths, and generate a unique name for each one. I'm planning on using SHA1 as the hash function.  My question is: do I have to deal with possible collisions (2 different paths producing the same SHA1 value) or can I assume it won't occur?

The chance of a collision in such a set is approximately $ \frac{1/2 \cdot n^2}{2^{160}} $, which for n=100k evaluates to about $ 3.4 \cdot 10^{-39} $. So it is fair to say, such a collision won't occur accidentially.

AFAIK nobody has ever found a SHA-1 collision The only concrete SHA1 collision to date was Google's on February 23rd, 2017 (found here). Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes.

If cryptoanalysis advances, an attacker might be able to create inputs that deliberately collide. Currently, however, there is no known way to do this efficiently. Of course, this only applies if your application needs to protect against deliberate collisions; many applications only require protection against accidental collisions. If you need protection against deliberate collisions, I'd prefer SHA-2 over SHA-1.


Can we find the exact number given remainder of the numbers with mod m? I have around 1500 numbers. The numbers $x_i$ are calculated as
$x_i$=($p*t_i$) mod m. $p$ constant and same for all the numbers while $t_i$ are chosen randomly everytime. For example the given numbers $x_i$'s are calculated as:

$x_1$=($p*t_1$) mod m.

$x_2$=($p*t_2$) mod m.

.
.
.

$x_{1500}$=($p*t_{1500}$) mod m.

given $x_i$'s and m, can we find the p using above $x_{i}$'s ?

If you know $m$ and the $x_i$ but not the $t_i$ then there's no way to find $p$ in general. For example, suppose that $m$ is prime. Then, for any $p \ne 0$, there is a set of suitable $t_i$, given by $t_i = p^{-1} x_i$. The only value for $p$ that may be impossible is $0$, which is possible only if all the $x_i$ are zero.

More generally, the only information you can have about $p$ is to rule out certain factors in common with $m$. If $k$ is a factor of $m$ and the $x_i$ are not all multiples of $k$ then $p$ cannot be a multiple of $k$ either. That's all the information you have about $p$.

(Note that in this answer, I work modulo $m$, so e.g. when I write $p \ne 0$ I mean $p \ne 0 \pmod m$.)


computing INV in boolean circuit for MPC Is it feasible to generate an efficient MPC function that compute $a^{-1}$ for $a \in \mathbb{F_q}$, with Boolean circuit?

The naive way seems impossible since the depth of the computation might needed to be known in advance. (for example in computation of Extended GCD).

Edit: my intentions for the question were: Is there a more way to compute inverse instead of using EGCD (i.e a similar way to compute the INV that is more suitable to transfer to MPC)

Thanks.

Boolean circuits are Turing complete and so the answer is yes for any computation. Specifically, for this case, the circuit will assume that the loop never exits early (and if it finishes early, then the circuit will not change the result). In general, if you need to compute a branch in a circuit, then the circuit will always have both branches.

If your question is about efficiency, then there may be more efficient ways to compute this than in a circuit. For example, use MPC to compute $r\cdot a$ where $r$ is an unknown random value. Then, the parties compute $b=(r\cdot a)^{-1} \bmod q$, and then securely compute $r \cdot b$. This result is $a^{-1} \bmod q$. There are many ways to do this, using homomorphic encryption (e.g., Paillier), OT and so on. However, the main challenge is to prevent cheating, if you want malicious security. It also depends if you are looking at the honest majority or dishonest majority setting. For an honest majority, one just uses standard techniques to generate a secret sharing of $r$. The parties then run secure multiplication on shared values to get $r\cdot a$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $r$ with  $b$ to get shares of $a^{-1} \bmod q$.


Hash based stream cipher where the input is a constant, key, nonce and counter This is a question out of curiosity !

A hash function produces an output that is considered computationally infeasible to reverse.

Let's consider, for the sake of illustration purposes a tried and tested hash function like SHA 256, belonging to any of the families ( 2 or 3). Since the block size for SHA 256 is 512 bits or 64 bytes, we could fill it in the following way, inspired by the ChaCha20 stream cipher.

cccc cccc cccc cccc kkkk kkkk kkkk kkkk kkkk kkkk kkkk kkkk bbbb nnnn nnnn nnnn

c - some fixed constants
k - key
n - nonce
b - counter (32 bits)

Each letter strings corresponds to a byte.

NOTE : The constants could be sacrificed for nonce bytes, hence facilitating a random IV, of bit length >= 128 bits. The counter could also be made to support 64 bits the same way.

We could generate $2^{n} . (blocksize/2)$ bytes of pseudo random key stream, that could be XORed with the plaintext to get ciphertext, where $n$ is the bit length of  the counter, $blocksize$ is the block size (in bytes) of the hash function, used.
In this case $blocksize$ is 64 for SHA 256...

Let the counter used be $n$ bits. There are $2^{n}$ possible values for the counter. Since output of the hash function   is $blocksize / 2 $ bytes for any individual value of the counter, the scheme can generate a maximum of $2^{n} . (blocksize/2)$ bytes.

Here $n = 32$ so we get, $(2^{32}) . (64/2)$ bytes.

I realize that, giving $x$ bytes of input (where $x$ = len(constants) + len(key) + len(nonce) + len(counter) ) and getting $x/2$ bytes as output from the hash function is a kind of inefficiency (SHA - 256), given the fact that the hash function has to run once more (for every input block of size $x$, (additional data of size $x$)) with MD complaint padding information (byte 0x80 followed by $55$ null bytes, and $8$ byte length encoding) . That could cost double CPU clock cycles, for every call to a stream generating function.

In the case of SHA 256 $x = 64$ bytes.

Also,
This scheme, is extremely inefficient compared to other stream ciphers available like Chacha20 / Salsa20 !

But,

Is this a good scheme ?
What are the possible security flaws,    (theoretical/implementation)
in this protocol?
If this is secure, can this scheme offer $256$ bit security ?
What are the possible Quantum attacks on this scheme ?
Since SHA-256 family of hash functions is immune to side channel attacks, will that be an added advantage?

Every advice and guidance, will be greatly appreciated! :)

Sure, you can do this. Officially the output of a hash function is not directly designed for this, but the output of SHA-256 is no doubt randomized enough to be used as a base for a stream cipher. And actually, ChaCha & Salsa use what is basically the same approach, but with a different PRF (compared with a PRP when a block cipher is used).

Of course, the devil is in the details. The nonce (96 bits) and counter (32 bits) are rather on the short side. Besides that, they don't follow the convention of having the more static nonce first and the counter next. Having a nonce for domain separation is nice, but as the key should be fully randomized, I guess it is not strictly required for this scheme.

As for the applicability: you haven't specified any padding scheme, and you do seem to be using the full 512 bit block size. That means you should have access to the low level block-based SHA-256 functionality to implement the scheme. Otherwise you would have two full blocks of SHA-256 to perform for one 256 bit output and one block with the padding and length encoding. The output is then the output of the last block operation (which also depends on the first one as the state is maintained). So in that case you would have a 4 x drawback compared with using a normal stream cipher at the minimum when using the full SHA-256.

If you are using the block size then you could define separate SHA-256 constants for the starting state instead of trying to shoe-horn them into the input block.

Generally the hash functions don't use table lookups and should be relatively safe against side channel attacks. Of course, side channel attacks are implementation dependent, so this detail is not a final verdict for any system.

A minor note: although logical, the output is not entirely related to the input block size for generic hash functions. So specifying $n / 2$ as output size feels a bit strange to me.


Security requirements for EC Diffie Hellman implementation I'm working on a crypto library to be used in a firmware product.
Beside other things we need key agreement based on Diffie Hellman.

Since resources are very limited we use a crypto accelerator on the MCU for which a low level library exists, allowing beside other things to make elementary calculations on elliptic curves over $GF(p)$ and $GF(2^p)$.

Now I tried Diffie Hellman and tested the results against various test vectors. It works fine.

But, of course, I know that this self-made approach can be dangerous, when the detailed implementation is open for attacks, whatsoever kind of.

So the question: What requirements must be considered additionally to plain algorithms in order to make the outcome a "secure" solution?

To make a statement to the answers below:

1) We must use P-256 (it's not a choice)

2) What do you mean with large private multiplier? In my implemantation the private key is taken randomly between $ 1 \ldots 2^{256}$ (32 Bytes) and then reduced to modulo group order. Is this acceptable?

3) I use a hardware RNG (TRNG).

4) We must use KDF specified within NIST 800-56A Rev2

5) The other side is authenticated by ECDSA based on a certifcate

6)

  side channel resistance is a hairy issue

I have to larn about what this is

7)

  If you only have the really basic operations: make sure your scalar
  multiplication is constant-time.

Why is this required?

Here's the obvious advice (other than "don't roll your own protocol/solution; reuse one that has already been vetted"):

Make sure that you use a secure curve.  Obvious alternatives are P256 (with possible P224 or P192 if you need better performance, and don't mind cutting into the security somewhat), or (if you don't trust the US Government) a NUMS curve or a Brainpool curve.  Normally, I'd suggest Curve25519; however if you have a crypto accelerator that's targeted towards arbitrary curves in Weierstrass form, well, it could do Curve25519, but it's more hassle, and you lose the advantages you normally gain from Curve25519.
Make sure that you use a large sized private multiplier; for P256 (or any other curve based on a 256 bit prime), that means a 256 bit multiplier (and note: this doesn't mean that the 255th bit must be set; it means that all values between 1 and $2^{256}$ are possible).  You can make things go a bit faster if you use a smaller range, however that also cuts into the security.
Both sides need good entropy; if the attacker can guess the private multiplier of either side (or even reduce it to a not-huge subspace), he can recover the shared secret.
Validate the point that you receive from the other side, that it is a point on the curve; for example, if the other side sends both $x$ and $y$ coordinates, make sure that when you plug them into the Elliptic Curve equation, both sides evaluate to the same value.  There are cases where you can skip this (for example, if you use "point compression", or if you always generate a fresh random private multiplier for each exchange), however it's so cheap that it just makes sense.
Use a good KDF to convert the ECDH shared secret into the keys that you'll actually use.
Remember that ECDH does not authenticate who you're actually talking to.  Unless no one other than the person you're talking to can possible send (or modify) a message to you, you need a way to authenticate the other side.


How does the key schedule of Rijndael looks for keysizes other than 128 bit? It said in Wikipedia that:

  [....] Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The blocksize has a maximum of 256 bits, but the keysize has no theoretical maximum.

How would the key schedule look for these other key sizes, like a 136-bit key?

Rijndael (the algorithm behind AES) is specified with block sizes and key sizes of  128, 160, 192, 224 and 256, in any combination of block and key size. (Thus, Wikipedia was wrong with the keysize has no theoretical maximum here, though one could invent extensions of the key schedule algorithm which allow longer keys. See below for details. I now fixed this wrong statement on Wikipedia, too.)

Of these 25 combinations, only the ones with a block size of 128 bit (16 bytes) and key sizes of 128, 192 and 256 bits (16, 24 and 32 bytes) are standardized as Advanced Encryption Standard. If you are using any of the other variants of Rijndael, you are not implementing AES.

For normal file encryption there is no reason to use any of the other variants, 128-bit key and block sizes are enough (when used with a reasonable mode of operation).

So, how does the key schedule look like?

(For the following, a column is a bundle of 32 bits (= 4 bytes).)

First, from the block size $N_B$ and number of rounds $n_r$ we calculate how much keying material we need for the round keys (it is $N_B · (n_r + 1)$.) The block size is then not needed any more for the key schedule. Calculate this in columns.  For example, in the case of 128-bit blocks and 160-bit keys, you are using 11 rounds, and thus need $4 · (11+1) = 48$ columns of round keys.

We write as many columns as there are in the key size - for example, for our 160-bit key, we would write these as

   k_0    k_1    k_2    k_3    k_4

These are the first five columns of the round keys (i.e. the first round key and one column of the second one). As the next step, we apply the non-linear function $f_1$ of the key schedule on $k_4$, and XOR ($\oplus$) the result with $k_0$ to get $k_5$:

                                     ┏━━━┓
   k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
    │                                ┗━━━┛ │
 ╭──│──────────────────────────────────────╯
 │  ↓
 ╰─→⊕
    │
    ↓
   k_5

I described $f_i$ in an answer to another of your questions.

To generate the following round key columns, we simply calculate $k_n = k_{n-1} \oplus k_{n-5}$ (as the key size is five columns here), until we come to $k_{10}$, where we have to use $k_{10} = f_2(k_9) \oplus k_5$. We repeat this until we get to $k_{47}$ (as we need only 48 columns of round key material), then we can stop.

                                     ┏━━━┓
   k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
    │      │      │      │      |    ┗━━━┛ │
 ╭──│──────│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓   │  ↓    ┏━━━┓
   k_5 ─╯ k_6 ─╯ k_7 ─╯ k_8 ─╯ k_9 ─→┃f_2┃─╮
    │      │      │      │      |    ┗━━━┛ │
 ╭──│──────│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
   k_10 ╯ k_11 ╯ k_12 ╯ k_13 ╯ k_14 ─→┃f_3┃─╮
    │      │      │      │      |     ┗━━━┛ │
 ╭──│──────│──────│──────│──────│───────────╯
 │  ↓      ↓      ↓      ↓      ↓
 ...........................................
 │  ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │
    ↓   │  ↓   │  ↓
   k_45 ╯ k_46 ╯ k_47

So, it is just like the key schedule for an 128-bit key, but with one column more.

When we actually have to use the round keys for the encryption (remember, in this example the block size is 128 bits, i.e. 4 columns), we use $k_0 \dots k_3$ as the zeroth round key (i.e. before the first round), $k_4 \dots k_7$ as the first one, … and $k_{44} \dots k_{47}$ as the last one (after the 11th round).

The key schedule works similarly for other key sizes, but for key sizes larger than six columns (i.e. seven or eight - more is not specified), there is a second nonlinear function $g$ (a simplified version of $f_i$) after the first four columns in each row (see my previous answer for an example with 8 columns, i.e. AES-256).

To extend this idea to larger key sizes than 8 columns (256 bits), one would have to define what would happen with more columns - use a third nonlinear function $h$, use $g$ again, do nothing? This definition was not done by the designers, as 265 bits of key size seem to be enough for the rest of human history.

This whole key schedule can be done on the fly (i.e. while encrypting a block), and this is usually done on memory-limited implementations, who don't want to hold the whole 167 bytes (for AES-128) to 240 bytes (for AES-256) in memory. On "normal" implementations, you'll calculate the key schedule once and reuse it for each block (as you normally encrypt multiple blocks with the same key).

One can even calculate the key schedule backwards (starting with the last some columns, i.e. $k_{43}$ to $k_{47}$ in our example), which would be done for decryption on low-memory devices.


OpenPGP Public-Key algorithm What means when pgpdump shows this kind of algorithm in the Public-Key Encrypted Session Key Packet?

New: Public-Key Encrypted Session Key Packet(tag 1)(126 bytes)
    New version(3)
    Key ID - 0xEC661A345473
    Pub alg - Reserved for Elliptic Curve(pub 18)
        unknown(pub 18)
        -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02

What means m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02?

Which Elliptic-Curve-based operation was made from the sender software?

Pub alg - Reserved for Elliptic Curve(pub 18)
    unknown(pub 18)

The output explains pgpdump knows this is an elliptic curve algorithm (which has ID 18), but does not understand the exact details (which curve was used, ...). Try gpg --list-packets instead which has full support for ECC (requires GnuPG 2.1, binary might also be called gpg2 on Debian and derivatives).

    -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02

These are details of the session key used for the symmetrically encrypted packet that will follow: the symmetric algorithm, a checksum and finally the PKCS-1 encoded session key. From RFC 4880, OpenPGP, 5.1.  Public-Key Encrypted Session Key Packets (Tag 1):

  The value "m" in the above formulas is derived from the session key
     as follows.  First, the session key is prefixed with a one-octet
     algorithm identifier that specifies the symmetric encryption
     algorithm used to encrypt the following Symmetrically Encrypted Data
     Packet.  Then a two-octet checksum is appended, which is equal to the
     sum of the preceding session key octets, not including the algorithm
     identifier, modulo 65536.  This value is then encoded as described in
     PKCS#1 block encoding EME-PKCS1-v1_5 in Section 7.2.1 of [RFC3447] to
     form the "m" value used in the formulas above.  See Section 13.1 of
     this document for notes on OpenPGP's use of PKCS#1.


Is there asymmetric encryption in SSH? I've read in DigitalOcean article about SSH that in order for a server to authenticate a client:

  The server sends the client this encrypted message.
  If the client actually has the associated private key, it will be able to decrypt the message using that key, revealing the original number.

But wasn't it enough for the client to sign the message, why do we need the encryption? Also, given that DSA keys can be used in SSH I'm starting to doubt that the article is correct.

The article is surely wrong.

Nowadays, the sole purpose of client-side private key in SSH is to sign messages (as their algorithms are typically ECDSA EdDSA, etc), the server doesn't encrypt the challenge, it almost certainly verifies it with the public key(s) in the authorized_keys file


Chance in cryptography I was just thinking about my own chance and the way chance can defeat even the most advanced algorithm.

My thought was : you can make a strong session id, but what if by chance, a hacker set this exact match up ?

hypothetical : 454{à"_çé89)hjdsHHKZmdsjYds"#

just try to imagine that someone, by typing a nonsense makes it happen.

You could say, the chances it happens is subminimal. And you may be right.

But what can we do against it ?
Ip lock is impossible since the ip is ever changing for some users. Geographical checks, if possible, will lead to severe performance hits (checks),
dynamic session may or may not add an interesting enough layer of security since you could take another people session id.

So what can crypto propose against chance ?

Thanks,

The probability of someone 'getting lucky' with a guess at a key for a decent cryptosystem is crazily low, but yes: it is possible. However, there are methods that can 'survive' even this.

For example, consider the one time pad.  In this system the key and plaintext are xor'd together to form the ciphertext, and to decrypt you xor the ciphertext and key.
So, what happens if the attacker guesses the correct key? Well, he can xor it with the ciphertext, and will be left with the plaintext. However, what happens if he guesses a different key? This will also leave him with a possible plaintext, which to the best of his knowledge could have been the intended message. Thus even if he guesses the correct key, he won't have any way of knowing that he was right.

This is called information theoretical security: If the ciphertext does not contain any information (in the formal sense) about the plaintext, there is no way that an attacker could possibly know when he has correctly found the key.

eg: Suppose the message $m=11111111$ and the key is $k=10101010$. Then we have the ciphertext $c=m\oplus k = 01010101$.

An attacker intercepts $c$, and starts guessing keys. He guesses two possible keys: $k_1=10101010$ and $k_2=01010101$, leading to him reaching two candidate messages:
$$ \begin{aligned}
   m_1 &= c \oplus k_1 = 01010101 \oplus 10101010 = 11111111
\\ m_2 &= c \oplus k_2 = 01010101 \oplus 01010101 = 00000000
\end{aligned}$$

He has no way of knowing if either of these guesses was correct, even though we (as the original sender) know that in fact he was correct with his guess $k_1$. To him, each possible message $m_i$ is equally likely, so he can conclude nothing. In our example, he has no way of knowing if every bit is set, no bit is set, or indeed something in between.

As an interesting corollary to this, one can (by guessing the wrong OTP key) come up with a possible plaintext that might contain more sensitive data than the original plaintext! For example, if I encrypt $m=\text{I'm just going to buy some milk}$ with key $k$, if the attacker guessed key $k'=k\oplus m \oplus \text{Nuclear launch code=4923...}$ (where 4923... is replaced with the actual launch codes), when they try to decrypt my innocuous message, they would be left with a plaintext telling them the nuclear launch codes. Pretty cool really.


How do the constants in this implementation of AES match up with the algorithm? In this file on GitHub, from lines 154 to 169, there are twelve arrays of constants that I've not seen in other AES implementations. How do they relate to the algorithm?

The tables represent the composition of some of the routines from the round function. These tables are used because they facilitate an efficient implementation. These slides and the "Advanced Implementation" section this blog post do a good job of explaining. The table based implementation was also mentioned in the Rijndael AES proposal as well, if I recall correctly.


Known plaintext attack without knowing the location of the plaintext I'm trying to understand known plaintext attacks and since I best learn by doing I broke out Python and did the following:

I have a plaintext string s and a key k:

s = 'Lorem ipsum dolor sit amet'
k = 'key'

As I'm doing this with xor, this is my xor method:

def xor(s, k):
  return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s, itertools.cycle(k)))

So to get a ciphertext I do this:

c = xor(s, k)

And I can get the plaintext back by doing this, so I know it works:

xor(c, k)

Now for the exercise, let's say I have the ciphertext and know the word "dolor" is in there. How would I attempt to get the key?

My first thought was to do xor(c, 'dolor') but since I don't know where the word is I guess I'll have to try every location?

I found that using the word dolor as the key and starting with a different character kinda seems to work. So I attempt this:

xor(c, 'dolor')
xor(c, 'olord')
xor(c, 'lordo')
xor(c, 'ordol')

etc.

Using the last one (ordol) I spot keyke in the result. Since I know what the key is I know that I found it. But how would I know if I didn't know the key?
Is there also some other way to do this instead of trying every possibility?

As you're aware your crypt/decrypt function works because  A $\bigoplus$  B $\bigoplus$  B = A. So for:

P = plaintext
K = Key
C = ciphertext = (P $\bigoplus$ K)

You can retrieve your plaintext as C $\bigoplus$  K == (P $\bigoplus$  K) $\bigoplus$  K = P.

You also know that C $\bigoplus$  P == (P $\bigoplus$  K) $\bigoplus$  P == K, i.e. you can retrieve the key if you know the plaintext.

Basic stuff, you already knew this.

You've asked "how would I attempt to get the key" if I only know a piece of the plaintext? In that case you cannot retrieve the key directly. However, you can narrow the search space for K considerably.

Consider the case where you know the plaintext less 1 character and, for the sake of simplicity, lets assume lower case alphabet characters only in the plaintext.

In that case, there are two positions that your known plaintext fragment can be in, in the original message, at the beginning or at the end. There are 26 possible plaintext solutions with the plaintext fragment at the beginning and 26 with it at the end, so there are 52 possible plaintext solutions. If you xor all those solutions with your ciphertext, one of the 52 results will be your key.

Knowing that you have "the key" is helped by having lots of ciphertext (like in the case where Mallory has stolen your million-record encrypted database). Identifying the key involves testing the 52 candidates against the million stolen records and seeing which candidate keys create the most plausible plaintexts (e.g. if the original plaintext is known to be English words, finding the key that generates the most of those)

Each fewer character that you know in the plaintext fragment (greatly) increases the search space. In the case where you know a plaintext fragment less two characters then there are three positions that the fragment could occupy and, for each of those positions there are $26^2$ possible combinations (for a total of 2028 combinations).

The search space grows exponentially with the number of characters that you do not know. But the converse is, therefore, true: the search space decreases exponentially with every character that you do know. And that is why an attacker having access to plaintext and ciphertext is scary.

So, no, you cannot directly retrieve the a key knowing a piece of the plain text and, yes, you do need to search the space. However, knowing part of the plaintext, you can greatly narrow a search and combined with other factors (like knowing the structure of the plaintext or encryption algorithm) can make a search that would be intractable either money or time-wise into something that an attacker can afford.

This is just a simple example, more complex ciphers are less straightforward to attack but, the concept is similar; each piece of knowledge (plaintext structure, key structure, algorithm) reduces the search space.


AES-CBC-128 Known plain, IV, Cipher attack Let's say we have a single char 'A' and we encrypted it as much times as we want with a fixed Key and a random IV
So now we have list of the IVs used, the result ciphers and ofc the known text "A"

Is there's any possible solution to get the key used ?

No, there's no possible solution to get the key used, assuming what we are told in the question, and

the key has been chosen randomly;
we find no way to get a clue about it (which could be the case for example if we monitored a device holding the key, or used the obligatory XKCD technique);
we define "possible" as: having odds better than one in a thousand millions (about one in $2^{30}$) for $2^{96}$ keys tested (which I guesstimate represents quite a few years of the effort currently wasted spent on bitcoin mining, based on that source telling these things recently got over $4\cdot10^{18}$ SHA256d hashes per second);
no serious attack on AES-128 (the block cipher) is discovered;
we discount the hypothesis of quantum computers usable for cryptanalysis, which currently are still very hypothetical.

That's because enumerating keys by brute force is quite nearly the best known attack against AES-128 (the block cipher) that recovers the key without attacking the implementation; thus odds of finding the right key after testing $n$ keys are at best $n\,2^{-128}$, regardless of the operating mode used.


Is there an encryption format that preserves length and only outputs alphanumerics? I'm trying to design a promo code system for a server app I'm designing. Basically, I generate a promo code for a certain item and give the code out to someone, who then types it into the server.

Currently, the generator I wrote gives out a 20-character alphanumeric code, but the codes are too easy to manipulate. To fix this issue, I'd like to implement some sort of symmetric encryption (so that the generator app can make the code, but the server can also read it) to keep users from figuring out how codes are generated.

Is there a symmetric encryption algorithm I can use that will return 20 alphanumeric characters?

If possible, I'd like to find an algorithm that can easily be implemented into Java code.

Both of the other answers tackle the question of encryption in a particular format, but I would argue that neither of them is necessarily a good fit for your use case. You want to be able to generate 20 character codes that a server will be able to verify. A symmetric MAC is sufficient for this use case, if you don't need the codes to contain any secret information.

For example, use the format ID||HMAC(key, ID), with ID an arbitrary unique number for each code. You can choose the ID size and then truncate the HMAC to match your length requirements. E.g. 32-bit ID and 168 left bits of HMAC-SHA256. Then encode in the format you want.

IDs can be generated randomly or using a counter or it can include encoded information. The server would store the association between an ID number and whatever the promo code is for etc. An attacker cannot modify a promo code without knowing the MAC key, except by chance with probability $2^{-l}$, where $l$ is the MAC length in bits. You can go as low as $l = 64$ securely. (Perhaps even lower if you make an online guessing attack sufficiently difficult/slow.)


Differences between industrial and military cryptography Industrial and military cryptography should follow the same basic rules, but what does make them different is:

Higher key length, protocols unknown to the civilian world, and perhaps unique methods of transferring media

Are there other fundamental differences that make military encryption safer?

There’s no difference except for marketing. Neither of the terms has a meaningful technical definition on which a substantial share of experts in the field can agree.

Historically there was a difference in permissible key length due to U. S. export restrictions but those stopped a long time ago except for a few countries that are under broader embargo (e. g. North Korea, Iran, Syria).


Bruteforcing a 64-bit key Diffuse the 64 bit key into eight 8 bit blocks. Each block can be brute forced in 2^8 steps. Thus, eight 2^8 steps and in total 2^11 steps are required for brute forcing. Is this kind of brute force possible?

No.
This doesn't work like this.
While, yes you can split a 64-bit key up into 8 8-bit blocks, you cannot confirm your sub-block individually. So you can only confirm the entire 64-bit key at once and only get a "yes" or "no" answer.

From this it follows that the maximal time to cracka 64-bit key is indeed $2^{64}$, where you first try all your guesss for the first byte, then all your guesses for the second byte for all your guesses for the first one and so on...


The security level of double encryption Let PKE $\Pi' = (Gen', Enc', Dec')$ and it is secure in the sense of $S'$.
Let PKE $\Pi'' = (Gen'', Enc'', Dec'')$ and it is secure in the sense of $S''$.
$S'$ and $S''$ may be separation which means that $S' \not\Rightarrow S''$ and $S'' \not\Rightarrow S'$. For example, $S' = \text{IND-CCA}, S'' = \text{NM-CPA}$ or $S' = \text{OW-CCA}, S'' = \text{IND-CPA}$.
Let $\Pi = (Gen, Enc, Dec)$ be the double encryption such that
$Gen(1^\lambda) = (pk, sk)$

$(pk', sk') \gets Gen'(1^\lambda)$ and $(pk'', sk'') \gets Gen''(1^\lambda)$.

$pk = pk' \Vert pk ''$ and $sk = sk' \Vert sk''$.

$Enc_{pk}(m) = c$

$(pk' , pk'') \gets pk$

$c \gets Enc'_{pk'}( Enc''_{pk''}(m)) $.

$Dec_{sk}(c) = m$

$(sk' , sk'') \gets sk$

$c \gets Dec''_{sk''}( Dec'_{sk'}(m))$.

Is $\Pi$ secure both in the sense of $S'$ and $S''$?
In my opinion, it is true.

We define the CPA game of $\Pi$ against an adversary $A = (A_{1}, A_{2})$ as follows:

$(pk, sk) \gets Gen(1^\lambda)$
$(m_{0}, m_{1}, s) \gets A_{1}(pk)$
$b \leftarrow \{\, 0,1 \,\}$ and $c \gets Enc_{pk}(m_{b})$.
$d \gets A_{2}(c, s)$.

We say $A$ wins if $b = d$, and $\Pi$ is IND-CPA secure if $A$ has at most negligible advantage.

For example, if $S'' = \text{IND-CPA}$, assume there exists an adversary $A$ with non-negligible advantage against $\Pi$. Then we construct an adversary $A''$ against $\Pi''$ as follows:
$A''_{1}(pk'') = (m_{0}, m_{1}, s)$:

$(pk', sk') \gets Gen'(1^\lambda)$.

$pk = pk' \Vert pk''$.

$(m_{0}, m_{1}, s) \gets A(pk)$.

$A''_{2}(c, s) = d$:

$c' \leftarrow Enc'_{pk'}(c)$

$d \gets A(c', s)$.

We say that $A''$ wins the CPA game against $\Pi''$ if and only if $A$ would have won the corresponding game against $\Pi$. Thus $\Pi''$ is IND-CPA secure implies that $\Pi$ is IND-CPA secure.
If $S' = \text{IND-CPA}$, assume there exists an adversary $A$ with non-negligible advantage against $\Pi$. Then we construct an adversary $A'$ against $\Pi'$ as follows:
$A'_{1}(pk') = (m_{0}, m_{1}, s)$:

$(pk'', sk'') \gets Gen''(1^\lambda)$.

$pk = pk' \Vert pk''$.

$(m'_{0}, m'_{1}, s) \gets A(pk)$.

$m_{0} \gets Enc''_{pk''}(m'_{0})$ and $m_{1} \gets Enc''_{pk''}(m'_{1})$

$A'_{2}(c, s) = d$:

$d \gets A(c, s)$.

We say that $A'$ wins the CPA game against $\Pi'$ if and only if $A$ would have won the corresponding game against $\Pi$. Thus $\Pi'$ is IND-CPA secure implies
that $\Pi$ is IND-CPA secure.
Am I right? So I conclude that $\Pi$ is a little stronger than $\Pi'$ and $\Pi''$. If it is true, why is there no double public-key encryption scheme?

Am I right?

Yes, with double encryption, if both are functionally correct and at least one is CPA-secure, then the composition is CPA-secure.

  If it is true, why is there no double public-key encryption scheme?

Because you took a scheme that can be reasonably classified to be "unbreakable" and then combined it with an other "unbreakable" one, you have constructed an "unbreakable" one that takes more time to compute than a single "unbreakable" one. There's no practical advantage to such combinators if we're confident in the security of the scheme we're using. If we're not confident either we pick a better one - or if we have also no faith in the better one we do indeed use such combinators. If you want a recent example of this, look no further than the hybrid ECDH / PQ-Crypto key exchanges that are being tested where we don't have faith in the PQ-Crypto yet so use ECDH to secure it against classical adversaries.

  Is $\Pi$ secure both in the sense of $S'$ and $S''$?

To prove this I suggest a simpler approach of checking whether $\pi\circ\operatorname{Enc}\circ\pi'$ is $S'$-secure assuming $\operatorname{Enc}$ is $S'$-secure (coming up with the correct decryption is left as an exercise to the reader) and $\pi,\pi'$ are any permuations applied to the input and the output.


Is this a secure keyed hashing construction? I need a PRF for use with PBKDF2, however, the only thing I have is the AES block cipher primitive. I'm attempting to derive a keyed hash function from the block cipher. The design is based on the Merkle–Damgård construction. The inputs are $i$ and $k$, for the input data and key, both are a list a bytes. The byte 0xff is appended to $i$, and then subsequent 0x00 bytes are appended until $length(i) \mod 16 = 0$. $i$ is then split into $length(i)/16$ blocks in the array $b$. And then the algorithm continues as follows.
$$s_{-1} = k$$
$$s_x = E_{s_{x-1}}(b_x)$$
$$h = s_0 \oplus s_1 \oplus s_2 ...  \oplus s_{length(b)-1}$$
$h$ is then returned as the resulting hash. Is this secure enough to use with PBKDF2?

If you want to construct a PRF for arbitrarily-long inputs using AES, then just use CBC-MAC (while prepending the message length in the first block). I don't see any advantage in what you are proposing and therefore don't see any point in trying to analyze something non-standard.


What does $k^{-1}$ mean?

In the question's formula $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ , the term $k^{-1}$ is a (or the) multiplicative inverse of $k$ modulo $p$. By definition, that is an integer $i$ such that $(i\cdot k)\equiv1\pmod p$ , that is an integer $i$ such that $p$ divides $(i\cdot k)-1$ (or if we want the multiplicative inverse, additionally $i$ must be such that $0<i<p$ ). Which  multiplicative inverse we take does not change the result $S$ .

$k^{-1}$ can be computed using the (half-)extended Euclidean algorithm (see this ); or other methods. Whatever was used, the question has $S$ matching $k$, $\mathrm{hash}$, $d_A$, $R$ and $p$ , and the equation given. But see below why $S$ is wrong.

  Its length seems to be only half of a valid signature

Indeed. That's because the signature is $(R,S)$ per some convention; like concatenation of fixed-length octet strings representing $R$ and $S$ per big-endian convention, perhaps with some prefix.

  Comment on the equation

Oh, I had missed that initially: the question's equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod p$ is wrong! There is confusion between the order $p$ of the field (used for coordinates on the elliptic curve secp256k1), and the order $n$ of the point $G$ on the elliptic curve (which for secp256k1 is also the number of points on the elliptic curve, including the point at infinity). The correct equation is $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ . For secp256k1, $n$ is 115792089237316195423570985008687907852837564279074904382605163141518161494337 . That changes $S$ , of course.

  If the equation only gives us $R$, how can we get $S$ ?

We obtain $S$ using the equation $S=k^{-1}(\mathrm{hash}+d_A\cdot R)\bmod n$ starting from $k$, $\mathrm{hash}$, $d_A$, $R$ and $n$ .

We must previously have obtained $R$ by computing $k\times G$ . That's by point multiplication on the elliptic curve secp256k1, using arithmetic modulo $p$ (this is not a typo), keeping the $X$ coordinate, and deducing $R$ . The normative way is to compute $R=X\bmod n$ (after having reduced $X$ modulo $p$ so that $0\le X<p$ ), and redoing from start with another $k$ when $R=0$ . However in practice, if we do no get $0<X<n$ , then the process by which $k$ was chosen and $X$ computed is almost certainly broken, and in all other cases $R=X$ .

Update: I confirm that the question's $R$ matches the question's $k$ . Thus all that remains to do is compute $S$ using the appropriate modulus, and format $(R,S)$ into the signature.


Encrypt a big file in blocks with AES-GCM: how many nonce do we need? I need to encrypt big files using AES-GCM, potentially 10 GB or more. For memory (RAM) reasons, I need to processs them by blocks (let's say 16 MB), rather than doing encrypt(plaintext) in one pass.
By reading the answers of this security.SE question:
Should I chunk or not for AES-GCM file encryption, I have the feeling that I read all and its opposite.
Which one is the correct approach?

Method A: Since "a counter mode converts a block cipher into a stream cipher" (quote from the linked post above), we can do this:
nonce = Random.new().read(16)
out.write(nonce)
cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
while True:
    block = f.read(16*1024*1024)
    if not block:  # EOF
        break
    out.write(cipher.encrypt(block))  # we encrypt multiple blocks with the same
                                      # "cipher" object, especially the same nonce
out.write(cipher.digest())  # we compute the auth. tag only once at the end

Here we encrypt multiple 16MB blocks with the same "cipher" object, same nonce.
I read some criticisms about this approach in the article AEADs: getting better at symmetric cryptography, paragraph "AEADs with large plaintexts".
But on the other hand, I noticed that:
print(cipher.encrypt(b'hello'))  # 4cadd813be in hexadecimal
print(cipher.encrypt(b'hello'))  # d3585e3471, different, fortunately!

so it seems ok (like a stream cipher).
Is it true that GCM (counter mode) converts a block cipher into a stream cipher?

Method B: we have to choose a new nonce and tag for each 16 MB:
while True:
    block = f.read(16*1024*1024)
    if not block:  # EOF
        break
    nonce = Random.new().read(16)
    cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
    out.write(nonce)
    out.write(cipher.encrypt(block))  # new "cipher" object, new nonce for each 16 MB block
    out.write(cipher.digest())  # we compute the auth. tag only once at the end

Drawback with this method: we have to save to disk nonce, tag metadata for each block.
This looks like the method detailed in Proper way of encrypting large files with AES-256-GCM. Obviously a malicious user could swap the order of blocks (including their nonce and tag) and the file would look ok, whereas it's not. So this solution seems not ok, as suggested by this answer.

TL;DR: Isn't it a problem that we use only one nonce in Method A above?
Note: I also read this method which chains and blocks (and tags).
Is there a general consensus/normalization for a good way to work with big files by blocks with AES-GCM?
(For implementations with Python, such as pycryptodome, I'll ask later on SO, but first, I wanted to read about the background).

AES-GCM can encrypt up to $2^{39}-256$ bits with a single key+nonce pair. That's just under 64GiB. A 10GiB file is fine.
If you'd go beyond 64GiB you'll lose security. In that case, either use XChaCha20-Poly1305 (max of 256GiB plaintext per message) or divide the file into chunks < 64GiB.
16MB is far smaller than needed, and will hurt performance.
Most implementations of AES-GCM (Or XChaCha20-Poly1305) will provide some sort of streaming interface, with init, update, and finalize functions, where init starts the computation, update takes in some data and can be called repeatedly, and finalize finishes it. Libsodium's crypto_secretstream_* (documentation here) is a good example, but any library offering a streaming implementation should have something similar.


What does the strict avalanche criterion mean? I can build black box ciphers with the following properties:

Satisfies SAC, but is trivially weak (a keystream from an LFSR seeded with the key).
Does not satisfy SAC, but built from secure primitives (Base64 encode the output of AES).

From 1 you can see that SAC is not sufficient for security. From 2 you can see that SAC is not necessary for security.

Since neither $SAC \implies Security$ and $Security \implies SAC$, what conclusions can you make based on SAC?

As pointed out in the comment, SAC is just one criterion relevant to diffusion, useful in ciphers as well as hash functions but by no means enough to provide security under any reasonable definition.

Just a partial list of desiderata for Sbox function design, optimal nonlinearity, high degree, low differential probabilities, high degree as a univariate polynomial, algebraic immunity, correlation immunity, etc should be enough to convince one of this.


Shortest Path for Certificate Network I was reading an example from my textbook about verifying a certificate from a client using a certificate network. The example in the book is as follows:

  A issues a certificate to B.
      A issues a certificate to C.
      A issues a certificate to D.
      B issues a certificate to D.
      C issues a certificate to A.
      C issues a certificate to Alice.
      B issues a certificate to Bob.

  Bob wants to verify Alice's key. What is the path in the certificate network to do so?

I've drawn out the diagram but I don't see anyway such a verification possible as Bob's certificate provider is B, which has a one directional relationship with A, such that A "trusts" B, but not the other way around. Is there even a path that would solve the problem?

Quoting SEJPM's (now removed) comments:

For the convenience of any answerer, I've rendered the graph and answerers may use it (and any derivatives) at their will. If required I can also provide vector graphic versions of it.

In this case one could argue that A issued both bob's and alice's cert indirectly and thus either party seems to trust A to certify CAs and thus they trust each other's cert. (But this doesn't really sound convincing to me -> no answer)

Thanks to @SEJPM for adding the graph. With what you stated you were give, it would not be possible for Bob to verify Alice's certificate.


A Simple Provably Secure Key Exchange Scheme Based on the LWE In this paper (A simple provably secure key exchange by Ding et al.), I am trying to understand the correctness (which is given on page number 8) of the key exchange technique based on LWE.

To understand the correctness of the scheme, there is a very important lemma (on page number 6). The lemma is as follows:

  Lemma 2. Let $q>8$ be an odd integer, the function $E$ defined above is a robust extractor with respect to $S$ with error tolerance $\frac{q}{4}-2$.

I'm confused by the proof of Lemma 2:

How does the author derive the condition that Lemma 2 is true for $q\gt 8$?
How does $|y+ \sigma$ $\frac{(q-1)}{2} \mod q| \le \frac{q}{4}+1$?
At the end of the proof of Lemma 2, the author writes that

  Our robust extractor enjoys a very nice property which says that for uniformly random $x\in$$
 \mathbb{Z} _q$, $E(x, \sigma$) is uniform in $\{0,1\}$ even conditioned on $\sigma$, where $\sigma \leftarrow S(x)$.

This property becomes Lemma 3 of this paper.

Can anyone  answer the above three questions and thus the proof of Lemma 2 and Lemma 3? Thanks!

Lemma 3 in this paper gives a better explanation regarding to your question 1 and 2.

For a simple answer for question 3, because we have equally divided region, this gives us even change on $k_i$ and $k_j$ be even or odd number, thus the output of function $E$ is uniform random.


Lookup table for DSA/ECDSA/Schnorr multiplication Something in common to [EC]DSA and related signature schemes like Schnorr is that the most expensive part of signing is calculating $r = g^k$ in the group for some per-signature $k$ of length $b$ bits.  But this is always taking the same generator to a power.

Because it's always the same base, we could precompute $\{g^1, g^2, g^4, ... g^{2^{b-1}}\}$ into a table.  Then calculating $g^k$ is multiplying by the entries in the table corresponding to the $1$ bits of $k$.  (Always do the multiply, but discard the result, for $0$ bits to stop timing and power attacks.)

This seems like it would save time, because instead of doing $b$ squares and $b$ multiplies, you'd only do $b$ multiplies.

This is most useful for signing.  For verifying, you'd need a second precomputed table for the squares of the public key $y$.  This could be stored as part of the public key, though, if the key length isn't a problem.

Existing implementations don't seem to do this optimization.  Why not?  (Or maybe I'm wrong and they do...?)

Actually, doing $k-1$ multiplications isn't all that much less than what can be achieved using a more sophisticated power algorithm (say, base $2^w$, for an appropriately chosen $w$) - and these algorithms don't need a precomputed table.

On the other hand, there are more sophisticated precomputational algorithms out there, which drastically reduce the number of multiplications (and sometimes also shrink the size of the table as well).

Now, I haven't seen this sort of optimization when dealing with finite field groups ($\mathbb{Z}_p^*$); in my experience, general power routines (or possibly optimizing for the case of $g=2$) appears to be the norm.

However, it is quite common when dealing with Elliptic Curve groups.

As for my speculations for why this is:

The $\mathbb{Z}_p^*$ routines tend to be older; perhaps no one considered it worth the bother to updating them to use precomputed tables.
The tables for $\mathbb{Z}_p^*$ would be larger (because each precomputed element would be larger).
With ECC, you can efficiently compute inverses - we can take advantage of this to improve our precomputation algorithms somewhat, making the precomputational advantage somewhat larger.


Convert affine to projective coordinates and vice versa in ECC? I am working on a small project. An elliptic curve equation with y^2=x^3-3x+27 mod 43, a point $Q=(1,38)$, using point doubling method https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_doubling, i got $2Q(Q+Q)=(41,5)$. Now in projective coordinate $Q=(1,38,1)$ taking $z=1$.https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Standard_Projective_Coordinates

Calculating $2Q$, I get $2Q=(22,31,39)$ and converting to affine coordinate I can't get $2Q=(41,5)$.

So, where did I went wrong can anyone explain or am I following the wrong method??

Somewhere you seem to have made a small mistake. $39$ is already the inverse of $Z_{2Q}$. The correct value of $Z_{2Q}$ is $\mathbf{32}$.

For the long story, let us first go through the doubling formula one step a time:

if (Y == 0)                     # nope
 return POINT_AT_INFINITY
W = a*Z^2 + 3*X^2               # W = 0
S = Y*Z                         # S = 38
B = X*Y*S                       # B = 25
H = W^2 - 8*B                   # H = 15
X' = 2*H*S                      # X'= 22
Y' = W*(4*B - H) - 8*Y^2*S^2    # Y'= 31
Z' = 8*S^3                      # Z'= 32
return (X', Y', Z')

This leaves us with $2Q = (22 : 31 : \mathbf{32})$.

To compute the affine representation, we compute $Z_{2Q}^{-1} = 39$. Now the affine representation of $2Q = (XZ^{-1}, YZ^{-1}) = (22 \cdot 39, 31 \cdot 39) = (41, 5)$.