Knowing pre-encryption data, can we find the private key CryptoWall used?

According to the Dell SecureWorks link from the comments, CryptoWall used/uses RSA encryption directly on the files:

  File encryption begins after CryptoWall successfully retrieves the RSA public key from an active C2 server. Therefore, using network-based controls to block this communication can prevent compromised systems from becoming encrypted. Unlike CryptoLocker's use of a symmetric cipher, such as AES, to encrypt bulk data, CryptoWall uses the RSA public key to directly encrypt files. Because the RSA algorithm is far more computationally intensive than symmetric ciphers, compromised systems experience significant CPU load after CryptoWall compromises as files are encrypted.

This alone could allow some data to be decrypted due to weaknesses of textbook RSA if it is naively blocking files and using raw RSA. For example, anything that can be guessed could be verified, and the last blocks of files could be small enough to be brute forced. It would not help in finding the private key, however.

Additionally:

  CryptoWall variants deployed before April 1, 2014 contained a weakness in the cryptographic implementation that allowed recovery of the key used to encrypt files.

According to Symantec the private key was present on the infected computer and sent to the command server:

  The Trojan then sends the private key back to the remote server. After the remote server confirms that it has received the key, the Trojan will send a screenshot of the computer’s desktop to the remote server.

More newly infected users would seem to be out of luck (from first link):

  This flaw appears to have been corrected in later versions of the malware. CTU researchers have not performed a rigorous assessment of CryptoWall's cryptographic implementation, but they have not discovered any obvious flaws that allow decryption without payment.


Why does TWINKLE use light instead of current?

TWINKLE  uses LEDs as their output is easy to sum.  Simply put, the overall light level measured by a photo detector in the top of the tube is the (rough - important) sum of the individual LED emissions. I say important as the overall sum does not have to be accurate. It only has to exceed a threshold level when TWINKLE notifies the controlling PC of the current integer. This ambiguity mitigates   the practical issues of light travel distances /times, variations in individual LED emission levels and geometric imperfections of the photo detector's lens.

It's really quite clever.  This guy's going to do well for himself.  You can add up the output of the device's 100,000 processing cells with a single detector that has clear sight of all of the emitters. The innovation here is that each cell can operate totally independently and an overall 100,000 input   adder is not required.  It also allows the outputs in the form of light to be send at 10GHz, whereas that's getting ridiculously fast for circa 1999 technology distributed across a 6" wafer.

Your suggestion of adding the currents /measuring the total resistance  would require something like this arrangement:-

A long chain of 100,000 resistors would have to run between all of the computation cells. To make the maths easy for a sanity check, assume that the wafer is actually square with a grid of 316 x 316 cells. That makes the resistor chain approximately 42m long.  The reasons  that this can't possibly work are entirely off topic for this site, so here they are:-

You cannot guarantee that any circuit produced on a wafer is viable. In 1999 manufacturers would have been using a ~200nm lithographic process to make this stuff.  Adi himself suggests a device yield of 80%.  That means it's highly improbable that the resistor chain would be intact without any break or significant thinning. Surprisingly, the yield rate is dropping as technology improves(?) and may be down to 30% today.
It's impossible to measure resistance. You can only detect a voltage or voltage driven current. And any changes in current or voltage have consequences especially if the rate of change is fast.
Contrary to what people think, unfortunately there is no such thing as digital electronics.  There is only fast analogue electronics. The implication of this is that electricity can't even travel at light speed, and can be considerably slower (50%c - 80%c). The resistor chain couldn't be longer than ~5mm for transmission line effects to start clobbering the signal at 10GHz.
The same pesky transmission line effects make it impossible to synchronise all the cells to within 10ps - 20ps that Adi requires. Hence the light sensor on each cell.

It's worth noting that TWINKLE's successor, TWIRL, does not use opto summation techniques.  This may be an indication of the designer's lack of confidence in the benefits of optical /analogue methods for modern computing


Are there any online, single pass, AE with associated data auth?

The comparison table is old. OCB has been updated twice since it was first published, supporting associated data since the Asiacrypt 2004 paper. The latest version is OCB3 (but Rogaway suggests it should be called OCB) from a FSE 2011 paper. See http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm#versions

In summary, OCB (versions OCB2 and later) supports AEAD and has supported it since 2004.


No.  The attacker cannot easily recover the secret key.  The attacker cannot modify the ciphertext to something that decrypts to some other plaintext.  This remains true even if the attacker can encrypt an arbitrary number of chosen plaintexts.

This is known as "IND-CCA2 security" (security against adaptive chosen plaintext/ciphertext attack).  CCM satisfies that notion of security.  So too do other authenticated encryption schemes, like EAX, GCM, etc.


Relationship between the use of a mask and entropy

A uniform random source has maximum entropy: 1 bit per bit. It's fully unpredictable.

There's no way to measure the entropy of a source since you can only get a partial, finite view of it. If you see no pattern in the first $n$ bits, that doesn't prove that the source doesn't repeat every $n$ bits. Conversely, an ideal random source can return $n$ identical bits, it's just very unlikely (probability $2^{-n}$). So when you estimate the entropy of a uniform random source by sampling it, you can expect to get an entropy measure of about 1 bit per bit, whereas a non-random source usually has less (but only if your entropy estimation manages to catch the non-randomness).

You're getting 1 bit/bit and 7.79 ≈ 8 bit/byte (clearly not 7.79 byte/byte: it's a number between 0 and 1) as the entropy estimate for source 1 which is supposed to be uniformly random. This is within expected bounds.

You're getting 0.95 bit/bit and 0.81 bit/byte for source 2. This indicates that source 2 has pretty much equal numbers of 0's and 1's, but there's a very strong correlation between successive bits since grouping bytes together gives a low entropy estimate.

When you apply a uniformly random mask, the resulting combination becomes itself random. This is because every bit has a .5 chance of being flipped, so each 0 bit in the source has equal chances of being 0 or 1 in the combination, and each 1 bit in the source also has equal chances of being 0 or 1 in the combination. The entropy estimates that you get for source 1 with the random mask and for source 2 with the random mask are close to 1 bit/bit as expected.

Note that the mask is a xor, not an and. A bitwise and with a uniform random source would merely reduce the entropy by forcing about half the bits to 0.

This observation that an unpredictable mask xored with an arbitrary source results in an unpredictable combination is the basis of stream ciphers.


Is bcrypt better than GnuPG's iterated+salted hashing method?

OpenPGP's "Iterated and Salted S2K" is just a single hash instance over a very long input, which consists in the repeated concatenation of the salt and the password. This is extremely GPU-friendly, especially when using a hash function which is built over 32-bit elementary operations (this category includes MD5, SHA-1, SHA-256 and RIPEMD-160; GPU are not as good at dealing with 64-bit operations, e.g. SHA-512). Consequently, an attacker will get a good boost out of GPU when trying to attack a password which has been processed with that key derivation function.

Note that this puts S2K in the same category than PBKDF2: although their internal structures differ quite a lot, they have similar usage patterns on the hardware. Comparatively, bcrypt and scrypt need much more fast access RAM, which puts GPU at a disadvantage. Bcrypt still fits in a few kilobytes of RAM, hence is still susceptible to optimizations through FPGA; scrypt looks even better, but it is shiny because it is new, which is not a good thing in cryptosystems (like good wine, good crypto must wait a few years for optimal quality; see this answer for a more thorough discussion).

Let me stress out that, in practical terms, OpenPGP's S2K (or, for that matter, PBKDF2) very rarely turns out to be the weakest part of a given system. For all its shortcomings, S2K is much better than a simple non iterated hash-with-salt, and a fortiori an unsalted hash invocation, as is unfortunately still commonly encountered in deployed applications.


Why is encrypting a key under itself dangerous?

Let $E$ be your cipher.
Consider the following cipher:
$$E_{k}'(m) = \begin{cases}
k & m =k\\
E_k(m) & \text{else}
\end{cases}$$
I believe you should be able to reduce the security of $E'$ to the security of $E$ in a rather straightforward manner.

This is a fairly important notion in general though.
The notion of "being secure, even if one gets encryptions of functions of the secret key" is known as Key Dependent Messaging security in general.
It's a property that (among other things) so far we seem to require to build FHE, but cannot prove that particular FHE schemes have it (instead we generally make the "Circular Security assumption").

Matthew Green has a blog post on it if you want a slightly higher level viewpoint on the topic.


Are collisions possible on the output of Blowfish?

No, you cannot, unless you have repeated messages, or use different keys. A block cipher such as Blowfish is a keyed random permutation or bijective mapping.

That means for each key any plaintext block is mapped to exactly one ciphertext block during encryption, and the ciphertext block is mapped to that particular plaintext block during decryption.

For different keys there are different mappings. So if you mix keys you may get a collision.


Is it possible to determine public key if you know private key?

Since you tagged the question with "rsa": Yes, with rsa it would be very easy to determine the public key (n) from the private key (p & q), because n = p * q.


You are correct. The $Update$ function is called after each invocation of the $Generate$ function, and this does mean that chunking affects the output. Changing both the key and the nonce of an $AES-CTR$ key stream generator to uniformly selected (pseudo) random values will, of course, make the resulting key stream uniformly independent from what it would have otherwise been.

However, it might be noted that the first $8$ bits of $Generate(state, 12)$ equals the full $8$ bits of $Generate(state, 8)$.

It should be noted that a $DRBG$ is primarily to be used as a replacement for a $TRBG$ (true random bit generator). It is not designed to be used as a stream cipher (which must support chunking) or as a key derivation function (which might support chunking). In particular, the NIST SP 800-90A specification explicitly forbids instantiating a $DRBG$ with the same state twice, which by itself makes it impossible to use it as a stream cipher or key derivation function.


How to change the master password in a password manager

In the context of most Password Managers that use encryption, you will generate a Master Data Encryption Key (MDEK) which will serve to encrypt all the passwords and the user's password would be the Key Encrypting Key (KEK) to encrypt the MDEK. This way, the MDEK stays the same when you change your Master Password derived KEK that wraps the MDEK.


