Construct block cipher from a smaller one with mixing function I read about the AEZ encryption scheme as presented at the CAESAR competition. To me it seems like a construction of an arbitrary length block cipher from a smaller one. The key component is the mixing function. (See the figure… Left: without cipher text stealing, Right: with cipher text stealing.)

Image source: http://www.cs.ucdavis.edu/~rogaway/aez/aez.pdf

In my opinion the properties of a mixing function would be:

keyable with good avalanche effect
no need to be cryptographically secure
arbitrary length
reversible
fast (at least faster than encryption cipher)

AEZ uses reduced round AES as the core of its mixing function. Overall operation time is about 1.8 AES (as mentioned in the document). This algorithm will be bound to the AES cipher.

I wonder, is there an alternative mix function with these properties floating around?

I read about the AEZ encryption scheme as presented at the CAESAR competition. To me it seems like a construction of an arbitrary length block cipher from a smaller one.

The construction is only used in the v1.x of AEZ, because it requires appriximately 1.8 AES calls per block of plaintext, while the one used in v2.0 requires only 1 AES per block asymptotically. It is originally due to Naor and Reingold.

It is more like a block cipher mode than a way to construct a larger block size cipher from a smaller one. Specifically, it does not improve the birthday bound which limits the number of blocks encrypted to less than the square root of block size (i.e. $2^{64}$ for AES).

  In my opinion the properties of a mixing function would be:

The requirements for the mixing function are given in the paper above. It is enough that the functions MIX and MIXI are pairwise independent permutations, but that is not a strict requirement. Instead it is enough that they are $\epsilon$-AXU2: $\forall x \not = y, z \in \{0,1\}^n: P[f(x) \oplus f(y) = z] \le \epsilon$.

The paper NR mode of operation (ps) refers to several types of functions that fit the bill if you are interested in using something else.


Is ElGamal still unforgeable if the adversary knows r? Is ElGamal still unforgeable if the adversary knows the value of $r$ that was calculated by $g^k$?

When we do sign the message $msg$, we calculate $r = g^k$.

As we know, the regular ElGamal is existentially forgeable:

$e$ is picked randomly from $\mathbb{Z}_{p-1}$
$r = g^e \cdot y$ mod $p$ and $s$ is $-r$ mod $p$
When we check if it was forged we check for $y^r \cdot r^s = g^m$. Thus $g^{xr} \cdot (g^{e} y)^ {-r} = g^{-er} = g^{es} = g^m$. Where $m = H(msg)$.

if now $m = H(msg) + r$ (concatenate $r$ to $H(msg)$ is it now unforgable ?

It seems that you mix things up.

ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function.

Given the type of forgery in your question that works, you compute your $m$ as $m=es \bmod p-1$ and have no full control over the choice of $m$. Note that you would have to find $M$ such that $m=H(M)$ for your forgery to be valid, which means that you need a preimage $M$ of $m$ under $H$ which is not feasible if $H$ is secure. This is because the verification algorithm will get $M$ and signature $(r,s)$ and will check if $$y^r r^s\equiv g^{H(M)} \pmod p $$ holds.

You could modify the computation to $m=H(M)\|r$ and to adapt the verification algorithm to check if $y^r r^s\equiv g^{H(M)\|r} \pmod p $, but I do not see any immediate reason why you should do so. AFAIK hashing the message prevents any existential forgeries of ElGamal signatures as long as $H$ is secure.


Is GMW different from Secret Sharing? Is GMW (How to play ANY mental game) protocol different from Secret Sharing??
If so, how is it different from Secret sharing?

They are very different. GMW is a multi-party computation protocol while secret sharing is a technique to distribute a secret. GMW uses secret sharing as a building block but it also uses other primitives like an oblivious transfer (OT). GMW deals with the problem that multiple parties jointly compute a function (over their inputs) securely without revealing anything else except the final output value of the function. Note that a simple difference is that GMW does not have a particular secret distributor (well actually every party distributes secrets), as opposed to secret sharing.


Discrete Logarithm (512 bits numbers) - Find exponent parameter I'm trying to resolve a discrete logarithm equation:

$$y = g^x \bmod p$$

Every parameter is a 512-bit number. I know the values for $g$, $y$ and $p$ and I need to find the $x$ value. Finally, I know that $g$ is a primitive root of $p$.

I tried to look at some related topics about the discrete logarithm, but I can't figure out how to implement an effective algorithm  to solve this problem.

Here you can find the value for each parameter: http://pastebin.com/JKvedKNd

I have started to look at how some algorithm works, but I would like to know depending on these value parameters which could be the more efficient.

It is 80 bits from the actual record I think: https://en.wikipedia.org/wiki/Discrete_logarithm_records.
So there is something I am missing due to my lack of skills in the mathematics area.


Chosen Plaintext Attack and Chosen Multiple-Plaintext Attack The original CPA game:

The adversary gives two arbitrary messages $m_0$ and $m_1$ to a challenger;
The challenger encrypts an arbitrary message $m_u$, $u∈\{0,1\}$ , and sends the ciphertext to the adversary;
The adversary outputs the guess $u$.

Now I give a revised version of the above CPA game:

The adversary gives two arbitrary sets of messages $M_0$ and $M_1$ to a challenger, where $|M_0|=|M_1|$, and each pair of counterparts are of equal size;
The challenger encrypts an arbitrary set of message $M_u$, $u∈\{0,1\}$, and sends the ciphertexts to the adversary;
The adversary outputs the guess $u$.

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?

Yes, because this is essentially a trimmed down version of Left-or-Right-CPA security (PDF) which is provably equivalent to the first definition you mentioned which is also known as Find-Then-Guess-CPA security.

If your scheme is LoR-CPA secure then you can query all message pairs from the two sets to the LoR oracle and answer any remaining queries $x$ by querying $(x,x)$.

The inverse direction (that the new definition implies LoR) probably requires a Hybrid Argument as indicated in the comments to "extend" the size of the set to all queries. This should go analogous to proving that FtG-CPA security implies LoR-CPA security.


How does the I2OSP primitive in RSA work? I'm trying to figure out how to convert a message to a message representative (non-negative integer) in RSA. I think I understand how the OS2IP primitive (converting from message to integer). It involves finding the sum of all the integer representations of each byte multiplied by 256 to the power of the length of the message minus the index for the byte. However, I don't understand how the opposite process works. PKCS#1 says to write the message representative x in its    xLen-digit unique representation in base 256. I'm not very good with the actual mathematical processes here, so I'm not sure how the integer is supposed to be separated into the separate bytes multiplied by powers of 256.

Basically I2OSP is nothing more than a fixed size big endian representation of the integer, using a given number of bytes (or octets, same thing). The way that this is described in PKCS#1 is very technical, but this is what it comes down to. Big endian (or network order, same thing) numbers need to be left padded with zero bytes in case they are too small.

For RSA, the length given to I2OSP is nothing more than the modulus size in bytes. Usually this is just the modulus divided by 8 as most RSA key sizes can are multiples of 8. The standard however does define that the minimum number of bytes required for the unsigned representation of the number is to be used.

Obviously I2OSP would have to report an error if the integer doesn't fit. However, given that RSA calculations are performed modulus $n$, this can never happen.

Usually runtimes already have methods to encode a number (usually called a bignum or BigInteger or something similar) into big endian encoding. If only little endian is available you'll have to reverse the bytes in the array yourself before proceding.

After you're retrieved the big endian encoding you simply have to left-pad with zero's, and that's it.

You may have to strip a single zero byte from the output in case you only have a signed encoding available within your runtime.

What you do not want to do is perform the mathematical calculations yourself. What is described is nothing more than a binary representation of the number, and this binary representation is already present in one form or other in the memory of your runtime.


Is encryption time greater than decryption time? Is encryption time always greater than decryption time for all encryption techniques (AES / DES / RSA / DSA), or is there a mistake somewhere in my implementation?

It depends.  Specifically, it depends on the type of cipher, and on the way it's used.

For stream ciphers like RC4, and for block ciphers like AES in CTR and OFB modes, decryption is effectively identical to encryption, and thus takes the exact same time.  (Minor exception: encryption may require generating a unique nonce / IV, which might take a small amount of extra time.)

For block ciphers in CFB mode, encryption must be done sequentially (since each cipher block depends on the previous one), but decryption can be parallelized.  Thus, on a multi-core implementation, CFB decryption is typically faster than encryption.

The same is also true for CBC mode, but there's an additional quirk: CBC mode decryption requires using the block cipher in inverse ("decryption") mode (CTR, OFB and CFB all use the block cipher only in forward direction, even for decryption).  For some block ciphers (notably including many implementations of AES), using the cipher in the inverse direction may be somewhat slower than the forward direction e.g. due to asymmetries in the key schedule.  Thus, on systems that support parallel decryption, CBC decryption is typically faster than encryption, but on systems that don't, it may be slightly slower.

Finally, for block ciphers in ECB mode (which is insecure for most purposes, and so should not be used), the only difference between encryption and decryption is the direction the block cipher is used in.  Thus, as noted above, decryption may be slightly slower than encryption (although, of course, you could always decide to swap the directions if you want).

Of course, in modern cryptography, you really should be using an authenticated encryption mode.  Many of these (like GCM, EAX, CCM, etc.) are essentially based on a combination of CTR mode and a MAC; since CTR decryption is identical to CTR encryption, and since the MAC is computed the same way in either case, the total time for encryption and decryption should be approximately the same.

That said, there are, again, some exceptions.  For example, for SIV mode encryption, the MAC must be computed (to generate the synthetic IV) before encryption can begin, whereas for SIV decryption, the MAC can be computed (mostly) in parallel.  Thus, for SIV mode, encryption may be up to twice as slow as decryption.  (Of course, this is by wall clock time; the CPU time consumed should still be approximately the same for both directions.)

Finally, for asymmetric encryption (RSA, (EC)IES, etc.), the difference could really go either way.

For RSA specifically, decryption is typically slower than encryption; that's because both RSA encryption and decryption involve modular exponentiation, but whereas the public encryption exponent is normally small and fixed (usually either 3 or 216+1 = 65,537), the secret decryption exponent is usually almost as long as the modulus.  Thus, doubling the modulus size makes encryption take twice as long, but makes decryption take four times as long.  Using the Chinese Remainder Theorem does speed up RSA decryption, but only by a factor of about four (as it effectively halves the size of the numbers one needs to work with) at most.

Conversely, for ECIES, encryption requires generating a random number and computing two scalar multiplications, and is thus generally slower than decryption, which only requires a single scalar multiplication.

In any case, asymmetric encryption of large messages is typically done using hybrid encryption, where the message is first encrypted using a symmetric cipher, using a random key, and the random key is then encrypted asymmetrically.  Thus, for large enough messages, most of the time will be spent on symmetric encryption anyway.


Does HMAC provide anything that AEAD does not? Alice and Bob have to talk through Eve. (server to device through untrusted third party that relays messages, no TLS available)

Assume a secure key. Out of scope. Example, ECDH key exchange with HKDF.

Each payload has associated data. Time, version, type, etc. Data that is used to get a message to the correct function in Alice or Bob. The transport protocols have none of this in their designs.

Message authentication is important, so HMAC. Message payload encryption is sometimes important so at least occasionally AES-GCM128 on payload. Most of the time the payload data is not confidential. AES-GCM128 AEAD could cover both use cases.

Constrained device. Overhead for nonce, keyid, time, time are noticeable. Compiled size for both algorithms also a factor.

If I need to support AEAD sometimes, is it reasonable to just use AEAD all the time and skip HMAC entirely?
HMAC should be faster, but how much? I’ll need to test this, but suspect the difference might not be huge.
Is there an advantage to HMAC other than speed and being able to debug data that remains in clear text? Only other thing I know is smaller unpadded payload data.
Slightly aside, but does HMAC or AEAD benefit from including their nonces in the hashed / additional data? My replay attack prevention will mostly revolve around server time delivered to device on connection included in each message.

If I need to support AEAD sometimes, is it reasonable to just use AEAD all the time and skip HMAC entirely?

Yes, and if you only  need integrity / authenticity of the message then you can put all of the message in the Associated Data.

  HMAC should be faster, but how much? I’ll need to test this, but suspect the difference might not be huge.

It won't be faster than GMAC generally, but if you include the CTR mode encryption  then you may see a difference. This is too dependent on the system config to be able to answer this reasonably.

Some settings or openssl speed may help you with this. In my case AES-GCM was even faster than HMAC-MD5 which is normally quite fast - although the MD5 speed in OpenSSL isn't that great (but it's the only supported version of HMAC for the speed command, unfortunately). And SHA-256 may also have hardware acceleration. This is a muddy field...

  Is there an advantage to HMAC other than speed and being able to debug data that remains in clear text? Only other thing I know is smaller unpadded payload data.