Xor is the "addition" operator for algebra with boolean operators, while AND is the "multiplication" operator for boolean operators. "Regular" addition and multiplication are the addition/multiplication operators for integers. So speaking of "linearity" in the sense of algebraic compatibility, XOR and integer addition are non-linear. I feel like this question/answer(s) sums it up pretty well.

As for why xor is required/why AR is not sufficient, technically, AR is equivalent to ARX, but less efficient. See the paper Rotational Cryptanalysis of ARX . There are some details to it:

  We also show that the
  AR systems
  , that do not use XOR, are theoretically
  equivalent to ARX systems. However, we prove that they are less secure with
  the same number of operations, because of the linear mod 2**n approximation.
  It is also easy to prove that omitting addition or rotation is devastating, and
  such systems (XR and AX) can always be broken.


The Vigenère cipher has many weaknesses, but perhaps the most obvious ones are:

An attacker, who knows (or can guess) as many consecutive characters of any plaintext message as there are in the key, can trivially recover the key and thus decrypt all messages.  (In fact, the characters need not even be consecutive, they just need to cover the entire key, or at least most of it.)
For most natural messages, it's fairly easy to guess the key length, for example by looking at correlations between characters $n$ positions apart.
An attacker who knows (or can guess) the key length can divide the ciphertext into blocks of this length and decrypt one block with the other as the key to obtain a linear combination of the two messages.  This will often have enough structure to allow the original blocks to be (at least partially) reconstructed, which in turn allows recovery of the key.  (Also, if there are multiple messages encrypted with the same key, or if the key itself is not completely random, other similar attacks may be possible even without guessing the key length.)

In short, I would strongly recommend not using the Vigenère cipher for any purpose, except perhaps for puzzles that are meant to be broken.  At the very least, use a stream cipher like RC4, which is simple enough to implement off the top of your head.  Also, if you need to encrypt multiple files, include a unique initialization vector with each (or derive one from some unique value, like the name of the file) and hash it together with your master key.

(Using a stream cipher in such a way that they output remains valid Unicode text is a somewhat non-trivial exercise in format-preserving encryption, but it should be no harder than doing the same with a Vigenère cipher.  Personally, I'd suggest encrypting the input as a binary octet stream and then Base64-encoding it into printable ASCII as the simplest secure method.)


Give a simple hash chain example in Java

I'm not a Java programmer, and I didn't compile this, but I modified answer to this question to achieve a hash chain of length equal to four.

byte[] bytesOfMessage = yourString.getBytes("UTF-8");

MessageDigest md = MessageDigest.getInstance("MD5");

byte[] thedigest = md.digest(md.digest(md.digest(md.digest(bytesOfMessage))));

PS. Don't use MD5 for crypto. It's not secure.


Are there MD5 collisions for inputs of different length?

So the problem with different-size MD5 collisions is that our collision-finding tools aren't yet powerful enough to find them efficiently.

First we need to understand the rough idea of how MD5 works, using the Merkle–Damgård construction where essentially you keep some state $s$ and some current input block $m$, combine them with a compression-function and use the output as new state $s$, with the last state effectively being the output.

Now what our current techniques can achieve is that given (arbitrary) states $s_1\neq s_2$, they can find a sequence of message blocks $(m_1,m_1',\ldots)$ and $(m_2,m_2',\ldots)$ that when fed into the hash function will yield the updated states to be the same $s_1'=s_2'$ (this is called a "chosen-prefix collision attack").

The problem is, that after $s_1',s_2'$ the messages need to be equal (including length) to preserve the collision or you'll have to re-unite the states again if you feed different messages again. This is a problem because MD5 appends the length of the processed message to the message just before feeding of to the final compression function call. In particular that means that when you use different-length messages your last blocks will differ and as it is the last block you can't just feed message blocks to make up for this difference again.

In theory you could try to defy this problem by either finding a collision on the compression function that involves this little control on the last few bytes, but practically it appears nobody has done this (yet).

However, if you are looking for a brute-force collision, which would entail about $2^{64}$ expected work and $2^{128}+1$ worst-case work, you can just have a 128-bit counter $\mathbb i$ and continually hash $\mathbb i$ and $\mathbb i\|\mathbb i$, looking for hashes which appear in both sets. Any such entry, which is guaranteed to exist after $\mathbb i$ cycled through its whole range will be a different-length collision.


Top 10-2017 A8-Insecure Deserialization , why products does not implement encryption

Why are products not encrypting the serialized data as discussed in [#30723]?

Because encryption by itself does not reliably prevent alteration of the data, which is the vulnerability here. As Maarten Bodewes comments in that very Q.

To prevent tampering in general you need -- as OWASP says -- an integrity check, like a MAC or signature. Not encryption. (Although if you have authenticated encryption, which does both encryption and MAC as a combined operation, and in recent years has become more popular and widely available, you might as well use it.)

Now, why don't/didn't people use a MAC or signature (or AE) on data which if altered can be dangerous? That's a good question. To which I don't have a good answer.


No, I think a general understanding of what a cipher, hash, signature, MAC and a few other of these concepts will make it much easier to understand what cryptography is about.

It's like some knowledge about cars can be very helpful, even if you don't get to be a mechanic. Especially understanding a bit about certificates and PKI is pretty useful, as it is the underlying authentication structure for the internet (especially TLS and therefore HTTPS).

We may be a bit biased here. You can get by pretty well without knowing cryptography. Then again, you won't need a lot of mathematics unless you presume you're going to build cryptographic algorithms or perform cryptographic analysis.


How to compute negative point in EC-DSA?

Your second point is the correct interpretation.

Due to the negation map automorphism on (Weierstrass form) Elliptic Curves we have for all affine points that if $P = (x,y)$ belongs to the curve then also $-P = (x,-y)$ belongs to the curve.

This is due the curve's symmetry with the respect to the $x$ axis, as you said.

You can view it as $-k \cdot G = k \cdot (-G)$ but you can also see it as $k\cdot G$ and $-k\cdot G$ are symmetric with respect to the $x$ axis just like $G$ and $-G$.
In fact, how would think of the negation of $(k\cdot G)$ if not with $-(k\cdot G)=(-k)\cdot G$ ?

Now the two point differs. But in the ECDSA verification only the x coordinate is checked, and this will be the same for $k\cdot G$ and $-k\cdot G$


Why the output length of a KDF should be the same as the underlying OWF?

It would be a benefit for badly defined PBKDF's such as PBKDF2. PBKDF2 re-iterates all the iterations if you ask more than the output of the one-way function. This requires the server to perform additional calculations. The attacker however might be able to validate that a guessed password is correct without going through the same number of iterations.

This would for instance be the case if you split the output into a 256 bit key and 128 bit IV when using PBKDF2 - SHA-256 - in that order. The key would be calculated first, then the entire work of hashing is repeated for the IV. But an attacker would only need the first 256 bits to confirm a guess.

Some older KBKDF's and PBKDF's such as KDF1/2 and PBKDF1 also simply do not allow for outputting more than the output size of the one-way function.

Newer KDF's such as HKDF (a key based KDF or KBKDF) and Argon2 (a password based KDF or PBKDF) have been specifically designed to allow for more output than the one-way function. It should however be remembered that retrieving a 256 bit key from a function that can only provide 160 bits of security will not give you 256 bits security.

This might be the main reason for the given statement.

That the output size needs to be precisely the output size of the one-way function is, in my opinion, hogwash. It is perfectly reasonable to ask 512 bits of output and split it into two times 256 bits, while the one-way function only provides 256 bits of security. It is nicer to use two labels and perform a KBKDF twice, but that's not necessarily more secure.

Besides that, it is certainly completely valid to ask for fewer bytes than the one-way function provides.

Commonly the output size is a configuration parameter for the KDF. But you might want to consider to use the most up to date KBKDF or PBKDF if you ask for more bits than the one-way function provides. As long as you don't fool yourself with regards to the key strength provided by the KDF, you should be perfectly safe (at least in theory: specification / implementation failures and catastrophic breaks of KDF's are not covered by this insurance).


How to ask for an Identity confirmation without revealing

There are two ways that I see.

First, Oblivious Transfer allows a requester to retrieve relevant information (and only relevant information) from the sender without the requester revealing which piece of information they're after.  This would allow the Bob to obtain the key that Alice has for Ted, without Alice knowing that Bob is interested in Ted's key.  Depending on the scenario, this could be a vulnerability in the case that Bob has the wrong key -- this protocol would allow him to obtain the correct one from Alice.

Second, Secure Computation allows Bob to obtain the value of $f(x,y)$ where $x$ is only known to Bob and $y$ only known to Alice (and $f$ is mutually known).  Let's say that Bob knows that Ted's key is stored at position $i$ of Alice's contact list.  Then we could have $y=$Alice's contacts, $x=(i,t)$ where $t$ is they key Bob has for Ted.  Then $f(x,y)=[[y[i] == t]]$.


Can the CRT speed-up Paillier decryption by more than a factor of two?

Since CRT is an isomorphism computing $m_p=m\bmod q$ and $m_q=m\bmod q$ directly is possible. To see this in the formulas above replace the $\bmod n$ step with $p$ and $q$.

To the question, I don't know if working in $\mathbb{Z}_{p^2}^{*}$ and $\mathbb{Z}_{q^2}^{*}$ could let you compute $m_p$ and $m_q$ more quickly than simply doing the steps modulo the prime factors of $n$. One thing that could help is to reduce $\lambda$ by the order of $\mathbb{Z}_{p^2}^{*}$ (or $q^2$ respectively). The order is given by the Euler totient function of $p^2$ which is $\phi(p^2) = p(p-1)$. This helps when $p$ or $q$ is small but in general doesn't speed things up.

The only other comment I can make is the improvement you want would need to exploit some property of the group of elements of the form $x=c^\lambda\bmod n^2$ under multiplication. This is the group of elements of order dividing $n$. Its two nontrivial subgroups are the elements of order dividing $p$ and $q$.


If we assume that Alice is the one sending the photons, and Bob is the one receiving them, then Bob selects random bases to take the measurements, and then announces them (both to Alice and any potential attacker) after he has taken those measurements. An attacker cannot use that announcement to decide how to take measurements himself, as he doesn't hear it until after the photons have passed.

Now, if the attacker could replace Bob's announcement about the measurements with his own, he could break the system - this would be a simple MITM attack, where Alice communicates to the attacker, and the attacker communicates with Bob.  However, authenticating this communication isn't difficult; it can be done using a universal hash, initially (for the first exchange) a key that was installed in both systems, and for later exchanges, bits that were exchanged during the previous exchange.


why IPSec transport mode is restricted for host-to-host communication , or host-to-gateway where gateway acts as a host only?

That's because IPsec transport mode reuses the same IP header as both the 'outer header' (that is, the IP header that appears in front on the encrypted IPsec packet), and the 'inner header' (that is, the IP header that's the plaintext packet).

Suppose Alice wants to send an encrypted packet to Bob (who may be a security gateway); that packet must have an IP header with Bob's IP address as the destination (because, if it doesn't, the network won't forward the packet to Bob).  Then, Bob decrypts the packet; if he (and Alice) were using transport mode, he retains the IP header.  Hence, the decrypted packet will still have Bob's address as the destination.  Then, if Bob is a security gateway, who does he forward the decrypted packet to?  Well, the packet says that Bob is the destination, and so Bob it is (and even if Bob decides to ignore that rule, he doesn't have any idea who the real destination ought to be).

Now, actually, this isn't entirely true; there is a workaround.  I have seen cases where Alice and Bob use a tunneling protocol between the two.  In that case, you really can use IPsec transport mode.  What Bob will do is, once he decrypts the packet, removes the tunneling header, which may expose the real plaintext IP header.  Then, Bob knows who to forward the decrypted (and detunneled) packet to.  This works; IMHO, this really is only a slight variation on tunnel mode, however apparently it does have some sort of advantage in some cases...


Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives?

Yes, at least for a definition of "based on a particular mathematical problem" allowing the problem to be breaking the generator!

Restricting to constructions that can be efficiently implemented, one of the simplest conjecturally Cryptographically Secure Pseudo Random Number Generator in the literature is the Alternating Step Generator, proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. Its best known cryptanalysys is by Shahram Khazaei, Simon Fischer, and Willi Meier: Reduced Complexity Attacks on the Alternating Step Generator, in proceedings of SAC 2007

The ASG consists of three Linear Feeedback Shift Registers, which have a well known reduction to arithmetic in $GF(2^k)$. To produce a bit:

advance LFSR2
according to it's low-order bit, advance LFSR0 or LFSR1
output the XOR of the low order bits of LFSR0 and LFSR1

To choose the (public) LFSR parameters, select the desired security parameter $n$. Then pick three binary primitive polynomials of degree $n_0$, $n_1$, $n_2$ with $\alpha\,n<n_0<n_1<n_2$ so that $2^{n_0}-1$, $2^{n_1}-1$, $2^{n_2}-1$ are pairwise coprime. The best known attacks are for $\alpha=\frac32$, but $\alpha=2$ is more reasonable.
Note: in the initial exposition, LFSR2 is modified to generate a de Bruijn sequence, that is the output sequence has an extra zero inserted after $n_2−1$ consecutive zeroes. But this detail makes no cryptanalytic difference, since that point in the sequence is reached with negligible probability for $n_2$ large enough to thwarts attacks guessing the state of a single LFSR.

Per comment: Checking if two integers are pairwise coprime does not require "testing primality of any number". It can be done with Euclid's algorithm (or others that efficiently compute the Greatest Common Divisor), and checking that the GCD is 1. Also, parameter choice is performed just once, then we can have multiple instances of the generator using these parameters and different keys.

Example, with the help of the compact table of primitive binary trinomials compiled by Jörg Arndt (and a caveat: I have no clear-cut argument that using trinomials leaves the ASG secure): $n=192$, $n_0=385$, $n_1=386$, $n_2=393$ and

LFSR0: $x^{385}+x^{142}+1$
LFSR1: $x^{386}+x^{83}+1$
LFSR2: $x^{393}+x^{91}+1$
$n_0$ and $n_1$ are minimal given the choice $n=192$ and $\alpha=2$. $n_2\in\{387, 388, 389, 392\}$ was not used due to absence of trinomials. $n_2=390$ was not used because $\gcd(2^{386}-1,2^{390}-1)=3\ne1$. $n_2=391$ was not used so that the center terms (otherwise minimal) are farther than 64-bit from each side (in hope to ease constant-time software implementation).

The key is the initial state of the three LFSRs (with say the high-order bit of each LFSR set to the complement of the XOR of the others in order to ensure non degenerate states). This is an inconveniently long key, of $n_0+n_1+n_2-3>3\,\alpha\,n$ bits, and the security conjecture is for uniformly random independent key bits.

Some formal definitions of a CSPRNG (and practical robustness) require it's key to be of size equal to the security parameter. If that's wanted, coming up with a safe initialization procedure starting from a key of $n$ bits is non-trivial: we need some auxiliary CSPRNG to expand from $n$ to $n_0+n_1+n_2-3$ bits (from 192 to 1159 in the above example).


How does hill cipher key exchange takes place?

In the Hill cipher, like in any symmetric cipher, it is assumed that both parties have the same secret key already.

Securely exchanging a key is not part of the symmetric algorithm, neither is it its job. That a separate protocol that needs to be done beforehand.


Is this scheme a provably fair random number generation?

Yes, your scheme is fine.

Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$).  Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).

This problem is known as secure coin flipping, and it has been studied in great depth before.  For solutions and analysis, look at the following questions on this site:

How to fairly select a random number for a game without trusting a third party?
https://crypto.stackexchange.com/a/465/351
Proof that lottery does not know outcome of draw
A fair peer-based coin-flipping protocol?


Possible to identify cryptographic keys in non-random binary data?

I think that the problem with your sneaky technique is in the first sentence - "a well-generated cryptographic key would be indistinguishable from randomly generated binary data"  That's absolutely true, and I'm extremely confident that 625,000 well generated unique keys concatenated together will form sufficient data for a Diehard test.  And that data sample would pass, probably with flying colours and no dodgy ps.

However you're only trying to find a single key that's perhaps only 128 bits of data.  That's 16 bytes.  16 random bytes can be anything ('cause it's random).  They could be 101010... or any other non random looking sequence.  That's the pesky nature of true randomness.  Who would have thought that 999999 is totally random, yet it famously is and clearly exhibits very low entropy.  This will easily be lost in all the different micro variations of entropy that constitute a computer application.

This is further camouflaged by things like compressed data structures.  Almost all parts of a JPEG are totally random as a result of lossless Huffman coding.  This might resemble an AES key, and readable high level disassembly is extremely difficult.

The only approach I can find is the brute force extraction technique.  Knowing that your thing is AES encrypted, I'd scan though the application from beginning to end, extracting every consecutive and overlapping 16 bytes.  They run them through the decoder to see if your thing decodes to something understandable.

Now since a complete dummkopf like me thought of this, clever application developers /cryptographers though of it too.  It would be very simple to obfuscate the raw AES key somehow.  Simply XOR it beforehand with another array or distribute the individual bytes randomly throughout the entire memory map.  You could even encrypt the encryption key with another algorithm.  This might be one of the few perfectly valid examples of rolling your own crypto to create security through obscurity.  I'm sure that there are even more complex obfuscation techniques in use - no body wants you to play Halo for free after all.


What does "running in polynomial time" really mean?

Perfect secrecy is achievable in a few cases, such as one-time pads, and, well, that's pretty much it. Most cryptographic protocols are vulnerable to an all-powerful, all-knowing attacker. If you do not put any restriction on what the attacker can do, then

Guess the key.
Profit.

breaks almost any cryptography, as does

Wave a magic wand.
Profit.

So at the very least we must restrict our model attackers who can do things we haven't even imagined. Cryptography also doesn't aim to protect against lead pipe cryptanalysis. So we assume that attackers are only allowed to do things “inside the system”. Based on Turing's thesis, we assume that the attacker can only compute computable functions, and that the function computed by the attacker does not depend on the key. (It's ok if the attacker can make random choices too, as long as their probability isn't influenced by the key.)

Even a deterministic attacker who does not know the key can still break most cryptographic protocols with enough effort. All he has to do after all is enumerate all possible keys. But for sufficiently large key sizes, this should be unrealistic: as a rule we aren't interested in attacks that would take more than the lifetime of the universe.

If you want to analyse the resistance of an algorithm very precisely, you would need to know exactly how powerful the attacker's computer is, and study all possible ways in which he can make the computation required by the attack to find which one is the fastest (or more generally the cheapest). This is impractical. To start with, we look at the asymptotic behavior of the attacks: the way the attacks become harder as the parameters (such as key size) become larger.

In computational complexity, there is a nice break between polynomial and super-polynomial algorithms. This break fits cryptography well. The usual methods of doing realistic stuff tend to be polynomial, whereas enumerating all keys is exponential in the size of the key (or more precisely in the strength of the key). So restricting to polynomial attackers combines two nice properties:

It is good for getting theoretical results.
It does a good job of including realistic attackers and excluding unrealistic ones.


How can I use SSL/TLS with Perfect Forward Secrecy?

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using.

This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, certificates have not entered the picture at all. This is because whether or not a connection has perfect forward secrecy is determined by how the session key is derived. And how the session key is derived is determined by the ciphersuite in use. So, the ciphersuites that use ephemeral Diffie-Hellman (DHE) or the elliptic-curve variant (ECDHE) will have perfect forward secrecy while the other options will not.

Thus, in order to configure PFS for your site, what you want to configure is your web server's ciphersuite-selecting options. More on this below.

  Can my choice of certificate authority hinder the use of Perfect
  Forward Secrecy?