HMAC is a very sturdy algorithm that doesn't suddenly fail. AES-GCM may fail catastrophically if the authentication tag is too small or if the IV is repeated. I'd say that HMAC is less brittle than AES-GCM: the latter is secure, but it doesn't bend - it breaks.

  Slightly aside, but does HMAC or AEAD benefit from including their nonces in the hashed / additional data? My replay attack prevention will mostly revolve around server time delivered to device on connection included in each message.

No. HMAC doesn't contain a nonce (although you may need a message specific nonce to avoid replay attacks). AES-GCM always includes the nonce automatically during the verification of the authentication tag, so adding it separately is useless.


Static ciphertext length for any plaintext length less or equal than x? I am encrypting buffers using AES-256-CTR encryption. My encryption is working but I have a requirement that I want to make sure I implement correctly. The requirement is as follows:

Given any plaintext of length less that x, the ciphertext should always be of length x.

In my example

x is 1 KB but can be anything while consistent.
The plaintext could range between 1 byte to 1 KB, never larger.
The length of the plaintext is not know by decryptor.

If you can give up two bytes (so the longest message is 1022 bytes long), then this can be straightforward.

Create a 1024-byte buffer. Make the first two bytes the length of the message. Then add the message. Then pad the rest of the buffer with random data. Random data is best here because it leaks less information than zeros, but you could use zeros.

Encrypt the entire buffer. When you decrypt the result, pull the first two bytes and use that to extract the right number of bytes.

This of course will work for any length; so if you need a full 1024-byte message, you can just make the ciphertext always be 1026 bytes.


Is a second preimage attack on MD5 feasible? What's the practical status of MD5 w.r.t. second-preimage?

Integrity of a piece of data is protected by an MD5 hash, itself assumed genuine. The data (and thus the hash) is known to the adversary. The adversary can change the data, and wants to do that while leaving the hash identical. Denote the data size as $K$, in 512-bit block increment, and assume that could be sizable (e.g. $K\approx2^{35}$, which is less than one big hard disk). The original data could follow some pattern (e.g. repeated 512-bit blocks). To some degree, the adversary could even choose some data in the original (e.g. embedded in some innocent-looking file); but we must assume that the adversary can't predict some of the data before what it injects, else the now classic collision attacks against MD5 apply.

A generic second-preimage attack is applicable to Merkle–Damgård hashes, with cost $2^{129-k}+2^{65}$ hash rounds for MD5, where $k=\log_2K$, but that's not exactly cheap (it is attributed to R. D. Dean in his 1999 thesis sect. 5.3.1, and also exposed by J. Kelsey and B. Schneier in their 2005 paper).

Has anything more practical surfaced?

As far as I am aware, there are no practical known second pre-image attacks on MD5, under the conditions you listed.

However: if the attacker can control any part of the original, I would worry about using MD5 in this setting.  Its security in this setting may be fragile and there may well be cleverer attacks than anything currently in the literature.  I wouldn't be shocked to discover that second pre-image attacks are possible if the attacker has control over part of the original, even if we assume that the original starts with some unpredictable stuff before the part that the adversary can control.

So using MD5 in this way in new systems would not be prudent.  (I don't think I'm telling you anything you don't already know...)


Insecurity in Needham and Schroeder protocol? I've been studying specifically the authentication algorithm Needham and Shroeder, and understand the idea in general of the message exchange. But, researching on the subject, I found a question that I do not know the correct answer to, and I would like to get some feedback from someone with more experience on the subject.

At one point in the algorithm agent A asks B to send an N encrypted with the session key in the form of challenge.

Example :

A - > B [ Nb ] Kab

Kab : session key,
Nb : a number sent by B,

Says the question that this step is not safe , and asks to explain why.
The only problem I see is the message of this session key, Kab, be violated . Anyone can access the session key, or there is some flaw in this step?

Because only if A and B have the key, Kab, this message can only be decrypted by these two agents.

Another problem may be the message playback, somebody third agent captures the [ Nb ] Kab and sends later getting the opinion that knows Kab, this can also be a problem? The latter case can be solved with a timestamp .

Maybe this question relate to public-key version of protocol.
In this case, adversary could start two synchronous exchanges with Alice and Bob, and use Alice responses to convince Bob, that he communicating with Alice. More information


Spritz cipher sponge function capacity Rivest and Shuldt proposed a new sponge like cipher algorithm called Spritz:

http://people.csail.mit.edu/rivest/pubs/RS14.pdf

In this paper they say that the strength of the cipher is related to the bit-capacity of its sponge-like internal function. They calculate this as 936 bits from 5 8-bit registers and 112 bytes of an internal state space. That gives (112+5)*8 = 936 bits.

However the 112 bytes of the internal state space are all different, thus they represent one of (256!)/((256-112)!) permutations. This number of permutations can be represented in 855 bits which with the 5 registers makes for 895 bits which is 81 bits less than claimed.

My question is, is the effective strength of the sponge function 936 bits as stated by Rivest and Shuldt, or, given it can be entirely represented in only 895 bits, "just" 895?

The relationship between Spritz's security and the capacity of the internal function, Shuffle, is based on the fact that any generic attack must use on the order of $2^{c/2}$ queries to Shuffle in order to have a non-negligible success probability, where $c$ is Shuffle's capacity. A generic attack does not use any details about Shuffle, meaning the attack holds if you replace Shuffle with any other function. This does not say anything about attacks against Spritz in general, and if you're able to find a special property about Shuffle which is useful for an attack, such as a more efficient description of Shuffle, then you can beat the $2^{c/2}$ minimum requirement on the amount of Shuffle queries for a successful attack.

So the fact that Shuffle can be described more compactly will not change Rivest and Schuldt's security claim since their claim only depends on Shuffle's explicit capacity. In fact, Spritz's effective security could be significantly worse than what they claim, but you'll have to find an attack against Spritz to show this.


RC4 : Keystream reconstruction? First up: it's a step in some challenge found on the Internet, where we get an application and a file. The application must be feed with that file and a password (the password is the flag for the challenge).

So, after reversing the application, I found that the algorithm used is RC4 with a small change in the "S" array, which was not initialized to the identity but initialized to $S[i]= 0xFF -i$ .

The information I get from the challenge is that the file once decrypted has the INTEL HEX FORMAT which has a quiet regular format (like the : at each line).

At this point, I get some information about the keystream (i.e a partial keystream).
My question is there some relation between the element of the keystream, and is it possible to reconstruct the total keystream from my partial keystream?

All what I found on the RC4 was for attacking WEP, based on the fact that it use the same (IV+key) to encrypt multiple packets, and I don't think it's possible to use this in my case.

If what the program does is "take your password, use that as-is as the key to a (modified) RC4 encryption algorithm, and use that keystream to decrypt the entire file", well, there is no obvious weakness to take advantage of.  Partial information doesn't help you much (for that matter, they could have given you the entire decrypted file, and it wouldn't help you to recover the key -- RC4 is pretty good at hiding that information).  As for the S[i] = 0xFF - i modification, well, there's no obvious weakness that causes.  At worse, that would change how certain related key attacks would work; since related key attacks do not appear to be relevant here, that is unimportant.

So, you can obviously do brute-force on the password, but unless the password is only a couple of characters long (or they give more clues about it), that's not likely to yield a result.

Hence, the obvious question is "is that a true representation of the challenge"?  Or, do they (say) reset the RC4 algorithm periodically (rerunning the Key Setup Algorithm from the original key)?  Do they stir in something when they reset the algorithm?

BTW: as for WEP, they don't use the same IV+Key to encrypt multiple packets.  Instead, they use different IVs (and the same key), and just concatinate they two when forming the key they give to RC4.  Because the RC4 Key Setup Algorithm doesn't do a great job of hiding information and so leaves some correlations between the original key and the initial parts of the key stream.  These correlations aren't enough to take advantage of if you're given one key stream (or even a few hundred), but given enough, it allows us to deduce the original key.


Linear Feedback Shift Registers analysis Cryptanalysis of Linear Feedback Shift Registers. From this site I found that lfsr could be break by Berlekamp-Massey algorithm. What is the specific progress of this algorithm? And if there is any other way to do it

First of all, LFSR's are not secure when they are used alone. They have good statistical properties and one can calculate their period given the feedback polynomial. The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. In this case, it visit all states except the all-zero state if it started with a non-zero sate.

To find the taps and internal of an LFSR, you can go in two ways;

Give variable names for the internal and tap point then you can generate a linear equation of the system then solve it with Gaussian elimination.
Use the Berlekamp-Massey algorithm, this is faster than Gaussian elimination and only requires the double of the LFSR's size. i.e. an LFSR with length $L$ can be constructed with $2L$ sequential output regardless of the number of the taps. It is an interactive algorithm that updates the taps according to a currently given output bit.