No. Perfect forward secrecy protects against the revelation of master keys. CAs do not have access to private (master) keys; a certificate from a CA is a signed public key. The CA is there to say "okay, client, I have verified that the public key here is indeed associated with <host>, it's safe." (Or, rather, the fact that it's signed by the CA says this.) Thus, your choice of CA will not impact PFS in any way.

  How can I create the strongest certificate using ONLY Perfect Forward
  Secrecy (meaning if the browser can't use PFS, it won't load
  anything)?

As you can see, certificates are unconnected with the choice of ciphersuite (and hence PFS).

Instead, the web server you use probably has a ciphersuite configuration in its SSL configuration. There are usually two relevant options: first, the ciphersuites that you want your server to use, and second, how the server picks the ciphersuite. Here is the relevant section in my nginx configuration:

ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_ciphers ECDHE-RSA-AES128-GCM-SHA256:ECDHE-RSA-RC4-SHA:ECDHE-RSA-AES128-SHA:RC4:HIGH:!MD5:!aNULL:!EDH;
ssl_prefer_server_ciphers on;

The first line tells nginx to use those four protocols, as is apparent. The third line tells nginx to prefer its own ciphersuites over the client's. The point here is that we want to control exactly which ciphersuite will be selected. A client may send an ordering that suggests a non-PFS ciphersuite; hence, we trust the server.

The second line is where the magic happens. Note that I manually specify that I want those three ECDHE-* schemes first if they are supported by the client. From there, I fall back to the usual schemes. I feel the need to emphasize that I don't disallow clients that don't support PFS; some encryption is better than no encryption at all. Not all clients do support PFS, so this is pretty important. I realize your question said you want only PFS ciphersuites, but I would advise against that. With the above nginx configuration, the vast majority of connections' selected ciphersuites will have PFS. The configuration for Apache is apparently quite similar, which is not surprising given that both use OpenSSL.

To that end, a useful tool: the SSL Labs SSL Test. It gives you a basic grade on your SSL configuration. See, for example, Google's grade (click on one). It has a little green box under the grade informing you that the site supports PFS for all its tested browsers, and if you scroll down to 'Configuration', you will see a ciphersuite priority list, including which ciphersuites have PFS, as well as "simulated handshake" for the common browsers of the day.


Difference between MPC and outsourced computation

About outsourced computing: under a security viewpoint, there is no challenge in trusting a thirty party and give him all responsibility on doing the task in secrecy and return the output the the parties. Trust a central party is all everyone doesn't want. So security isn't a problem when you trust someone.

Secure multi-party computation: in the most classical view, with secure MPC we have n parties entering their correspondent inputs (in secrecy), and get their correspondent output(s) (when it is the case) (in secrecy). The challenge here is the inexistence of a trusted party, and all we want is that a protocol makes the role of that trusted party, giving the guarantees that trusted party could provide.

For example, we can consider some security level of a digital version of an election: think about some computer that we can trust, in a hypothetical idealized world, realizing the election function. Your challenge is: how can you construct a (distributed) protocol that runs among the parties, and that gives all the security guarantees that trusted computer could provide to the electors.


How Diffie-Hellman authentication works?

Diffie-Hellman comes in two basic forms - static and ephemeral - and a number of combinations of those.

Ephemeral Diffie-Hellman means that both parties of a key agreement generate new - ephemeral - key pairs and send their respective ephemeral public key to the other party. If both parties generate ephemeral key pairs each time, you get Perfect Forward Secrecy. This type of key agreement is usually used in conjunction with signature algorithms (RSA, DSA, ECDSA) to authenticate the ephemeral public keys of one or both parties. When Ephemeral Diffie-Hellman is used plainly, without a supplemental signature algorithm, it is anonymous, unauthenticated and susceptible to MITM attacks.
Static Diffie-Hellman means that both parties of a key agreement use long term - static - key pairs. This form of Diffie-Hellman becomes authenticated exactly when at least one party is able to link the other party to the static key that is used. Typically, this is done either by that party having advance knowledge of the Static Diffie-Hellman public key of the other party, or by both parties belonging to some form of Public Key Infrastructure, in which a trusted third party connects the identity of the peer to its public key.

Hence, regarding your questions:

The purpose of Diffie-Hellman is to agree on a shared secret. This is perfectly possible with long term static keys. The public keys will still have to be exchanged somehow, but it might be done ahead of time, through authenticated channels.
Static Diffie-Hellman public keys would typically be exchanged through a Public Key Infrastructure. Having two parties directly exchanging static public keys to use with Static Diffie-Hellman, would indeed not necessarily be better or more practical than them generating a shared secret directly, and storing that shared secret instead of the public key of the other party.
The purpose of authentication is typically to tie an online presence to some form of identity that makes some form of sense to the other party. Typically, you want a method of authentication that identifies the other party in the way that makes most sense given the circumstances. Theoretically, if the parties have no advance knowledge of each other, and will not assign any other identity to each other beyond the initial online presence, they could use the public keys from the initial anonymous key exchange for authentication. Normally, authentication would however be accomplished either by exchanging public keys in advance, or by means of a public key infrastructure.


How to apply lagrange interpolation on bilinear pairings?

Are you asking how we come up with the $l_i$ values?" Most probably yes

How we find these values is pretty much standard Shamir Secret Sharing, and has nothing directly to do with the pairing we'll do later.

To do a quick review, in Shamir Secret Sharing, we pick a finite field, and a $t$ degree polynomial $P$ (whose constant term is the secret we'll share, and the rest of the terms are random [1].  We generate shares by assigning each share a nonzero index $i_j$ (which can be public), and the value $y_j = P( i_j)$, that is, the polynomial evaluated at the index.

Now, if we know $t+1$ shares, we know enough to reconstruct the polynomial (and thus the constant term, which is the secret); the standard way to do this is to not bother computing the entire polynomial, but instead just compute the values:

$$l_j = \frac{\prod_{k=1,...,t+1, k \ne i}-i_k}{\prod_{k=1,...,t+1, k \ne i}i_j-i_k}$$

And, this we can reconstruct the secret as:

$$s = \sum_{i=1}^{t+1} l_j y_j $$

If you go through the math, you'll find that this value $s$ is precisely the constant term of the polynomial $P$.

The $l_j$ values are precisely what you are asking about.

Now, the standard Shamir method has the secret (and the coefficients of the polynomial) being elements of the finite field; what this paper does is tweak things a bit by making the secret, the rest of the coefficients and the secret $y_j$ values being elliptic curve points (one way of thinking of it is that, instead of having the secret being a value $s$, it is actually the point $sG$).  They then have the finite field that the $i_j$ values work in being $GF(q)$, where $q$ is the prime order of the curve.  Because the above algorithm never needs to multiply two different $y_j$ values, this all works out.

[1]: Note: we allow the high order term of the polynomial to be 0.  Standard terminology would state this would be a $t-1$ or lower degree polynomial; however, we need to allow this case to provide for the informational security that Shamir provides.


What is the significance of i^Q mod P = 1 and are there any special properties to be aware of?

A special case of the relation you've found is called Fermat's little theorem.
In a more "mathy" way this looks like:

$i^Q\equiv 1 \pmod p$

which will always hold for $Q=p-1$ and for any $Q|p-1$.

The use of this theorem is limited in cryptography, however the problem of determining $Q$, if only $i$ and $p$ are known, this problem is called "discrete logarithm problem" (assuming there isn't a "1" on the right side but rather some random number).

If $p=r*s$ and you're given $Q$ then this is called the RSA-problem (the problem if finding the Q-th root modulo p), again assuming the right side isn't 1 but rather some random number.


Benefit of combining classical substitution ciphers with modern cryptography

The fact that a given cipher has a key length of 296 bits doesn't mean at all that it provides 296 bits of security or even that a brute force attack would take $2^{296}$ steps. The problem of mono-alphabetic substitution cipher is the ridiculously small block size (in this case, barely $\log 64 = 6$ bits).

If absolutely nothing about the plaintext is known, every cipher is unbreakable, as there's no way of knowing if you got the right result.

In practice, you always know something about the plaintext. If that's not enough to launch a known-plaintext attack, your method might add some security form a theoretical point of view, but it's rather pointless in practice, since brute-forcing a 256-bit key is just as feasible as brute-forcing a 552-bit key.

However, if you do know enough plaintext, the mono-alphabetic substitution cipher doesn't add any security at all. After encrypting the known plaintext with an AES key, all you have to do is check if matching characters get mapped into matching characters. If they don't, discard the key; no further tests are required.


When does multiple OTP encryption become insecure if new keys are permuted?

This is an inconsequential variation on a two-time pad and falls just as readily.

Say your pad is $n$ symbols long.  Fix a permutation $\pi \in S_n$ of $\{1,2,\dots,n\}$—this is determined by your $\operatorname{permute}$ operator.  If the pad is $(p_1, p_2, \dots, p_n)$ and the $i^{\mathit{th}}$ message is $m_i = (m_{i,1}, m_{i,2}, \dots, m_{i,n})$, then the $i^{\mathit{th}}$ ciphertext $c_i = (c_{i,1}, c_{i,2}, \dots, c_{i,n})$ where $$c_{i,j} = m_{i,j} + p_{\pi^{i-1}(j)}.$$  Here $\pi^i(x) = \pi(\pi(\cdots \pi(x)\cdots))$ is the $i$-fold iteration of $\pi$, with $\pi^0(x) = x$.

So far this is just a restatement of your system, with specific names given to each symbol in the message, pad, and ciphertext.

If I learn the ciphertext $c_1$ of a single known message $m_1$, then I can trivially recover your pad by $$p_j = p_{\pi^0(j)} = c_{1,j} - m_{1,j},$$ and then decrypt the next ciphertext $c_2$ or any other by simply permuting the pad $(p_1, p_2, \dots, p_n)$ with $\pi$.

Obviously, if I don't know $m_1$ exactly but can narrow it down to a small set of options, then I can narrow down the $p_j$ to a small set of options too, and thus narrow down $m_2$, and so on.

In general, if the pad for the first message is $p$, the pad for the second message is $F(p)$, the pad for the third is $F^2(p)$, etc., where $F$ is a fixed function of pads (in this case, $F(p_1, \dots, p_n) = (p_{\pi(1)}, \dots, p_{\pi(n)})$), the stream cipher you get is completely broken.  When $F$ is a permutation with an easily computed inverse, as it is here, a known plaintext anywhere among the messages is enough to decrypt all other messages, even prior ones.

For the same reason, $\operatorname{MD5}(k) \mathbin\| \operatorname{MD5}^2(k) \mathbin\| \cdots$ makes for a terrible stream cipher even though $\operatorname{MD5}(k \mathbin\| 1) \mathbin\| \operatorname{MD5}(k \mathbin\| 2) \mathbin\| \cdots$ is basically fine.


Discrete logarithm problem - Pohlig Hellman $GF(2^p)$

A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ such polynomials $$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$

Addition is by mod 2 addition of coefficients. When you multiply two polynomials, you take the remainder of the product modulo $f(x)$.

You can use square and multiply (see here) to compute the power
$$a(x)^k=a(x)^{k_0+2 k_1+ 2^2 k_2+ \cdots+ 2^t k_t},$$
taking care to reduce modulo $f(x)$ from time to time, so the degrees of the squares don't get too large.


Yes ElGamal and RSA (without padding) are both partially homomorphic (wrt. mulitiplication). I can not think of any applications that uses the homomorphic properties of these schemes in practice. However, in terms of efficiency they are probably about equal. Evaluating the homomorphism involves just one multiplication for RSA and two for ElGamal. As for security, ElGamal is the way to go. ElGamal at least provides semantic security which unpadded RSA does not.

Wrt. FHE: the known constructions of FHE are still quite computationally heavy. However, since the first construction in 2009 a lot has happened to make FHE more efficient. At this point it is conceivable to run FHE in practice although it would be very very slow. In this paper
researches evaluated the AES circuit using FHE for example. Whether or not it would be practical to use for any given application of course heavily depends on the application.


How to find m so that RSA cipher end with '\x00'+SpesificString , if we freely input the plaintext?

I assume this is homework (I have time imagining that this is a problem that you need to solve; if it is, turn "use real RSA padding").
Since this is assumed to be homework, I'll give you the initial steps, and let you do the rest of the work.
First off, what you're asking is to find a value $m$ such that $(m^3 \bmod n) \bmod 2^{136
} = \text{"\x00"} + \text{"MySpesificString"}$; noting hat $\text{"\x00"} + \text{"MySpesificString"}$ consists of 136 bits.
Now, we are not told anything about $n$, except that it is "2048 bits", that is, it is in the range $2^{2048} > n \ge 2^{2047}$.  Now, we want a value of $m$ that would work for any $n$ in this range; we can do this if $m^3 < 2^{2047}$, and so $m^3 \bmod n = m^3$
Hence, we're looking for a value $m$ for which $m < \sqrt[3]{2^{2047}} \approx 2^{682.333}$ and for which $m^3 \equiv \text{"MySpesificString"} \pmod{2^{136}}$.
That may still sound daunting; however can we find a value $m$ that satisfies the last equations modulo $2^1$?  And, if we have a value $m$ that satisfies the last equation modulus $2^k$, can we find a value $m'$ that satisfies it modulo $2^{k+1}$?


Would reuse of the symmetric key in a hybrid cryptosystem between files be inherently insecure?

Reusing the symmetric key in a hybrid cryptosystem may or may not be safe depending on the cryptosystem. To give a simple example, suppose a system was designed to use a single-use symmetric encryption key with a cipher in CTR mode, and it is now extended in such a way that the symmetric key is now reused for several messages but still shared with the same party. (If the protocol changes to share the symmetric key with a different party each time, that obviously affects security.) If the cryptosystem uses a random initial counter value, the same key could be used more than once without affecting security. If the cryptosystem uses the initial counter value 0, that's perfectly fine with a single-use key but catastrophic if the key is reused.

Having data which is encrypted with a long-term key which is unlocked at the beginning of a session is perfectly standard. Full-disk encryption does this, for example — typically the same key is used to encrypt all the successive versions of all the blocks of the encrypted device.

The basic idea of storing a symmetric key in a smartcard and having the card deliver it to the computer (a phone in your case) when the user enters a PIN is sound. The computer should keep the key only in RAM, and your application should wipe the key after a delay. How long a delay is a compromise between UX and security and depends on the nature of the data; you have to balance user convenience with the risk of the device being stolen.

There may or may not be value in encrypting each file with a different key. Having the card do the whole encryption and decryption is probably out of the question for both performance and UX reasons (the card would have to be present during all file accesses). But having the card release only one per-file key at a time may or may not make sense. You do need per-file keys if there is ever a reason why access to different files should be subject to different rules (e.g. you might want different timeouts on different files' keys). Per-file keys also offer better protection against a limited-time compromise (e.g. a rogue app that can extract the key from your app's memory but not inject code into your app). You can have per-file keys in two ways: either there's a single master key which the card releases upon request, and the computer does the key derivations; or the master key never leaves the card and the computer asks the card to derive each file's key when that file is accessed.

Whatever algorithm you pick, make sure to use it properly, in particular with a random IV for each file (stored at the beginning of the file). Note that if a file changes, the new version of the file must use a new random IV if it's encrypted with the same key.

You should use authenticated encryption (e.g. GCM), to prevent active attacks where a rogue app on the computer tries to decrypt bad data. Note that this means that a file must be decrypted (+authenticated) as a whole; you may need to split large files. Note also that authenticating a file only proves that it's some valid version of the file; it could be an old version, or it could be valid content of a different file unless you authenticate the relationship between a file's name and its content.

As a final note, modern major mobile platforms include protected environments that can store encrypted files with some protection against third-party applications and some form of user authentication (PIN or fingerprint) required for access (keychain on iPhone/iPad, keymaster on high-end Android phones and tablets). This satisfies the requirement of two-factor authentication. While it doesn't offer as a good a protection against attacks against the key at rest, it offers a better protection over what is a significant threat here, which is a rogue app on the device exploiting an OS bug to extract the key while it's in use. With the smartcard approach, the key is in your app's memory; with a keychain/keymaster approach, the key remains inside a protected environment, although the decrypted data would be visible to the rogue app anyway.


Relation between decisional SIS and leftover hash lemma in lattices

The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random.  In particular, this implies that for uniformly random $(A,u)$, there exists a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability.  For if not, a significant fraction of $u$ values would admit no solution, hence the distribution of $Ax$ would not be close to uniform, because it never produces any of those $u$ values.  (In fact, most $u$ will typically have many solutions.)

All the above is unconditional---we're not relying on any assumptions about whether a problem is hard or not, we're just making statements about probability.

The "decisional SIS problem" is not a standard concept, because it's not so meaningful.  If one were to define it, the problem would ask to distinguish between $(A,u=Ax)$ and uniformly random $(A,u)$.  But by the above we know that's just impossible: the two distributions are very close, so they can't be told apart.

The computational SIS problem (in its inhomogeneous version) asks, given uniformly random $(A,u)$, to find some short (e.g., binary) $x$ such that $Ax=u$.  Again, the choice of $m$ is such that solution(s) exist with very high probability; the computational question is whether we can efficiently find a solution.

The SIS problem is believed to be hard, thanks to much supporting evidence (e.g., reductions from worst-case lattice problems). However, we can't rule out the possibility that SIS actually is easy, but we just haven't yet found an efficient algorithm to solve it.  Yet even if SIS were easy, that would not contradict any of the above probability statements; it would just mean that we can efficiently find a solution among the several that are likely to exist.


Advantages/Disadvantages of Bcrypt vs. hash/salt

Is it bad to use this method to store passwords?

Yes. It is bad.
Why?

It's bad because you're rolling your own crypto, which is generally considered a bad choice.
It's bad because SHA-3 is slow in software (e.g. on servers and consumer PCs) and fast in hardware (e.g. FPGAs, ASICs) and hence attackers can relatively fast try out many passwords.

So the disadvantages:

SHA-3/2 is fast and therefore an attacker can try many passwords very fast even though you're using a salt.
SHA-3 isn't widely deployed yet and availability of bcrypt/scrypt may be better.
SHA-3 is designed to be a good hash-function, not a good password-hashing-scheme (PHS), whereas bcrypt is designed to be a PHS and was analyzed in this direction as well.
Bcrypt is slower and requires some memory (4 kiB IIRC), so one spends 100ms to check a valid password whereas an attacker needs days / years to crack it because he's slowed down and can't use GPUs efficiently.

So all in all, always prefer bcrypt over standard (iterated) hash-functions.

You may also want to take a look at scrypt and the password-hashing competition (PHC). PHC is in the final phase and until winners are selected and deployed scrypt may be a better option - if you don't want to authenticate users on your server.


Fault-based transition for crypto proof (a la Shoup) with big probability of fault - does it work?

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i.

For example, one of Bellare's applications of this technique is the "poisoned point" principle: you choose the value of a hash function or similar at a particular point. As long as the adversary does not query the function at this particular point, the new game is identically distributed to the old one. If he does query this point, you abort.

Of course what you will argue next is that since you chose your poisoned point at random, the chance of the adversary querying this exact point is negligible. But the actual game-hop doesn't depend on the probability of F happening, it only says either all is well or else F must have happened.

Failure events with non-negligible probabilities happen frequently in hybrid arguments. They tend to make for very lossy reductions of course but the principle stays the same, the hop itself is Pr[S_{i+1} = 1 | not F] = Pr[S_i = 1] and then you compute the probability of F in a separate step to get your "concrete security" constants.


Does the AES-KW (Key Wrap Algorithm) perform authenticated encryption?

Yes, it does perform authentication.

AES-KW is essentially a keyed pseudo-random permutation on large blocks, and being a keyed PRP means 2 things:

Observing ciphertext and plaintext pairs gives no knowledge of the key.
Without knowledge of the key, one cannot obtain any knowledge of the plaintext from the ciphertext or vice versa.

Therefore the knowledge of key (thus identity authenticity under the assumption of key secrecy) is a necessary condition for producing ciphertexts that yield recipient expected values (in this case, the IV) when decrypted.

Also, the wrapping algorithm W is unauthenticated and not approved for use in production as noted in NIST-SP-800-38F, and you may be interested in what exactly is key wrapping.


Security implications of using a high entropy password with a low iteration count for a key derivation function

If a low iteration count is used, it can allow for fast brute-forcing, but what if the entropy of the password is high enough (50 bits? 100bits? more?)? Would it still matter this much?

If the entropy of the process used to choose the password is high enough, then it doesn't matter how cheaply an attacker can test a guess for what the password might be.  Provided the hash is uniquely salted for each user, if your password selection process has 128 bits of entropy, nobody will ever guess the password.  (The story is more complicated if the hash is not salted, but suffice it to say that 256 bits of entropy is enough.)

  Would there even be a way of determining a minimum entropy?

Study the process, not any particular password.  For example, if your process is that you roll a d6 enough times to draw a ten-word diceware password from a 7776-word list, this process has 128 bits of entropy.

  A limited charset like "0123456789ABCD" would surely hinder reaching high levels of entropy, but given a long enough length, it's rather hard for me to guess if it could still be considered safe or not.

From a 14-character alphabet like that, if you choose each character independently and uniformly at random, to attain 128 bits of entropy it suffices to use $\lceil\log_{14} 2^{128}\rceil = \lceil128\log 2/\!\log 14\rceil = 34$ characters.  (For 256 bits of entropy, 68 characters.)


Is it feasible to use combination of ABE schemes for encrypting the data?

Layering your encryption mechanisms like that would not display collusion-resistance between the two schemes. For example, someone with an Org-A key could decrypt the outer encryption over a record designated for Org-A administrators and then pass the inner ciphertext to someone with an Administrator key. Of course, you could use a different key for each Org's administrators, but that's just business logic, not a cryptographic guarantee.

I think you're thinking ABE too narrowly. It sounds like you're trying to force ABE to operate like IBE, which is totally possible, but not the best use of its capabilities. With CP-ABE, you can specify multiple attributes per key and multiple policies per ciphertext, and relate those ciphertext policies using a custom-built predicate expression.

With this in mind, it seems to me that the simplest option for your log-file problem is to encrypt each record using CP-ABE under a predicate that matches exactly the circumstances decryption is supposed to occur under. Each key can contain both the attributes for organization membership and the attributes for role within the organization. For example, records 1-90 might be encrypted to "Org-A" by itself, and records 11-100 to "Org-A AND Org-A-Admin" instead.


What are the advantages of SM3 and SM4 compared to NIST-approved algorithms (SHA3 and AES)

If you are seeking a government contract with China, you might be required to use Chinese government standards for cryptography, just like if you are seeking a government contract with the United States, you might be required to use United States government standards for cryptography.  There are many national pride cryptography standards that have little technical reason to recommend over widely used systems like BLAKE2, Ed25519, etc.  Some of them become prominent enough to matter commercially.


Why is a known-plaintext attack considered a complete break?

if a cipher has a known-plaintext attack, then it is considered completely broken.

Yes, pretty much...

  [Paraphrased] But can't we come up with a case where this isn't true, such as a One Time Pad?

Yes, we can come up with cases like that; however the requirements of such a case (key as long as the plaintext, no key reuse) make such a cipher impractical.

Instead, when we talk about such a cipher:

We generally use the same key to encrypt multiple messages (for example, consider TLS, where the the symmetric key is used to encrypt all records going in the same direction)
And, even when we use a key to encrypt only one message, the attacker might be able to guess parts of it; if he can use those guessed parts as known plaintexts, and recover the parts he didn't know (or even to verify if his guess is accurate), well, the cipher didn't do its job.

"Known plaintexts implies total break" is an excellent rule-of-thumb, even if you can come up with cases where it is not true.


Which algorithm is the simplest reversible fixed-size length-preserving symmetric "cryptography" with low probability of collision?

What's asked is fulfilled by a block cipher with 128-bit key and block size (but notice that it's trivial to make collisions when one of the keys is known). We can't use a stream cipher (collisions would be trivial even with both keys secret), nor OAEP padding as used in RSA encryption (as practiced it is not length-preserving, and not exactly simple).

AES-128 is one suitable block cipher, and is not slow . It commonly runs at over 1 million 16-byte encryptions per second per core in pure software, sometime 20M (for repeated use with the same key), or even 200M with AES-NI hardware. Sure, that's not for AES implemented in pure python.

But using AES from python is easy, even if we use the question's message-as-int interface.

from Crypto.Cipher import AES

def rev_hash(msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).encrypt(msg_int.to_bytes(16,'big')),'big')

def rev_unhash(encrypted_msg_int, key_int):
    return int.from_bytes(AES.new(key_int.to_bytes(16,'big'),AES.MODE_ECB).decrypt(encrypted_msg_int.to_bytes(16,'big')),'big')

Try it online!

That might be acceptably fast. It would be hard to beat if we used the native bytestring interface (avoiding to_bytesand from_bytes), and modified the interface to reuse the AES instances across calls with the same key.

It is possible to make a block cipher that's simple, fast, secure: pick at most two of these features. Here, one of the requirement can be read as: making collisions must be comparable in difficulty to making collisions between MD5 hashes with different (secret) keys appended, even with many plaintext/ciphertext pairs at hand for both keys. Combined with reversibility, that means 64-bit security, since MD5 remains that strong against collisions under these conditions. With this requirement, it's hard to make something simple and fast, especially in pure python.

Without any claim of security, here is a very simple self-contained 128-bit block cipher

def rev_hash(msg_int, key_int):
    for x in [305065944875308933,445871615361279994733287202953785,859072698151683073,893999628687995393356516725455569]:
        msg_int = (((msg_int>>64)^msg_int^key_int)*x+1)&((1<<128)-1)
    return msg_int^key_int

def rev_unhash(encrypted_msg_int, key_int):
    encrypted_msg_int ^= key_int
    for x in [409772003941621297,679237006192346672534347824675841,229702291678999561,786310896237332493342854003018061]:
        encrypted_msg_int = ((encrypted_msg_int*x-x)&((1<<128)-1))^key_int
        encrypted_msg_int ^= encrypted_msg_int>>64
    return encrypted_msg_int