Actually, Berlakamp-Massey algorithm produces the shortest LFSR with taps that produce the given sequence. The algorithm may reach the result before consuming all $2L$ bits, however, an attacker needs to use all $2L$ bits to be sure. If the determining polynomial of the LFSR is no primitive, then there can be more than one LFSR that produces the sequence with different lengths. Berlakamp-Massey algorithm, however, always will find out the shortest LFSR.

The LFSR based archaic stream ciphers are;

Combining LFSRs with non-linear combiner broken by the novel attack of Siegenthaler
Irregular clocking as Alternating step generator
Shrinking Generator is broken if the taps are known; Gil et. al,  2009 New Attack Strategy for the Shrinking Generator
if not known then the attacks are not better than brute-force.
Filtering the LFSR
Self Shrinking Generator (SSG). Attack on SSG;

2001 Zenner et. al; Improved Cryptanalysis of the Self-Shrinking Generator require less than 70% of the brute-force, for example for 120-bit the attack requires $\mathcal{O}(2^{83})$-time.
2011  Amparo and Sabater; Cryptanalytic Attack on the Self-Shrinking Sequence Generator requires $\mathcal{O}(2^{L/2})$ for time complexity, $\mathcal{O}(2^{L/4})$ for the amount of intercepted sequence and $\mathcal{O}(L^2)$. Note This work may not be correct, see comments
2006 Zhang and Fang; New Guess-and-Determine Attack on the Self-Shrinking Generator. Depending on the $L$ the length of the LFSR their attacks has;

$L \geq 100$ then $\mathcal{O}(2^{0.556L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.161L})$-bit keystream
$L < 100$ then $\mathcal{O}(2^{0.571L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.184L})$-bit keystream

And all the above is broken, at least, theoretically.

Also, some well-knowns due to GSM and Bluetooth.

A5/1 and A5/2 used in GSM phones, E0 used in Bluetooth. They are broken, see the links. According to this source NSA can break A5/1.


Valid private keys on curve25519 Given that valid private keys on curve25519 must be less than the order of the curve which is (as I understand) already smaller than 2^256, AND a valid key must be clamped to be divisible by 8 and have its high bit set, what is the actual 2^X number of valid private keys approx?

The private keys are integers $x$ with $2^{254} \leq x < 2^{255}$ and $x \equiv 0 \pmod 8$, or just $x \in 2^{254} + 8\{0,1,2,\dots,2^{251} - 1\}$, so there are exactly $2^{254}/8 = 2^{251}$ of them.


The output of experiments Real and Ideal in simulation-based security proof For simulation-based security proof in searchable encryption, there are two experiments running for the Real and the Ideal world respectively.

I can understand that the Real world experiment taking the real ciphertext and auxiliary information as the input, while the Ideal world experiment only taking the auxiliary information as the input.

However, it is a little bit difficult to understand the meaning of the output of these two experiments.

Normally, both Real and Ideal world experiment will output a bit. What't the meaning of this bit?

The question is rather abstract, so the answer will be rather abstract too.
In general in simulation-based proofs you compare two worlds (ideal and real).
Consider some protocol $\pi$ between two or more parties.

In the real world, the adversary corrupts some fraction of the parties and executes $\pi$ with the remaining honest parties that have some secret information.
The honest parties follow the protocol description, whereas the corrupted parties may behave arbitrarily.

In the ideal world, the corrupted parties interact with a simulator that does not have the secret information of the honest parties, but still tries to somehow simulate the messages that the corrupted parties expect.
To successfully accomplish this task, the simulator is usually given some sort of auxiliary information.

Now imagine that at the end of any interaction the adversary outputs a bit, which is its guess of whether it was in the real world or in the ideal world.
If the adversary cannot do much better than guessing in which world it was, then it will output bit $b$ with roughly the same probability in both worlds.
This in turn means that it cannot tell the difference between talking to real parties holding some secret information and a simulator that does not know the secret information, which in turn means that "nothing" about the secret information was leaked from the protocol execution in which the adversary participated.
Usually "nothing" is a bit much to ask for and thus we at least hope that the adversary learns nothing beyond what we gave the simulator as auxiliary information.

You can find a great introduction to simulation-based proofs here.
The concrete formulation, where the adversary outputs a single bit, which represents its guess regarding which world it was in, is common to security definitions in the Universal Composability model


generate RSA public key having public modulus and exponent i want to generate an RSA public public key file using openssl (or other tools) having public modulus and exponent, so i can use it later to encrypt files

i have this:

the modulus:

"BEB90F8AF5D8A7C7DA8CA74AC43E1EE8A48E6860C0D46A5D690BEA082E3A74E1"
+"571F2C58E94EE339862A49A811A31BB4A48F41B3BCDFD054C3443BB610B5418B"
+"3CBAFAE7936E1BE2AFD2E0DF865A6E59C2B8DF1E8D5702567D0A9650CB07A43D"
+"E39020969DF0997FCA587D9A8AE4627CF18477EC06765DF3AA8FB459DD4C9AF3"

the exponent: 0x10001

so how can i generate the public key from those, so i can use it to encrypt some data, or maybe there's a way to use these directly for encryption ?

i got this, it's not with openssl, but python

e = 0x10001
N = 0x1234214....

words = open("words.txt").read().split()

for w in words:
     ww = int(w.encode("hex"), 16)
     print pow(ww, e, N)


What is purpose of a simulator and extractor in zero knowledge proof protocols? I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat.

The author proposed a zero knowledge set membership protocol in page 9. Then, he stated in theorem 1 that the the protocol is a zero-knowledge argument of set membership. Then, he explicitly said "to prove honest-verifier zero-knowledge, we construct a simulator Sim that will simulate all interactions with any honest verifier V. This is all detailed in Page 8 and 9.

What is simulator, and what is purpose of Sim? Is the Sim an adversary? What does "the extractor" mean? If you look at the paper, the simulator in Fig. 2 looks exactly to the proposed protocol in Fig. 1.

The rigorous way to argue that the verifier learns nothing more than the validity of a statement in by designing a simulator. The simulator is an efficient machine that has oracle access to the verifier and given input the statement it simulates the view of the (adversarial) verifier. Since the simulation is possible using only the statement, it can be argued that the verifier learns nothing more (about the witness).

The extractor concerns zero-knowledge proofs of knowledge which are zero-knowledge proofs which additionally guarantee that the prover indeed holds the witness. In particular, the extractor given access to the prover (which it can potentially rewind) can extract this witness for example by rewinding it.


Size of Fresh Ciphertext's Noise in FHE over the integers I'm studying FHE over the Integer which is https://eprint.iacr.org/2009/616.pdf