Try it online!

Rationale: there are 5 rounds, each reversibly acting on the whole state. Each round uses XOR with the key, and (except for the last round) modular multiplication by a constant (which gives left diffusion) with addition of 1 modulo 2128, and XOR of the left half into the right one (which gives right diffusion, and alternates addition and XOR to break linearity). The constants are pre-computed as four 18-digits random primes selected among about a million for having 33-digit modular inverses, alternating with the inverses. Such use of round-dependent constants hopefully partially compensates for the total lack of key schedule. Things are arranged so that the encryption is compact. Decryption is even so slightly more complex, because it needs to proceed in reverse order. The addition avoids a stationary point at zero with key 0.

Speed is only marginally better than in first example using AES (like by a mere factor of two), at the expense of security. And again the first example would be much faster with a rethought interface.


Distribution of safe primes generated using different techniques

$\{p \in \mathbb Z \mid \text{$p$ is prime and $(p - 1)/2$ is prime}\} = \{2q + 1 \in \mathbb Z \mid \text{$q$ is prime and $2q + 1$ is prime}\}$

With your intervals suitably adjusted, the algorithm considers the same candidates with the same probability whether you check $p$ or $q$ for primality first.


Why is Ring-LWE more efficient compared to LWE?

If you're using LWE for cryptography, then you'll need a system of $n$ linear equations with errors (mod some $q$). So for those $n$ equations, your key size will have $O(n^2)$ coefficients. In Ring-LWE, you only need $n$ coefficients (see Oded Regev's survey, page 5).
Because you're dealing with polynomials now, you can use the Fast Fourier Transform or (even better for finite fields) the number theoretic transform to multiply them.


We are talking about hash-function families $\{h_k\}_{k\in K}$ here. The parameter $k$ is used to rule out the trivial collision search algorithm that simply prints a collision for a given $h$ (such algorithms exist, but are difficult to find). For large  $K$ such an algorithm would be too large. The parameter $k$ is called a key, but it is not actually secret.

The issue is that concrete hash-functions are unkeyed. This is not a problem in practice, since such ``printing'' algorithms are never found. However, to prove the security of a protocol that uses such a hash function, one needs to show a proper reduction: the protocol is secure as long as the hash function is collision free. The latter is easily formulated for keyed hash functions, but for a single hash function it has been formalized rather recently. This answers your second question.

For the first question, there is no standard way of making a keyed hash function out of SHA-1, because this is not needed in practice. One may think of HMAC-SHA-1, but I doubt its collision resistance when the key is known (it is probably reduced to the chosen-prefix attack).


A simple client/server authentication protocol

If Eve knows $C, \space N, \space K_{CA}(N)$ then she is able to impersonate $C$ just by following the protocol you described above.

If she just knows $K_{CA}(N)$ for a single $N$ then the effectiveness of the attack depends on the set wherein $N$ is picked.

But as you are supposing that the communication channel is not secure, an attacker could spy several authentication session to get a sufficient number of pairs $(N, K_{CA}(N))$ to successfully attack with high probability.


Securely computing functions over source code

I'd like to divide the problem into semi-honest and malicious adversaries with corrupt the party inputting the source code.

In the semi-honest setting, you assume an adversary which follows the protocol correctly, but tries to learn information from the messages the party corrupted by the adversary. As a result, if you assume the adversary is semi-honest, the problem will be trivial to compute since that party can simply compute the lines of code himself and send the other party the result.

It will be very hard to securely construct a secure multiparty computation protocol in the malicious setting where an adversary may also vary the protocol specification, if there are not additional properties about the code known to both parties, like the length of the code. That is for two reasons:

Some data like the length of the code has to get leaked. As to my knowledge, there is no MPC protocol known which permits inputs of variable length.
Adversaries in the malicious setting may input another input like anothercode.py. You can assume that the input is not changed by the adversary, but then you can just use the semi-honest setting.

My best idea of designing the MPC procotol you desire would be to define and reveal properties about the code and then prove them using zero knowledge protocols such that these properties are fulfilled. The best candidates which come to my mind are Zero-Knowledge Using Garbled Circuits or ZKBoo: Faster Zero-Knowledge for Boolean Circuits (the authors even provided an impmenentation of ZKBoo on Github). These protocols are zero-knowledge protocols which prove generic statements (generic as described using AND/XOR gates) using MPC techniques.


Sigma protocol with Pedersen commitment and Hash function

This is no longer a secure commitment. Note that there should not be any way to efficiently verify if a given commitment value $c$ is to a message $m$. However, once you derive the randomness in this way, an attacker could try to guess $m$ and verify if this guess is correct by checking if $g^m\cdot h^{H(m)} = c$. Thus, this is not a secure commitment scheme.


What is the importance of $f_k$ in a feistel network being a permutation

I assume that you are referring to the round function. This is false. The whole advantage of a Feistel network is that $f_k$ does not need to be a permutation. Indeed in DES, it is not a permutation. In an substitution-permutation network it needs to be a permutation so that it can be inverted, but in Feistel inversion is possible in any case. Thus, you have more freedom in choosing $f_k$.


Are there any advantages in using proprietary encryption?

Yes, there are advantages to the attacker.

Using a well vetted encryption algorithm provides a better assurance of security. There may be cryptographic algorithm flaws and/or coding mistakes.

As noted, relying on the algorithm being private just adds a layer of false security.


How to find element g order q, given 2 large primes p and q where q|p-1

The multiplicative group $\mathbf{Z}_p^*$ of non-zero integers modulo $p$ is cyclic of order $p-1$, so it has exactly one subgroup of order $k$ for each divisor $k$ of $p-1$. In particular, it has exactly one subgroup of order $q$, which consists of those integers $a$ such that $a^q \bmod p = 1$. Let $G$ be this subgroup.

To obtain an element $g$ of $G$, take any element $a$ of $\mathbf{Z}_p^*$ and let $g = a^{(p-1)/q} \bmod p$. Then $g$ is an element of $G$ because
$$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$

The order of $g$ is a divisor of the order of $G$, so it is a divisor of $q$, and since $q$ is prime, it equals either $1$ or $q$. The only element of order $1$ is the identity $1$, so if $g \not\equiv 1 \pmod p$ you are done. Otherwise, try another $a$.


Hash function based on block cipher (and proof of security in the PRP model)

A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible.

For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP:

  PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP (pseudorandom permutation) then Skein is a PRF. It is important to understand that we are referring, in this context,
  to the keyed version of Skein. The PRF property is that the input-output behavior of keyed Skein
  should look like that of a random function to an attacker who is not given the key. This proof
  supports the usage of keyed Skein for key derivation (KDF). It also supports the use of keyed Skein
  as a MAC. This is true because any PRF is a secure MAC


Is it wise to use HOTP (raw bytes) as a key for HMAC?

As mentioned by SEJPM in the comments, four bytes is much too short for an HMAC key.

Since KEY_SECRET is already in place, you could just use it directly as a MAC key, but then you need to make sure that DATA cannot collide with any counter value. You could do this by prefixing DATA with enough constant values to make it longer than the counter.

For example: MAC = HMAC(KEY_SECRET, 0x01 * 9 || DATA, where nine 1-bytes are prepended to make it longer than the eight-byte counter of HOTP.


Should we use the new CAESAR competition ciphers?

The CAESAR competition took way too long, didn't go as well as expected, and other interesting constructions that would have been worth considering were designed after it started.

Some of these (AES-GCM-SIV) got standardized before the competition was over, and may get more adoption than CAESAR candidates.

The goal of CAESAR wasn't clearly defined. We didn't end up with AES alternatives. If only because AES is well-supported in hardware and has no sign of being broken anytime soon.

I'm not convinced of the practical outcome of the NIST LWCC competition either. AES is here to stay.

To get back to CAESAR, some finalists are interesting.

In particular, AEGIS doesn't change the AES core function, but builds a very fast (faster than AES-GCM) and simple construction taking advantage of the parallelism of some CPUs.

AEGIS-256 has been implemented in libsodium. So, it may get some adoption for applications where speed is the primary concern.


Advantages of RSA / EC against QC attacks

This is by no means a comprehensive answer on this subject, but perhaps it's a good start.
Shor's algorithm for (specific) ECC
This paper by Proos and Zalka compares implementations of Shor's algorithm for integer factorization and discrete logarithms for some elliptic curve groups (notably, ONLY those over prime finite fields).
If $n$ is the bit length of the group (from section 6.3):
RSA                      | ECC
-----+--------+----------+-----+--------+---------
n    | qubits | time     | n   | qubits | time
-----+--------+----------+-----+--------+---------
1024 |   2048 | 4.3*10^9 | 163 |   1000 | 1.6*10^9
2048 |   4098 |  34*10^9 | 224 |   1300 |   4*10^9
3072 |   6144 | 120*10^9 | 256 |   1500 |   6*10^9

RSA needs about $2n$ qubits, while ECC needs approximately $6n$ (for smaller $n$). Similarly, RSA needs ~$4n^3$ gates, while ECC only requires ~$360n^3$.
ECC is classically more difficult than RSA, allowing for smaller key sizes and more efficient computation. Quantumly, ECC is still more difficult than RSA, but less so, leading to what the authors call a "quantum advantage" for elliptic curve discrete logarithms over integer factorization.
Comparing RSA-3072 to ECC-256, they found that a quantum computer needs to be approximately $4\times$ as big and takes approximately $20\times$ as much time to crack RSA as compared to ECC.
Keep in mind that this work is from 2008 and is only relevant for curves over prime fields.
In practice
Obviously a factor of 4 in the number of qubits is not "much more quantum-resistant" as per the link given by fgrieu. It's very possible that ECC over GF($2^m$) is much more efficiently broken by quantum computing.
Due to the similarities of the two problems, I can't imagine that qubit configuration would have much of an impact in one direction or the other.
However, this is all conjecture on my part.

It is not likely that the gap between quantum
cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to
serve as a basis for a cryptographic strategy.

In any case, I interpret the above quote from as there being no practical difference between the two. Both should be considered utterly broken at that time.


Does secure hashing imply secure symmetric encryption?

The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.

A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.

Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)\oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.


What is the polynomial to use in the Massey-Omura cryptosystem?

Actually, it doesn't matter (as long as the polynomial is prime, of course).

For any $n$, there's only one finite field $GF(2^n)$, however there are a number of ways of mapping those elements to bit patterns.  We call that mapping a representation; one method of generating such a representation is to use a prime polynomial of degree $n+1$.

Now, between any two representations of $GF(2^n)$, there will be a mapping that converts values in one representation into values in the other; if both representations are sane (by which I mean that they perform addition by bit-wise exclusive-or of the representation), then this mapping will be linear (and hence, cheap to compute).

In Massey-Omura, the sides exchange the representations of the field elements $m^a$, $m^{ab}$, $m^b$; if there was a representation that makes this exchange weak, then the attacker could convert these three elements into that weak representation, find the value $m$ in that weak representation, and then map it back into the original representation, breaking MO in the supposedly strong representation.  Hence, no representation is any stronger or weaker than any other -- the choice of representation is strictly a practical matter.

In fact, if you go to the patent, Massey and Omura suggest using a normal representation (which is an alternative to a polynomial representation); in normal representations, the operation of squaring is cheap, and they believe that this will make computing exponentiation cheaper overall.  Again, this is a practical consideration -- it has no impact on security.

I will leave off with one security issue: people have recently made significant progress in computing discrete logs over $GF(p^m)$ for small $p$ (and 2 is as small as we can get), and smooth $m$.  Because of this, it would appear to be wise to select a prime value of $n$; that way, these recent results do not apply.


Does adding complexity mean a more secure cipher?

xoring the output of the cipher with the plaintext message

Xoring the message into the ciphertext removes the ability to decrypt the ciphertext.

If all you have is $k, c = E_k(m) \oplus m$, then you need to know $m$ in order to strip the external $m$ off of $E_k(m)$ before you can apply $m = D_k(E_k(m))$; Basically, you would need to know the message in order to "decrypt" the message, but since you already know the message, then there would be no knowledge gained from "decrypting".

$(E_k(m)\oplus m)||(E_k(m) \oplus 1111...11)$

The previous section was striked out, because there was more to the suggestion than simply xoring the message into the ciphertext.

In fact, the complete suggestion is far, far worse then simply implying the inability to decrypt a ciphertext: Anyone can decrypt a ciphertext from this scheme without requiring the key.

$$c = (E_k(m) \oplus m) || E_k(m) \oplus 1111\dots 11)\\c_{\text{a}} = E_k(m) \oplus m\\c_{\text{b}} = E_k(m) \oplus 1111 \dots 11\\c' = c_{\text{b}} \oplus 1111\dots11\\m = c_{\text{a}} \oplus c'$$

The value $1111\dots11$ is known to all, so anyone can compute $$E_k(m) = E_k(m) \oplus 1111\dots11 \oplus 1111\dots11$$

So $E_k(m)$ is effectively public knowledge, so again anyone can compute $$m = E_k(m) \oplus m \oplus E_k(m)$$

This scheme is completely broken.

  I have tried searching for examples of similar schemes and found nothing (which probably means it's not a good scheme) but I need to justify my answer.

See the previous section - "encryption" is an invertible process: You have to be able to undo the transformation so that you can retrieve the plaintext from any given ciphertext.

It is completely broken, so you won't find anything similar to it (other than situations where people asked this same question and found it to be broken)

  Does this in fact increase security of the cipher or increase new problems.

It's a lot easier to determine whether or not doing x or y will increase/decrease security once you have a clear goal of what it means to be secure. This is a context dependent notion.

It helps to list:

What you have
What your adversary can do
What you want to accomplish (in very specific terms).

If you don't know where to start, then look for the standard notions of security that cryptographers have already worked out for the context of interest (e.g. indistinguishability for ciphers)


Multidimensional meet-in-the-middle attack on AES

Why GOST was broken with such method and AES not?

MD-MITM attacks have been published e.g. against KATAN and GOST in https://eprint.iacr.org/2011/619. The authors stated that their attack is "suitable for lightweight ciphers with simple key schedules and block sizes smaller than key lengths". Another reason and the answer for this question is, that the attacked ciphers in that paper had a block lengths up to 64 bit, while AES has a block length of 128 bit and the space–time tradeoff would require too much space.


Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed that LPN is (in some sense) "harder to break" than LWE, simply because we know much less attacks on LPN. It seems to have less structure that could be exploited in advanced attacks - but also, for the very same reason, has far less known applications. Yet, no formal reduction relating any of them is known. It should also be mentioned (thanks for TMM for pointing that out) that the best known attack on LPN takes time $2^{O(n/\log n)}$ (where $n$ is the dimension) while the best known attack on LWE takes time $2^{O(n)}$ - hence LWE appears stronger than LPN when considering solely the running time of the best known algorithms.

Note that while they clearly seem related, there is a fundamental difference: LWE uses a Gaussian noise, while LPN uses a Bernouilli noise. The first type crucially relies on some "non-black box" considerations on the field where it's implemented (since we need to be able to talk about "small" and "big" field elements), while the latter one is actually completely oblivious to the field (i.e., you can define LPN over a field in a way that makes a black-box use of the field).

To elaborate on your sentence "Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits": it's not really the case, actually. The natural generalization of LPN to a larger field $\mathbb{F}$ would be obtained by adding to each linear equation a noise which is a uniformly random element with some probability $p$, and $0$ with probability $1-p$ (this is the natural generalization of the Bernoulli noise over $\mathbb{F}$). LWE, instead, uses a small Gaussian noise everywhere, which is quite different.

EDIT: to clarify, the last paragraph above is my point of view, but not the formal "demonstration" that LWE is not a generalization of LPN. As pointed out by TMM and Chris Peikert in the comment, the Bernoulli distribution over $\mathbb{F}_2$ can technically be seen as a Gaussian distribution - hence LPN can be seen as LWE over $\mathbb{F}_2$ (or conversely, LWE can be seen as the generalization of LPN over larger fields). My point in the last paragraph is that this is not the only possible generalization, and the alternative one which I mention seems to me much closer in spirit to the original LPN assumption: under the "LPN over large fields with Bernoulli noise", one gets essentially the same implications as with standard LPN (e.g. public key encryption, but not collision resistance), and the same structural properties (i.e. the best known attacks on this generalization are the natural generalizations of the best known attacks on LPN over $\mathbb{F}_2$). LWE is technically a generalization of LPN over larger fields, but one with important differences compared to the original LPN assumption (different attacks, different (and much more "advanced") implications, non-black-box use of the field, etc).


Acceptable assumptions when proving security

The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in fact secure as no one has been known to attack them.

For ciphers the usual model is PRP, pseudo-random permutation, although the ideal cipher model is also used, but generally PRP is realistic and strong enough to prove things secure.

Number theoretic primitives do not output random strings. For instance DH never produces all zeros. You should use hashing to make this truer.

For protocols usually a game is designed where an adversary tries to get bad things to happen. Showing that the game is lost if the cipher is a PRP implies that a real version will be secure if the cipher behaves like a PRP, and so is generally considered a proof of security. However, the constants involved matter: if you haven't read DJB "Non-uniform cracks in the concrete" you should before embarking on any sort of provable security work.


Algorithm to transform plaintext to a key of desired keysize, when using input plaintext as key for FPE?

I'm using it as a one way encryption on plaintext values such as SSN, names, dates, etc.

I suggest rethinking your approach.  None of these values have much entropy, so it would be straightforward to bruteforce the original plaintexts (just like cracking a password hashed with a fast hash function).

If you're planning to use these values for authentication, that doesn't sound like a great idea... but I know that, in some applications, it's the best you can do.  A few suggestions:

Use a password hash instead of fancy encryption.  Since there's likely not much entropy in the secret values, a password hash would be helpful in slowing down brute force attacks.
Combine the values before hashing.  This will at least force attackers to crack them as a group, not one-at-a-time.  Be sure to combine the values such that they are delimited unambiguously.

If you must process the fields separately (in order to perform comparisons between accounts, for example), I still think a password hash is better suited to this purpose -- just use a fixed salt to make the hashing deterministic.  Don't expect too much security here though; thoroughly hashed dates can still be cracked quite easily.


Is a strong block cipher usable as a strong sponge function?

I believe that, in this specific case, you are correct; it would appear to take $2^{60}$ effort to find a collision in the above function.

On the other hand, there is one nit with this approach: this makes stronger assumptions on the block cipher than is typically assumed.  A block cipher behaves as a random permutation if it is keyed by a random unknown key; there is no such requirement that holds if it is keyed by a publicly known key.  AES is believed to act like a random permutation even with a fixed key, however that might not hold in general.  You could come up with an artificial block cipher that meets the normal requirements, but doesn't work as a sponge function.


So after some more help and an extensive reboot of my math skills, I found the answer. The information that I overlooked but is crucial to have is the total length of the message. Moreover, we also need a second message with slightly changed parameters. This thus presupposes that an attacker has access to at least 2 known ciphertexts with known prefix and that both ciphertexts only differ by the prefix (known) and padding (unknown).

Following the above we end up with:

$c_1$ = $(prefix_1 + secret + padding_1)^e mod \ n$
$c_2$ = $(prefix_2 + secret + padding_2)^e mod \ n$

Now, without the prefix change this would be a simple case of Coppersmith's short pad attack. But the prefix requires some changes. This is where the length comes in handy: if we know the prefix change (e.g. a 0 byte becomes a 1 byte), and we know the total length, we can find the additional delta between the 2 ciphertexts (i.e. the delta besides from the padding), since we know which bits changed and can then add/substract $2^i$ for all changed $bit_i$

Example: if

$prefix_1$ = 'hello\x00'

$prefix_2$ =   'hello\x01'

and the total message length (including secret and padding) is 100, we know that the 94th byte changed from 0 to 1. In bits, it means the 752nd bit changed from 0 to 1, hence adding $2^{752}$.

From here we can pick up the Coppersmith attack whereby the second polynomial needs to incorporate the difference:

$g_2(x,y) = (x+y+\Delta)^e - c_2$

The rest follows the classic attack. Now once we have $y$, we can use the Franklin-Reiter related message attack with the small exception that we need to also add the $\Delta$ we calculated from the prefix.

I realize this might have gone beyond the scope of my answer but I thought it was an interesting twist on existing exploits that could help someone out in the future :)