In the remark 3.4, it says that the fresh ciphertexts have noise at most $2^{\rho'+2}$.

I don't know why that statement is true.

In my guess, the value $2^{\rho'+2}$ came from $m+2r$. But it cannot be strict proof of the statement.

Can anybody help me?

Let's look at the ciphertext:

$ c \leftarrow m + 2r + 2 \sum\limits_{i \in S} x_i \bmod x_0 = m + 2r + 2\sum\limits_{i \in S} (pq_i + r_i) + k(pq_0 + r_0) $ for some $k$.

When we do modular reduction by $p$, what remains is $ m + 2r + 2\sum\limits_{i \in S} r_i + k r_0 $. This (without $m$) is called the noise - as long as it doesn't wrap around $\bmod p$, decryption will succeed. So the term $ 2r + 2\sum\limits_{i \in S} r_i + k r_0 $ is what they are referring to with "noise".

I do understand your confusion though - while $2r$ does seem to have the longest bitlength $\rho' + 2$, I'm not clear on why $2\sum\limits_{i \in S} r_i $ can't exceed this, as we have up to $\tau$ terms that we are adding.

Sorry I couldn't answer your question in full!


NTRUEncrypt - Choose the initial random polynomial I'm trying to implement NTRUEncrypt but encounter some problems. I've finished all the basic functions that are needed for the scheme base on this Document, but I can't find an algorithm to check the validity of the initial polynomial f.

If f is not qualified (inverse mod p or inverse mod q doesn't exist) then the function to calculate the inverse modulo would end up in an infinite loop.

I've found some documentation about ntru con the ntru's website but there are too many of them and I don't have the time to go through them all. If anyone can help me with the algorithm or point out the document that I should read, that'd be helpful.

So long the GCD of f(1) with p and with q is 1, f will have an inverse with high probability. (f(1) = f evaluated at 1, i.e. the sum of the coefficients of f).

If you take f to be binary with df 1s, then take df to be relatively prime to p and q.

If you take f to be trinary and it has df 1s and df-1 -1s, then f(1) = 1 and this will satisfy the GCD requirement identically.

If you take f to be of form 1 + pF, f(1) is 1 mod p and satisfies that requirement identically. For the GCD requirement mod q, either pick F to be trinary with equal +1s and -1s (so f(1) = 1) or pick F to be binary such that 1 + p*F(1) is relatively prime to q.

"High probability" above means that the probability of not having an inverse goes down rapidly as both q and N increase. I've posted toy examples on Stack Overflow (http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key) and when I generated them I came up with invertible keys on the first attempt for N = 11, q = 29.


How does AES bit security increase by round? As AES progresses through multiple rounds, approximately how does it security increase round by round up to its maximum? I'm curious about the shape of the curve. Is it linear, some kind of exponential, a power law curve, etc.?

A few data points for AES-128. In 2018 Bar-On, Dunkelman, Keller, Ronan and Shamir described a 32-bit attack on 5 round AES (attack complexity here is the maximum of data, memory and computation requirements) and claimed a 99-bit attack on 7 round AES. The 2011 biclique cryptanalysis paper of Bogdanov, Khovratovich and Rechberger claims a 125.4-bit attack on 8 rounds and a 126.18-bit attack on 10 rounds. I'll claim a 128-bit attack against 11 rounds :-)
Based on our current knowledge then, perhaps it looks like an S-curve? Of course cryptanalytic effort has focussed strongly on larger numbers of rounds and I'd be hesitant to hypothesise any security vs. rounds function based on this.
ETA: The quoted figures for 8 and 10 rounds were for a related key biclique attack. The current best generic attack for 10 rounds is $2^{126.01}$


What does "overwhelming" mean in cryptography? I found the term "overwhelming" when I study cryptography.
According to the definition, we call $f$ overwhelming if $1-f$ is negligible.
I already know the negligible function and its way to use but I don't understand why we consider the overwhelming function.
Can someone teach me how to use it and some examples?

"With overwhelming probability" means that an event happens with probability at least $1−2^{Ω(n^\varepsilon)}$ for a constant $\varepsilon >0$.

Example: In a public key cryptosystem where $\mathcal{PK}$, $\mathcal{SK}$ and $\mathcal{R}$ are the spaces of public keys, secret keys, and sender randomness respectively, if $∆_{\mathcal{R}}$ denote the distribution on $\mathcal{R}$, then we require the usual correctness condition: for all $pk ∈ \mathcal{PK}$, all $sk ∈ \mathcal{SK}$, and $b ∈ \{0, 1\}$, we have $Dec_{sk}(Enc_{pk}(b; r)) = b$ with overwhelming probability over $r ← ∆_{\mathcal{R}}$.


Are those RSA keys flawed? I used rsa-json.native to generate RSA keys for a node.js application that will use secure-peer later to connect two clients with each other. Now I have 2 questions:

In secure-peer/index.js I've found defaultCiphers = ['RC4'] - is this acceptable? I've heard that RC4 is broken.
Are my example RSA keys flawed? They contain the same data at the end and beginning of the keys.

RSA-Key #1:

-----BEGIN RSA PUBLIC KEY-----
MIGJAoGBALJWTxyvIedsbg4QffU7vqvBlsHR8w6dfN19bSMiVjdSPoU2mKGN+n/Ck5gTPrWK
zz64JRrLWE7pYsd1YF1RQIbh8eUUNA3cUmVpuAdfolwpE3ixFlaYRgwGjwkaONoGerP9p1SS
VUCwuEfgmS14n5x9AQ/3HJVICQTb/2dryQqFAgMBAAE=
-----END RSA PUBLIC KEY-----

-----BEGIN RSA PRIVATE KEY-----
MIICWwIBAAKBgQCyVk8cryHnbG4OEH31O76rwZbB0fMOnXzdfW0jIlY3Uj6FNpihjfp/wpOY
Ez61is8+uCUay1hO6WLHdWBdUUCG4fHlFDQN3FJlabgHX6JcKRN4sRZWmEYMBo8JGjjaBnqz
/adUklVAsLhH4JkteJ+cfQEP9xyVSAkE2/9na8kKhQIDAQABAoGAJpEtyLlDLsYvQtFkPA2w
nXpfPQlHdCiw4UGHwapiVNJvfOWiuoV23/xXaPL4g9BCI4E1XQcO0Pn+B76lmWjB+EvVLTnw
SM0M/coY73mOT/Suc51OKG+cd9HnYjNe9hzwkbIwX73AcgyWRGYt0NAPbAFBM/xxLPNzSeyo
othjFYECQQD9BD/HDwbNycu3mhPOlhPU605xcZnWb2IOcSWoNb6zlq4JcVXXR/Nb1R4qPSBU
s+thdtc6Lpk+0Fr/iQaJ9f3hAkEAtHCiTQbsDBlR8ypCfau2CmHZ8nLMlYhtarzfcJ5PJZ0d
zQOVdcdivC5gIGs0t6+UH4KKbFBPSvuNH+pwZbx5JQJAAaj7eiThGIyQZ539L0fQzX7VvuzN
45hLfmjDpHzlyWvdrHYv5/+y2xFk50YLZkLf8n3DH8CahMz9K9wMTO9uQQJAeS6D8dNKSD3h
CbxB94CQu5xH8UokF/EN+vdp4IqRgSNp1jwn7ne/2b4TlPIq74odoqPbLy8ocaVLfDnIzqqr
eQJAB9j9REz3a5J1vAcFTcZ36pt3D6O/cF+9AB5jopeV5je2qJ2VRqMlr2yoxLEyEVNXHWbS
tkRRNBKgDChumUtMAA==
-----END RSA PRIVATE KEY-----

RSA-Key #2:

-----BEGIN RSA PUBLIC KEY-----
MIGJAoGBANMnnH3ZrBRVboez1+u5CS6nHg0M4BwkVGHfHDX3AdGyxxm2L8QFdOK3Uf5b9jCK
MlDGXPoCoqiT6FesQvtXcTSJ4ZkIPvY9BKi2qZ3oK7B50Rc5ULd8MsHoQH+DV436GlV/JRUg
NLgoouykKKryo7dSU2LzwcPc0v7w16HVebIHAgMBAAE=
-----END RSA PUBLIC KEY-----

-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDTJ5x92awUVW6Hs9fruQkupx4NDOAcJFRh3xw19wHRsscZti/EBXTit1H+
W/YwijJQxlz6AqKok+hXrEL7V3E0ieGZCD72PQSotqmd6CuwedEXOVC3fDLB6EB/g1eN+hpV
fyUVIDS4KKLspCiq8qO3UlNi88HD3NL+8Neh1XmyBwIDAQABAoGBAKtn7FD88gNPlnnyM8TW
X+3PG0XcvdAabaVFR9FGweNIDPeCPSQSid/AkH66iA6/IDkRzUfl+8R8zI7e90CwquNRmUWa
uBg1xO6heOGXn+HFUQlt0TXmnPw6CZl0yWGPhED7otO6wyFmSix8h+kR6ixWTGR0EfmtYfFw
MaLgpVWBAkEA8Jgz5NVjQUMz1s6zRXD65Tk9kjcKRuia3pccwvxXSbnm+jqE2jvqyA+ucVJu
+QzzxukPjBY3kzK4fVJ+KOgoPQJBAOCs1a6gOYdHoh19btROLoK3p3WK/dvPfWO2/yGB1VPh
d/1kI0N5oQ+taDRHTy0BGU/brxnMvhrV8dOD0NG3Y5MCQQC3AH5Qa8MAbBZtKHIRursMSfq8
UaM+hkTuVHCrG3dle8LlyEcvG+4cWFkuly4Tv7dZMAMEYg3JqAXORUXy5YtdAkARFTMeFvKo
1Yp/AYWGwPcKW1pxNoM8zlbzWPunGY8V1KPh8VY5ECtt3Lp6lx1vB5FcIBD9PjMKKVA8y935
xB7fAkEAsbtvwg3leiFz8biyWib8Gq7KDSEZOeBFKbPu7zDHR7koCxJoqjUtBA6WSJ6td5b+
RjnPQl6sh+lyQ1gEuAJMJA==
-----END RSA PRIVATE KEY-----

defaultCiphers = ['RC4'] - is this acceptable? I've heard that RC4 is broken.

About RC4 vulnerabilities in general, see e.g. Google is using RC4, but isn't RC4 considered unsafe?

RC4 can be secure when you discard (enough of) the beginning of the keystream or use a new key each session. Since node.js calls into OpenSSL, I don't think it does the former and can't see it done in secure-peer either.

From a look at the secure-peer source, it seems like they use Diffie-Hellman to get a shared secret and use that to derive the RC4 key and IV. That is should be safe, but I could be reading it wrong.

To test, you could try printing secret before this line:

var encrypt = crypto.createCipher(cipher, secret);

If it's different each time (for the same pair of peers), it's probably fine. Otherwise, there may be cause for concern.

  Are my example RSA keys flawed?

They certainly are now that you published them :)

But, no, probably not. RSA keys are stored in one of several formats that have some leading and trailing data that is similar for keys made using the same implementation.

The keys have format and version tags.
They may have information regarding whether the key is stored encrypted and with what algorithm, presumably the same.
The public key exponent is usually chosen as e.g. 65537 for all keys.


Exposing RSA private-key data... bad? We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$.

In OpenSSL (and most RSA implementations) decryption is done via the CRT, so we store $n$ and $d$, but also store $d \bmod (p-1)$ and $d \bmod (q-1)$ as CRT exponents.  Suppose these leaked... is there a practical attack?

Yes, there is a practical attack.  Leaking those (or even just one of those) allows us to factor the modulus quite efficiently.

Suppose the attacker knows the values $n$, $e$ (the public exponent) and the value of $d \bmod (p-1)$ (which we will call $dp$).

Then, the attacker selects a value $m$, and then computes:

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n)$

To see why this is likely to give us a nontrivial factor of $n$, let us consider the value of $m ^ {e \cdot dp-1} \bmod p$ (which we can do, even if we don't know the value of p).  We see that this is:

$m ^ {e \cdot dp-1} \bmod p = 1$

This is because $e \cdot dp = 1 \mod (p-1)$ (and Fermat's Little Theorem).

In contrast, this same value modulo q is (with high probability, assuming $m$ was selected randomly) not 1, and so $m ^ {e \cdot dp-1} - 1 \bmod n$ will have $p$ as a factor, but not $q$.  And thus,

$gcd( n, m ^ {e \cdot dp-1} - 1 \bmod n) = p$

with high probability.


emulating AES GCM with AES CTR Building off of Relationship between AES GCM and AES CTR... if your GCM nonce is "aaaa aaaa aaaa" (no spaces) then the CTR IV is that with (0,0,0,2) appending to it.

My question is...  what happens when the counter gets to (255, 255, 255, 255)? Would the last five bytes be (98, 0, 0, 0, 0) (where 98 = b) or would they be (97, 0, 0, 0, 0) (where 97 = a)?

I'm guessing the latter but idk.

Thanks!

In the NIST Special Publication 800-38D page #8 the maximum inputs lengths are defined in the standards as;

  The bit lengths of the input strings to the authenticated encryption function shall meet the
  following requirements:

$len(P) \leq 2^{39}-256$

and in section 8.3 the number of invocations requirements for all implementations:

  The total number of invocations of the authenticated encryption function shall not exceed
  $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with
  the given key.

As a result, the recommendation doesn't advice the overflow of the counter.

We can find the maximum as:

$2^{32}$ invocation, per invocation you can encrypt 128-bit ($2^7$-bit) with AES, thus

$2^{32} \cdot 2^{7} = 2^{39}\text{-bit} \approx 68.7\text{GB}$ is the maximum data that one can encrypt with AES-GCM under the NIST recomendation.


mapping a 256 bit random number to a 3 bit number I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao.

each user generates n sha3 hashes recursively of a random seed : e.g.

H[0] = sha3(sha3(seed))
H[1] = sha3(sha3(H[0]))
...
H[n] = sha3(sha3(H[n-1]))

During the nth round, we xor the H[nth] value of each user to be used as a random value for that round:random_result

My Question: What is the best strategy to map the 256 bit random_result to a 6 sided dice without completely botching the entropy?

Method 1 - Big Integer Math

Convert the 256 bit random_result to an unsigned big-integer. Divide by 6 and take the remainder. Your die roll result is the remainder plus one.

$6$ does not evenly divide $2^{256}$. It divides about $1.93\times10^{74}$ times with an exact remainder of $4$. That means values $1$-$4$ are over represented but by a negligible amount, since they're only represented once more than $5$ and $6$ over a gigantic range.

The bias towards low die rolls is much much much much less than $2^{-128}$, modern cryptography's slightly arbitrary threshold for the maximum detectable amount of bias in probability.

Method 2 - "Small" Integer Math

Let $M = 6 \times floor(2^{32} \div 6) = 4294967292$, ie. the largest multiple of 6 that fits into a 32-bit unsigned integer.

Split the 256 bits into 8 32-bit unsigned numbers. Find the first value one of those values less than $M$ and return one plus the remainder of its value divided by 6. This returns value has a value a range of values $[1, 6]$.

The reason for using values in the range $[0,M-1]$ instead of $[0, 2^{32}-1]$ is because the latter is not evenly divided by 6. Random numbers in the former range lead to a perfectly uniform distribution.

The probability of one 32-bit value being rejected is $p = (2^{32} - M) \div 2^{32} \approx 9.32 \times 10^{-10}$. All 8 are rejected with $p^8 \approx 5.66 \times 10^{-73}$ probability which is very unlikely. The exact probabilities happen to be $p = 2^{-30}$ and $p^{8} = 2^{240}$. Again, this is less than $2^{-128}$, so you shouldn't expect it to happen.

If it does fail 8 times you can derive more 256 bit numbers by hashing random_result concatenated with a counter. Or you can just use the final 32 bit value if the first 7 fail. The probability of that happening is small and the resulting bias is smaller.

The reason why I specify 32 bit numbers is for ease of implementation and for optimization reasons. There isn't any cryptographic relevance. 64-bit numbers and 64-bit division works as well, but it might not be available in some scripting languages and 32-bit division may be faster than 64 bit division on 32-bit and 64-bit architectures.

You could use 3 bit chunks. Then you could eliminate division entirely because 6 only divides 8 once. Rejecting an individual chunk happens with $1/4$ chance. Rejecting 85 times is less than $6.7 \times 10^{-52}$ or $2^{-170}$.

Method 3 - Seed a PRNG

This would be a really easy if CS-PRNGs were implemented in standard language libraries or popular add-on libraries with a similar API to those for non-secure PRNGs. Using standard PRNGs doesn't work for every application either because of statistical artifacts, small state space, predictability, or lack of a good seeding algorithm.

Edit: Avoid this method. I don't have a single example I can cite. There are too many ways it could go wrong.

No method has significant bias and therefore the entropy of the die roll has very close to $\log_2 6$ bits of entropy. (Assuming reasonably high entropy seed, like 128 bits of entropy. It doesn't need to have 256 bits of entropy.)

I don't think you want an answer based on entropy. I don't know what you mean by "botching the entropy" and I assume you don't know either.

For each method you can estimate entropy of the result by treating the entropy of the hash output about equal to $min(256, \text{seed-entropy})$ and calculating the probability of each outcome 1 through 6 by computing how many hash outputs map to that die-roll-value.

Since we already know the bias to be incredibly small we know that the die-roll result is about uniform. Since it is about uniform we know it has about the maximum entropy you can get out of 6 element discrete uniform distribution, $\log_2 6$.


How can I implement ID based encryption using RSA? I want to implement ID based encryption using the RSA encryption algorithm but how can I edit the algorithm for IDs.

Simple answer: you cannot. Identity-based encryption is an advanced cryptographic primitive, you cannot simply take any existing encryption algorithm and make it identity-based with simple modifications. There exists several constructions of IBE, but they all strongly differ from the standard RSA algorithm. You can find more information on the wikipedia page. There are several schemes that could suit you, such as Cocks QRA-based IBE (link on the wikipedia page) if you really want something that works in RSA groups (but note that it is not based on RSA). More classically, you could consider using a pairing-based IBE scheme, such as the famous scheme of Boneh and Franklin. Further details and links to implementations of IBEs can be found here.


correct usage of keys and nonce I've being studying up on AES, GCM, CBC, HMAC and a lot of other primitives and am somewhat ( a little bit, perhaps) familiar with them however I am still a bit weary on the use of the keys and nonce.

Background:
I have got multiple (embedded) devices (sometimes hundreds) all of which are connect to a server. These devices are to communicate with either AES-CBC HMAC or AES-GCM. when using HMAC I know first to encrypt then MAC. Further more these devices have a pre-installed key on them.

Here is what i think i know:
1. You can have 1 master key but AES and HMAC never use the master key directly
2. You should use a KDF like PBKDF2 to create a session
3. Every so often you should change the master key

Now say we start connecting a device to the server. Both the device and the server have the same master key but they must agree upon a session key. I cannot do this in any other way than to use Diffie hellman? simply sending over a salt for the PBKDF2 won't do since an attacker might alter it.

Then, when using CBC, we create a random number as IV, we encrypt the message, add the IV and then use the HMAC with the session key, append the result and send it over.

When using GCM we create a nonce, encrypt the text, append the nonce to the cipher text and send it over, we either keep sending the nonce over or we keep a counter on both sides either way we always +1 the nonce.

So my question:
is diffie hellman a must have? or is there an other way to do? keep in mind I am very restricted in processor power and memory so using a PKI with RSA is not an option.

is everything else i described correct?

1 final remark, It is often said it's better to use 2 separate keys (1 for encryption 1 for HMAC) this simply means using DH twice

PBKDF2 is an acronym for Password Based Key Derivation Function, #2. As you already have a key you need a Key Based Key Derivation Function or KBKDF instead. Currently the most up to date one is probably HKDF, which was - very quickly - also recognized by NIST. There are other KDF's such as KDF1 and KDF2 which are easier to construct (not many libraries contain KBKDF's by default).

You don't require Diffie-Hellman if you already have a shared secret, unless you also require Forward Secrecy.

What you can do is store device keys on the device, send over some device ID to the server that uses that to calculate the device keys from a master key. That way, if one device is compromised, you don't loose the master key (the device is fitted with the device key upon creation using the same algorithm).

Similarly you can use a key derivation from the device key using some unique session based information or large enough random to establish session keys. I would create 2 to 3 session keys:

for explicit authentication using a MAC (you don't want to use your secure channel for implicit authentication - trust me on this)
for encryption of the secure channel
for authentication of the secure channel (unless you use one key for encryption and authentication as in GCM)

It's best to use different session keys for client and server (e.g. by reordering the client ID and server ID) otherwise you may run into nonce reuse, replay attacks etc.

Note that the authentication data used for explicit authentication should contain as much data as possible, including one or more randoms, client ID, server ID and something to identify the session with.

So basically you don't require asymmetric primitives for such a scheme, although you may gain additional benefits from it. Forward secrecy is one, but you might also want to achieve anonymity to name just one other (I presume this is less important for your use case though).


iO from Matrix Branching Programs Recently I'm learning about constructing iO from Matrix Branching Programs via Multi-linear Maps (to be exact, [GGH+13] and [GGH15]). However, I have a small question that I couldn't figure out.
It seems like the steps of converting a program/circuit into an obfuscated one is to first convert it into an MBP (a bunch of $M_{i,b}$s) via [Bar86]. Then, we can use Kilian randomization to add random 2k $R_i, R_i^{-1}$ matrices to make the MBP matrices distribution look random. Next, we put this into the MMap framework that allows people to do add/multiply plus a zero test. Finally, there's some construction that protects input mixing attacks.
My question is that why we need to put this MBP into the MMap framework? It seems like that after the Kilian randomization, the matrices in the MBP already look random and don't leak information. Couldn't we just publish the randomized MBP as the obfuscated version of the program? I feel that I'm missing something here...

The problem is that two partial evaluations of same length $\ell$ will have the form
$R_0 B_1 R_\ell^{-1}$
and
$R_0 B_2 R_\ell^{-1}$.
Thus, because the attacker possible knows $B_1$ and $B_2$, they can learn something
about the branching program that is obfuscated.
Encoding these randomized matrices with the multilinear map hides (or at least tries to hide) these relations.
Consider the security definition of iO.
It says that an attacker chooses two equivalent branching programs $P_1$ and $P_2$, sends them to an obfuscator, and then receives an obfuscated program $P$. The goal is to guess if $P$ corresponds to $P_1$ or $P_2$.
Now, if the obfuscation is done without the multilinear map, an attacker can break the security definition as follows:

Choose two different matrices $A$ and $B$;

Choose a length-2 branching program $P_1$ with a single input bit as follows:
$$\text{bit 0:} ~ ~ ~ ~ I  ~ ~ ~ ~ A$$
$$\text{bit 1:} ~ ~ ~ ~ I  ~ ~ ~ ~ B$$
$$\text{inp}(1) = \text{inp}(2) = 1$$

Choose a length-2 branching program $P_2$ with a single input bit as follows:
$$\text{bit 0:} ~ ~ ~ ~ A  ~ ~ ~ ~ I$$
$$\text{bit 1:} ~ ~ ~ ~ B  ~ ~ ~ ~ I$$
$$\text{inp}(1) = \text{inp}(2) = 1$$

Notice that $P_1(0) = P_2(0) = A$ and $P_1(1) = P_2(1) = B$, thus, they are equivalent programs.
Now, if $P$ obfuscates $P_1$, it is of the form
$$\text{bit 0:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot A \cdot R_3^{-1}$$
$$\text{bit 1:} ~ ~ ~ ~ R_1 \cdot R_2^{-1}  ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot B \cdot R_3^{-1}$$
Thus, we can distinguish the obfuscated programs by checking if the matrices
corresponding to the first step are equal.


FFT multiplication for RLWE key exchange I am try to multiply two  polynomial quotient ring of type $R=Z[x]/\phi(x) $ in sage using Fast Fourier Transform.:

a=Rq.random_element()
R. = PolynomialRing(GF(40961))  # Gaussian field of integers
Y. = R.quotient(X^(dimension) + 1)   # Cyclotomic field
ouput=Y(a)*Y(a)

I have found the following code on github to do this job but it is for simple polynomials and when I run this code for quotient polynomial, It give me following Type error

Sage itself has an internal negacyclic convolution, which is what is necessary here. To avoid type errors, we convert the polynomials to lists of coefficients, and work with those instead:

from sage.rings.polynomial.convolution import _negaconvolution_fft

n = 10 # degree 1024
Rq = GF(40961)
R.<X> = PolynomialRing(Rq)
S.<x> = R.quotient_ring(X^(2^n) + 1)
u = S.random_element()
v = S.random_element()

w_1 = S(_negaconvolution_fft(list(u), list(v), n))
w_2 = u * v
assert(w_1 == w_2)


For AES CBC, can I encrypt the IV with AES ECB and the same key and include it with the message? Is it safe to use this process:

Generate Key, IV
Encrypt Message with Key, IV and AES CBC into EMessage
Encrypt IV with ECB into EIV
Send over EIV + EMessage

Then the recipient

Decrypt EIV with Key into IV
Decrypt EMessage with IV and Key into Message

The thing that I'm worried about is that encrypting the IV with the same key gives additional information about the first block (and therefore subsequent blocks).

Edit: There was a great response with a direct proof in the case that the first block is all zeroes. What about this revised process:

Generate Key, IV1, IV2
Encrypt IV2 + Message with Key, IV and AES CBC into EMessage
Encrypt IV with ECB into EIV
Send over EIV + EMessage

Decrypt:

Decrypt EIV with Key into IV
Decrypt EMessage with Key and IV into IV2 + Message
Throw away IV2

This seems to counter the information lost at the cost of one additional block of data in the message.

It actually leaks information. You are sending:

Encrypted IV: $AES(k,IV)$
First ciphertext block of CBC: $AES(k, M_1 \oplus IV)$

Eavesdropper can observe whether the two blocks are equal, which happens iff $M_1$ is all zeroes.


Calculating random number in ECDSA based on private key and signature In ECDSA (Elliptic Curve Digital Signature Algorithm) we use a random number k in the signature process.

Signature in ECDSA is:

$$ (x_1,y_1) = k * G $$
$$r = x_1 \mod n $$
$$s = k^{-1} (z+rd_{a}) \mod n$$

If we know the private key $d_a$ and signature (r,s) would it be possible to calculate random k? If no how hard would it be to calculate that?

This is immediate:
$$ k = s^{-1} (z + r \, d_a) \bmod n $$
where $z$ is the hash value of the message being signed.


How many different keystreams can I produce with AES in Counter Mode? I'm using a 64-bit nonce (incremented between the streams) and a 64-bit counter (incremented within a stream) for AES in CTR mode. How many different key streams can I produce with this setup?

The number of different key streams depends on the keysize used and the number of bits in the nonce. Say you are using an $n$ bit key and $k$ bits for your nonce. Then the theoretical maximum number of keystreams is $2^n\cdot 2^k=2^{n+k}$ since each combination of nonce and key should result in a different keystream.

If you limit the length of your keystreams, however, this changes. Say you only want $128$-bit keystreams, but you use a $256$-bit key and a $64$-bit nonce. There will only be $2^{128}$ different key streams.

So, if your keystreams are $s$ bits long, you use an $n$ bit key, and a $k$ bit nonce, then really, the number of possible key streams is $\min(2^{s}, 2^{n+k})=2^{\min(s,n+k)}$.

Update
Based on the comment that the key is fixed, this changes the analysis. Since there is only one key it becomes $\min(2^{s}, 2^{k})=2^{\min(s,k)}$. The above analysis if for a randomly chosen key.


What are the advantages of neural cryptography over Diffie-Hellman algorithm? I am not sure whether such a question is accepted here, or if this is the correct place to ask.

I have done some research on this topic, however most of the information was way too complex for me to understand. I know that the most used protocol for key exchange between two parties A and B, in practice is Diffie-Hellman protocol.

I have read here, and understood the basic working protocol for neural cryptography but do not see any clear advantages over the Diffie-Helman algorithm.

What are the advantages (if any) of neural cryptography over the Diffie-Hellman algorithm?

I am not an expert either, but from what I gather the intent is to create a key exchange mechanism that is not based on any number theory problem. The concern is that advances in computing such as quantum computing could make the existing one-way functions such as prime multiplication effectively a two-way function. The authors believe that the neural exchange process will not be as vulnerable to advances in computing.

However the authors also acknowledge that their initial implementation is vulnerable to attacks using probabilistic analysis or genetic algorithms.

So at the moment, there is no advantage. The research is based on creating a future advantage, assuming that they can create a more secure implementation, and that future attacks do in fact become more sophisticated in the way that we expect.


Eliptic curve verifiable secret sharing I am implementing the following the algorithm instructions as shown in 1 (section IV, B).

When trying to verify the share given the commits, $a_jG$ verifier $i$ checks whether $f(i)G=\sum_{j=0}^{t} (x_i)^ja_jG $.
The phrasing of the verification is unclear to me, on the left side of the equation there is a scalar on the elliptic curve, on the right side there is a a polynomial.
Should the polynomial on the right be evaluated at point $i$?

A robust threshold elliptic curve digital signature providing a new verifiable secret sharing scheme

I cannot access the linked document, but I think that $G$ is a generator point of the elliptic curve, so you will have points on both sides.


Regarding the feasibility of MPC protocols I know that there is a general result stating that any function can be computed in an MPC protocol. In this question, I'm interested in understanding the practicality of MPC protocols.

Are any theoretical results regarding the feasibility of MPC protocols? To be more specific, are there any functions that are infeasible to compute in an MPC?
Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

Are any theoretical results regarding the feasibility of MPC protocols? To be more specific, are there any functions that are infeasible to compute in an MPC?

Yes, there are hundreds of paper on MPC feasibility. The answer always depends on the adversarial model. Here are a few of the more well-known/standard results:

$n$ parties can compute any function of their inputs, in the presence of a passive (semi-honest), computationally unbounded adversary that corrupts strictly less than $n/2$ parties.
There are functions that can't be computed in the presence of a passive adversary that corrupts $\lceil n/2 \rceil$ parties.
$n$ parties can compute any function of their inputs, in the presence of an active (malicious), computationally unbounded adversary that corrupts strictly less than $n/3$ parties.
There are functions that can't be computed in the presence of a malicious adversary that corrupts $\lceil n/3 \rceil$ parties.
$n$ parties can compute any function in the presence of a passive computationally-bounded adversary that corrupts any number of parties.
Most functions can't be computed against an active adversary in a way that provides universal composability, if there is no setup (like a common reference string).

I have taken all of these examples from a survey chapter that I co-wrote on the topic. You can find the original references there.

  Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

This is a harder question to answer because it is more about concrete efficiency than feasibility. There are theoretical results about how you can compute everything securely with "constant overhead" relative to the plaintext computation, but none of these results are what you would consider practical.

Using a more colloquial interpretation of what's "practical", pretty much everything falls into your category of "impractical" under secure computation. As @SEJPM points out in the other answer, unless you know that your problem has a lot of structure, the only known way to do 2-party secure computation would be to translate it to a boolean/arithmetic circuit and securely evaluate that circuit. This is many orders of magnitude slower than just computing something on raw data.

I know very few examples where the secure computation is reasonably close in efficiency to the plaintext computation. One such example is private set intersection, which is only ~ 6-8x slower than insecurely computing the intersection.


Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$ This is a homework question, therefore I'm not expecting full solutions, just general guidance.

I want to build a one-time MAC using universal hashing.

I defined my hash functions as:

  $h_{a,b}:\begin{array}{lll}
\mathbb{F}_{2^{n}} & \to & \mathbb{F}_{2^{n}}\\
x & \mapsto & ax+b
\end{array}$ for $a\in\mathbb{F}_{2^{n}}\backslash\left\{ 0\right\} $, $b\in\mathbb{F}_{2^{n}}$

Where $\mathbb{F}_{2^{n}}=GF\left(2^{n}\right)$ means the galois field/finite field of size $2^n$.

These functions have 0 probability of collision for two distinct messages.
However, in order to use these functions as a one-time MAC, I need to show security which is defined for the following game with adversary $A$:

  An oracle generates a secret key $a,b$, then $A$ can choose exactly one message $m$ to query, that the oracle tags for $A$ with $h_{a,b}\left(m\right)$). Then $A$ has to generate a message $m'\neq m$ and tag $t'$ such that $h_{a,b}\left(m'\right)=t'$.

Security is defined as for any efficient (polynomial) adversary $A$ allowed only one query (as described), there exists a negligible function such that the probabilty of $A$ winning the game is at most that negligible function.

This is where I'm stuck. I have intuition, but can't formulate a formal proof. I know that if $A$ decides to query with message 0, then he knows what b is, since
$a\cdot0+b=b$, but then he's left with guessing $a$ (need to show here he can't do it other than randomly guessing). And if he decides to query message $m$ that is not 0, he could at most calculate $\left(a\cdot m+b\right)m^{-1}=a+bm^{-1}$ which is the same problem (more or less) as $am+b$.

I would love some direction on how to approach such proof of showing finding such message with a viable tag, reduces to guessing at best (therefore showing an upper bound that is negligible).

Thanks!

You are in the right direction.

First, some intuition. The idea is that $y = ax+b$ constitutes a line, and if you need two points in order to fully determine it. However, if you only know one point, and if you don't have any additional information, then it is not possible to determine which line is it since there are "infinitely many" lines passing through the given point (of course, since we're on a finite field there are finitely many, but you get the idea).

Now, for the formalization, imagine that $A$ queries the oracle on some $m$ to get $t = a\cdot m + b$ (let's ignore how $A$ chose $m$, maybe it was crafted in some way, perhaps $m=0$ as you said, but this will turn out to be irrelevant).
We claim that if $A$ successfully crafts another message-tag pair $(m',t')$ with $m=m'$, then it is because $A$ guessed $a$, which is not possible since it was chosen at random from a large enough domain.
Now, this is argued easily by something I already mentioned: given two different points on a line, you can get the line and therefore the coefficients $a,b$.
In other words, once you fix $(m,t)$ with $t = a\cdot m+b$, getting a new $(m',t')$ allows an adversary to find $a$ as $a = (m-m')^{-1}\cdot(t-t')$.
This finishes the argument.


Can we always find a key to map a given plaintext block to a given ciphertext block in AES? I am revising for my exams and I have come across this question in a past paper and I am not confident about it at all.

Assuming that only the smallest permissible key and block sizes can be used I have derived the following:

Possible plaintext blocks: $2^{128}$

Possible ciphertext blocks: $2^{128}$

Possible mappings: $(2^{128})!$

Possible keys: $2^{128}$

My assumption is that it is true that you can find a key given a plaintext and ciphertext since there are significantly way more mappings than there are keys. But then again, are there even enough mappings for that to be possible?

I really feel like I am missing something important here. Are there any hints or suggestions you can give?

The answer is no, such a key need not exist.  Let the given plaintext/ciphertext pair be $P,C$ and let $n=2^{128}.$

How many permutations on $n$ points map $P$ to $C$? Clearly $(n-1)!.$
Thus, if we could uniformly sample all possible permutations, the probability that under a given permutation $P$ would map to $C$ is a tiny
$$
\frac{(n-1)!}{n!}=\frac{1}{n}.
$$

Since the AES keyspace also has size $n,$ the expected number of keys that would have this property is $n\times(1/n)=1,$ provided we assume AES perfectly samples the keyspace with respect to this arbitrary property $P\mapsto C.$  But there are no guarantees that it does so since it uses only 128 bits instead of $\log n!$ bits.


Example of CHI Square test on Caesar Cipher? I am trying to get my head round the chi square test, when used with the Caesar cipher.
I started off using this formula,

$$ X = \sum_{i = 1}^k \frac{f_i · f'_i}{n · n'} $$

Where $k$ is the number of distinct letters in the alphabet, $f$ is the number of times the $i$-th letter appears in the first string and $f'$ is the number of times the $i$-th letter appears in the second string. And $n$ and $n'$ are the total number of characters in the first and second strings.

However when I run this, the highest value is not always the correct result. I was expecting values to be around 0.0650, however my correct answer is coming out around 0.0700. Is this the right way of calculating the Chi value?

The formula on Wikipedia is a completely different formula, and the values should be near to 0 for the correct answer? Which has confused me.

I'll assume that the objective is to assert if the distribution of the $f'_i/n'$ is sufficiently similar with the distribution of the $f_i/n$ to support that a substitution cipher (including Caesar cipher) with the same permutation table and same frequency of plaintext characters could be used in both case.

If $n \gg n'$, $f_i \gg 5$ and $f'_i \ge 5$ for each $i$, we can use the first sample as reference; the expected $f'_i$ is $n'·f_i/n$, and the usual Chi-squared test is now to compute (update: formula and condition fixed)

$$X = \sum_{i = 1}^k \frac{(f'_i-n'·f_i/n)^2}{n'·f_i/n} = \sum_{i = 1}^k \frac{(n·f'_i-n'·f_i)^2}{n·n'·f_i}$$

which should be distributed as a Chi-squared variable with $k-1$ degree of liberty under the null hypothesis. We can reject the null hypothesis (substitution cipher with same permutation table and frequency of plaintext characters, assumed independent) if $X$ is bigger than found in a table for Chi-squared confidence test. E.g. for $k$ = 27 and $X$ > 38.9, we reject the null hypothesis with confidence level 95%. CAUTION: we have disregarded the fact that letters in the plaintext are not independent, and this will tend to make $X$ bigger than predicted by the null hypothesis.

If some $f'_i$ (or $f_i$) are too small, an option is to aggregate the smaller ones into a single value (and reduce $k$ accordingly).

If fail to find a reference on what to do when $n$ and $n'$ are of the same order of magnitude.


Is using the same IV in AES similar to not using an IV in the first place? So if I understand how an IV works with AES, I'm supposed to generate a different IV for every message because using only a key, I will get the same encryption if the message was encrypted twice (which is not secure) thus we use the IV which is some kind of a salt (some random bytes added to the encrypted message so 2 messages with the same value won't have the same encryption).

Now my question, is using the same IV for all of my messages the same as not using an IV at all? Or is it slightly better?

Lets see if I can clarify things for you.

For one, the IV is not specifically related to AES at all.  AES is a keyed invertible transform from a 128 bit value to a 128 bit value; that's all it can do.  Now, if you just happen to have a 128 bit value that you want 'encrypted' into a 128 bit ciphertext, well, you can just use AES as is.

However, we typically want to other things than that; we may have plaintexts which aren't exactly 128 bits long; we might want nondeterministic encryption (so that if we encrypt the same value twice, it's not obvious that we did so); we might want integrity checking on our ciphertext as well.

To allow us to do those things, we use a Mode of Operation; that's a construction that uses AES (or some other block cipher) to perform these more generally useful operations.  It is these modes of operation which may (not all do) take an IV.

At the moment, the most popular modes of operation are CBC and GCM; they also have very different requirements to their IVs.

So, in that context, I'll answer your questions:

  I'm supposed to generate a different IV for every msg because using only a key I will get the same encryption if the message was encrypted twice

That's not the complete story; yes, if you use the same IV, same message and same key (and same AAD for GCM), you'll get the same ciphertext, but that's not the full reason.

For CBC, if you use the same IV, there are two potential problems; one is that you'll leak how the two plaintexts are related.  For example, if the two plaintexts have the same first 16 bytes, and differ in the second 16 bytes, that'll be obvious to the attacker.  The other is that if the attacker can predict the IV (which he can if you use the same one repeatedly), and if he can introduce his own plaintext (which can happen in some scenarios), then he can use the encryption operation as an oracle (and thus deduce the value of low entropy plaintext blocks encrypted by the same key).

For GCM, if you use the same IV, there are two different potential problems (both of which are far more serious); for one, he can deduce the bit-wise xor of the two plaintexts (which is often enough for him to deduce those plaintexts).  Worse, it allows the attacker to deduce the internal authentication value, and thus allow him to modify ciphertexts (and thus the resulting plaintexts) without being detected.

  Now my question, is using the same IV for all of my messages is the same of not using IV at all? Or is it slightly better?

Well, for neither mode, you don't have an option of 'not using an IV'; when you perform a CBC or GCM operation, an IV must be there (for GCM, you can have a zero length IV; that's not quite the same as 'not having an IV').

And, you didn't ask, but I'll state the general wisdom anyways:

For CBC mode, the IV really ought to be unpredictable to the adversary.  Now, you can pick it randomly each time, or you can use (say) an AES encryption operation with the same key to generate it (which the attacker can't predict, as he doesn't have the key); both works.
For GCM mode, it doesn't matter in the least whether the IV is predictable to the adversary.  What's critical is that you use a different one each time.  If you can manage a counter (e.g. if you restart the program, you'll pick a fresh key), then using IV=0 for your first message, IV=1 for your second, etc, is the obvious approach.


Request for 1024-bit primes $p$ , subgroup $q$ and subgroup generator $g$ I need to find a prime $p$ of $1024$ bits with a $160$ bit sub group size $q$, such that $q|p-1$ , and $g$ is the generator of the sub group size $q$.

I'm looking for the numeric values of $p$ , $q$ and $g$.

Suitable values are
$q=2^{159}+9593, p=2^{1023-159}*q+1, g=2^{2^{1023-159}}\mod p$

I have checked the values given in section 2.1 of RFC 5114 and they seem fine too.

Whether "it's safe to use them" depends entirely on how they're being used, what you're trying to prevent, against whom and for how long and what the consequences of getting it wrong are.


Maybe Interactive, Not Zero-Knowledge, Arguments of Knowledge zkSNARK is a technique composed with the following features:

zk: zero-knowledge
S: Succinct
N: Non-interactive
ARK: ARgument of Knowledge

Everywhere I look on the web for material on cryptographic arguments of knowledge I find techniques that mush these four features together. I am only interested in feature 4, that is a technique with no conditions on features 1, 2, or 3, for Alice to prove to Bob that she correctly performed a computation without Bob needing to perform the computation. Could I find literature under a more commonly used name for this technique than 'argument of knowledge'? Can you please point me to some literature on this technique?

I am curious which of the 4 features are at the core of the research in this area. Is it feature 1 that makes these cryptographic techniques so hard? or features 2 or 3? If the difficulty of current research is in solving a combination of features 1, 2, and 3, then shouldn't there exist simpler, more successful techniques that only need to solve feature 4? If so, I'd like to learn about these techniques. Ideally I'd get a response like "sure, if you don't need features 1, 2, or 3, simply ...".

The zero-knowledge property is not the core feature, in the sense that it's already very challenging to come up with a construction satisfying 2-4, and once it's done, adding zero-knowledge usually comes almost for free.

The property 4 is necessary, as it is implied by the property 3: if you want succinctness, you cannot hope to get unconditional soundness. The intuition between this is that if we have a proof of size $n$ for (say) 3-SAT, then we can slove 3-SAT in time $2^n$, by doing exhaustive search over possible proofs (the formal result is a bit more involved as it also considers interactive proofsm but that's the main idea). Therefore, $n$ cannot be much smaller than the witness size, otherwise we would get a subexponential time algorithm for 3-SAT (which would be a major breakthrough).

The property 2 is essentially the one you want to keep: succinctness usually means that the size of the proof and the computation time of the verifier are sublinear in the witness size. And this is exactly what is hard to get :)

Eventually, non-interactivity is usually not the core issue if you are ok with working in the random oracle model - although that's not always the case, most constructions of succinct proofs can be made non-interactive in the random oracle model.

From your question, I guess that what you are looking for is not a succinct proof for all NP language, but only for proofs of languages in P, where the verifier could in principle redo the entire computation himself, but this would be too expensive. Proving correct computation is easier than proving all statements in NP. This was studied a lot (I'm giving keywords here) in the context of delegation of computation. I think one of the seminal papers in this area (you can also look via Google Scholar the papers that cite it) is this one. A more recent, really cool paper in this area is this one. If you provide us more details about the exact specifications of your problem, I might also be able to give you more pointers; delegation is an active research area, with many papers providing efficient solutions in many settings.

Summing up, if you only want succinctness and languages in P, this is indeed easier than building a zk-snark for all of NP, but that remains far from easy.


Is any group of bits in a SHA-1 hash more/less unique than another? Is there any bias in certain parts of the hash? E.g., first n bits are more/less unique than the last/middle n bits? Is there any particular property of any group of bits that makes it more/less unique?

Thanks

Yes in a sense in terms of the Hamming weight/Hamming distance. This relates to how the changes of one bit or series of bits affect others. While there is also an avalanche effect counteracting many n string bits attacks, Hamming dictates some attacks to be more successful on certain n bit strings and thus certain n bit strings more vulnerable to exploits:

http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf

http://www.sciencedirect.com/science/article/pii/S0166218X02005887


Transparent Setup of SNARKs The STARKs paper states

  Third, and most important, ZK-PCPs are transparent (or “public
  randomness” ), which means that the randomness used by the verifier is
  public; in particular, setting up a ZK-PCP requires no external
  trusted setup phase

as one of its main advantages over SNARKs.
This statement is not fully clear to me.
Which properties rely on this "common random string"?
Does the verifier only "trust" a received proof if he/she trusts that the public random string was chosen uniformly at random?
If not, why can't the prover simply pick a random string itself and send it along with the proof if the setup does not need to be trusted?
This way there would be no setup at all.

That is a very good question. First, observe that in general, using a common random string (or any other form of trusted setup) is necessary to get any provable security guarantee, as soon as you want your proof system to handle statements outside of BPP. Indeed, it is known that non-interactive zero-knowledge proofs without any trusted setup can only exist for languages in BPP.

So, it is necessarily the case that "something" relies on the common reference string being sampled at random, in a trusted way. That "something" can be either soundness, zero-knowledge, or both (since those are the two security properties we care about). With most existing proof systems, the crs is actually needed for both:

if the prover picks the string himself, he can break the soundness of the proof (i.e., prove incorrect statements)
if the verifier picks the string himself, he can break the zero-knowledge property of the proof.

Whether this issue can be mitigated has been studied under the name of subversion resistance. This is a line of work which attemps to build NIZKs/SNARGs that maintain some security guarantees even if the common reference string is adversarially subverted. It was initiated in this paper. Essentialle, it shows that achieving zero-knowledge and preserving soundness under subversion at the same time is impossible - however, the other way around is possible. Several follow-ups (1, 2) have built various subversion-resistant SNARGs.

The transparent setup of STARKs avoid this issue essentially by relying on the Fiat-Shamir transform; in the random oracle model, it is in fact possible to have NIZKs without setup for arbitrary languages, so that's just what they do (succinctly). Of course, in the end, their non-interactive argument has no provable security guarantee in the plain model, but only heuristic security guarantees given by the analysis in the ROM.

So to conclude:

Standard SNARGs: you need to perform a trusted setup or find a globally verifiable source of randomness which is hard to manipulate (e.g. the result of the last 100 loteries, or randomness extracted from black spots on the sun, or whatever you like - to be honest, any nothing-up-my-sleeve number should work in practice, so you can just take the digits of Pi). But in exchange for that, they can be proven secure under some (non-standard) assumption, in the standard model.
STARKs: no trusted setup, you have a provably secure construction, but only in an idealized model with a random oracle. This gives you something heuristically secure, but with no formal security argument, when you replace the random oracle with a true hash function. However, it removes the burden of finding a source of globally verifiable randomness.


Known-plaintext attack on 1-round Feistel networks Consider a simple, 1-round Feistel network.

Because the ciphertext is essentially $(L_1,R_1)$, if one knows the plaintext $(L_0,R_0)$, the only unknown left is $K$.

However round functions in Feistel networks are not necessarily invertible. For example, one could in principle use a cryptographic hash as a round function.

The Feistel network equation would become:

$R_1=L_0 \oplus \operatorname{sha2}(R_0,k_1)\\L_1=R_0$

One could XOR $R_1$ (known ciphertext) and $L_0$ (known plaintext), thus obtaining $\operatorname{sha2}(R_0,k_1)$, but this would not yield the key unless one uses brute force.

Clearly brute force is always possible - and there are other issues with a 1-round Feistel network, for example it leaks half of the plaintext - but I was wondering.

When one talks about KPA against 1-round Feistel networks, is it implicit that brute force can be used in the end to obtain $k$, for non-invertible round functions?

Regardless of the specific $f$ function, you already observe that you can obtain
$$
R_1\oplus L_0=f(R_0,k_1)
$$
where $k_1$ the first round subkey is your target.

But $R_0$ is also a part of the known plaintext. So you have a system of equations for the bits of $k_1$ which you can systematically attempt to solve. For a normal Feistel function $f$ (which is one to one or the cipher wouldn't be invertible) this is straightforward.

Exactly how $sha_2(R_0,k_1)$ is defined plays a part here:

Possibilities include $sha_2(R_0||k_1),$  or $sha_2(R_0 \oplus k_1)$ (possibly with padding or repeating of $k_1$ to make it the same length as $R_0.$).

In any case you can try to use the $sha_2$ equations, noting that the effective input length is essentially at most the length of $R_0$ plus the length of $k_1$ and hence a strong hash function is most likely one to one for such inputs. Using the random oracle model, a randomly chosen function from an input of length, say, 128 bits, to the full digest size for sha_2 of 512 bits is one to one with overwhelming probability (see birthday paradox, addressed in many answers to questions on crypto stackexchange).


Why is PuTTYgen-created RSA public exponent(e) not in {3,17,65537}? As far as I know, RSA public exponent(e) should be one of {3,17,65537}.
However, I found PuTTYgen-created RSA public exponent(e) is 0x25(37) by default,as follows, (PuTTYgen version: 0.66)

I am curious why PuTTY uses 0x25(37) instead of 0x10001(65537), and does 0x25(37) offer adequate security?

The answer is in the source, file sshrsag.c, line 9:

  #define RSA_EXPONENT 37             /* we like this prime */

This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent:

$e$ is odd,
$e$ is at least $3$,
$e$ is reasonably small.

The later condition

is good for speed of operations involving the public key (encryption, and signature verification);
makes it harder to choose the prime factors of the public modulus so as to get an unnaturally small $d$, which could allow factorization.

That $e=37$ is prime simplifies the choice of the prime factors of the public modulus $N$, as explained in a later comment:

  Generate $p$ and $q$: primes with combined length `bits', not congruent to $1$ modulo $e$. (Strictly speaking, we wanted $(p-1)$ and $e$ to be coprime, and $(q-1)$ and $e$ to be coprime, but in general that's slightly more fiddly to arrange. By choosing a prime $e$, we can simplify the criterion.)

The only known drawback of $e=37=2^5+2^2+1$ compared to $e=17=2^4+1$ or $e=3=2^1+1$ is that raising to the 37th power modulo $N$ requires 7 modular multiplications, versus 5 for the 17th, or 2 for the 3rd.

We can speculate that the authors like $e=37$ because it is not of a special form, as are the Fermat primes $F_k=2^{(2^k)}+1$ with $0\le k\le4$, often used as RSA public exponents. A compromise between being large and allowing efficient public-key operation was likely not part of the considerations: the larger $e=41=2^5+2^3+1$ also requires only 7 modular multiplications (and as a bonus, is closer to the Answer).

The rest of this answer reports on my incomplete review of the RSA code of PuTTY 0.66, aimed at weakness related to the relatively small $e=37$. I have not identified any if the generated key is used by (that version of) PuTTY, and all other entities relying on the corresponding public key do so properly. Otherwise, I can't rule out that some systems have vulnerabilities that could be more easily exploitable with PuTTY's $e=37$ than the traditional $e=65537$ mandated as the minimum by several security authorities. I'm thinking in particular of

incorrect verification of PKCS#1 V1.5 type 01 signature, which abound; see Daniel Bleichenbacher's RSA signature forgery based on implementation error (archived account by Hal Finney of Crypto 2006 rump session); Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and yet other reports.
vulnerable (even if conformant) implementations of decryption per PKCS#1 V1.5 of padding type 02, as considered by Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 (in proceedings of Crypto 2008).

There is no known weakness associated to using small $e$ when RSA is used with good padding (as RSASSA-PSS and RSAES-OAEP in PKCS#1 V2). Other RSA paddings supported in PuTTY include lesser PKCS#1 V1.5 paddings, but I did not find the dreaded padding type 00, which essentially is no padding, unsafe, and even more unsafe for small $e$. PuTTY can use PKCS#1 V1.5 padding type 01 for signature, which has no known vulnerability for correct verification, as performed by PuTTY. It can use PKCS#1 V1.5 padding type 02 for encryption, but does not implement decryption with potentially vulnerable padding check.


Hashing a Diffie-Hellman result In many implementations, the result of the Diffie-Hellman algorithm is hashed. I read that:

  Hashing the shared secret point prevents an attacker from gaining more information about the EC private keys used to generate the shared point.

Could someone give me an example of how to get information about the private key with a shared secret that isn't hashed?

I have never heard of this reason, and I don't quite understand it. In general, the security of Diffie-Hellman key exchange is reduced to the DDH assumption. According to this assumption, the result of the key exchange is a group element that is computationally indistinguishable from a random/uniformly distributed element in the group. However, what is important to note is that a uniformly distributed group element is not a uniformly distributed string (where the latter must have each bit equal 0 with probability 1/2 and equal 1 with probability 1/2). In particular, if you work in $\mathbb{Z}_p^*$ then the most significant bit will certainly not be uniformly distributed. Likewise, if you are working in an Elliptic curve group, then the result is a pair of field elements which fulfill the Elliptic curve equation. Therefore, in order to derive a uniformly distributed string, you need to apply a function that extracts a uniform string from a high entropy source. These are called extractors or key derivation functions. This is the reason that you hash.

I note that it's possible to prove the security of Diffie-Hellman key exchange under the CDH assumption and in the random oracle model. In this case, the hash function is needed to get a long pseudorandom string from a computational assumption. However, I think that explaining this here will be "too much information".


Weakness of SRP after server compromise From SRP section 3:

  The host stores user passwords as triplets of the form

{ <username>, <password verifier>, <salt> }

  Password entries are generated as follows:

<salt> = random()
x = SHA(<salt> | SHA(<username> | ":" | <raw password>))
<password verifier> = v = g^x % N

  Where g and N are agreed upon in advance.

They claim resistance against server compromise, but if an attacker gains access to the password verifier v, how much work is required per guess, to perform an offline brute force dictionary attack?

If I'm not mistaken, the work required for each password guess is two iterations of SHA, and then raising a single large exponent, and computing a single large modulo-division. This is not comparable to pbkdf2, bcrypt, scrypt, or similar, and probably shouldn't be considered a strong enough rate-limiter to protect a low entropy password.

From the Security Considerations -section of the RFC:

  Even
     if the host's password database were publicly revealed, the attacker
     would still need an expensive dictionary search to obtain any
     passwords. The exponential computation required to validate a guess
     in this case is much more time-consuming than the hash currently used
     by most UNIX systems. Hosts are still advised, though, to try their
     best to keep their password files secure.

So not much security is claimed in the case of password compromise. A dictionary search is possible, just deemed expensive, which it arguably was back then.

The "hash currently used" presumably means DES-crypt (bcrypt was new and as yet rare), which uses 25 iterations of slightly modified DES with only 56 bits of the password used. You can see how even two iterations of SHA-1 followed by a modular exponentiation could be better.


is PBKDF2 reversible? Given an AES key that is wrapped using another AES key, the second one being generated using PBKDF2, and given that I know the wrapped key: can I derive the passphrase that went into the PBKDF2? (asking for a friend)

PBKDF2 is not reversible using any semi-safe underlying hash function, including for instance SHA1 or even MD5.


Possible SHA-256 implementation weakness I came across a SHA-256 implementation that seems not to conform to the standard and because I can't change the implementation I would like to know if it's safe for use or can be a potential weakness.

For the last 32 byte block instead of performing this: (As copied from wikipedia)

Add the compressed chunk to the current hash value:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h

It overwrites the current hash value:

h0 := a
h1 := b
h2 := c
h3 := d
h4 := e
h5 := f
h6 := g
h7 := h

Aside from this difference, the implementation in question is equivalent to the pseudo code in wikipedia. It does not produce equivalent output to a correct implementation of SHA-256.

Quoting zaph from the comments:

  If the implementation does not produce the correct results it is a failed implementation, don't use and report it.

This is pretty much the correct course of action, assuming that the algorithm is supposed to be SHA-256.

Cryptanalysis of the incorrectly implemented algorithm would be non-productive, unless your goal is to maliciously exploit the protocol that is using this hash function.

Alternatively

It is possible that the author was attempting to be clever or obscure and made such a modification intentionally. There may not be much you will be able to do to help the situation if that is the case; Even if you present collisions/preimages, you may simply garner hostility from the author/users (see the drama around IOTA for an example).