Is LUKS Anti-Forensic information splitter (AFsplit) indistinguishable from random data?

No.

AFSplitting is merely meant to provide diffusion, not cryptographically secure randomness.

When you check the LUKS On-Disk Format Specification (eg PDF of v1.1.1) you'll notice it states

  LUKS uses anti-forensic information splitting as specified in [Fru05b]. The underlaying diffusion function shall be SHA1 for the reference implementation, but can be changed exactly as described in the remarks above.

Even though the (broken due collision attacks) SHA-1 function is used as a diffusion function in the reference implementation, that doesn't mean the AFSplitting function does provide any more than that – diffusion.

While it definitely has a (let's just call it) random character, you should not generally rely on it to provide cryptographically secure randomness indistinguishable from random data. That's not what AFSplitting (by itself) is intended to provide. While diffusion surely adds to randomness, there's a big difference between “diffusion” and “cryptographically secure randomness indistinguishable from random data”. Both are hardly exchangeable terms.

And I'm not yet considdering practical breaks against SHA-1 which also might or might not render the answer into a clear “no”… but that's another question.

EDIT

To clarify this a bit more indeep, trying to clear up some confusion in the comments by the asker.

Let's remember the question asked

  I want to know if AFsplit(random_data_input, stripes, digestmod=sha) output is indistinguishable from random data, not knowing random_data_input.

and

  … I just want to focus on this particular function.

The question didn't ask if PBKDF2 is indistinguishable from random data and the question did not assume input to AFSplit to be indistinguishable from random data either.

Therefore, when merely focussing on the AFSplit functionality (as the question asks), one can and has to cryptanalytically assume distinguishable data inputs too. Otherwise, the input to AFSplit would have needed to be defined as “exclusively data indistinguishable from random data”, but the question doesn't limit the input to such indistinguishable data when asking what AFSplitting outputs.

In LUKS the user password is entered and processed by PBKDF2 (which provides the randomness which should be indistinguishable from random data.  The master key is then splitted by the AFsplitter into a number of stripes… via diffusion (using SHA-1 or an alternative replacement).

So, any data indistinguishable from random data needs to be produced outside the AFSplit function. If you'ld feed AFSplit distinguishable data, AFSplit won't magically turn the data you feed it into data indistinguishable from random data; it merely diffuses what you feed it. That's all you get when keeping the focus on this particular function (and the main reason for no as an answer). How the input to AFSplit should be produced in a LUKS implementation is another story, and goes well beyond the AFSplit function (which is merely a diffusion-providing piece of the LUKS cake) and therefore well beyond what was being asked – which was to focus on this particular function.


Proof of RSA security dependent on public key exponent

Loosely define the RSA problem as solving for $x$ the equation $c=x^e\bmod N$, with $x$ random in $\{0,1,\dots,N-1\}$ (or equivalently $c$ random in this set), and $(N,e)$ properly chosen. The best method we know for tackling that problem is factoring $N$, but we have no proof that there is no substantially better method.

We do not know if the RSA problem is more difficult when $e$ is small (e.g. $e=3$), or large or/and random, or even have expert consensus on that research topic or what should be done in practice (I'm in the league favoring good padding with $e=3$ at least when speed matters, and reluctantly bowing to $e=65537$ to avoid conflict with official advice); much less do we know if it is possible to make a proof in either direction.

We do not know an efficient integer factorization method (that is one with effort growing polynomially with the number of digits in the number to factor); and I doubt that there is a proof or even argument that such an algorithm can not be found, for integer factorization is not in Wikipedia's list of known NP-complete problems.