Converting normal alphabets to 64 bit plain text

What's asked requires choices not explicit in the question:
1. Character encoding into bytes
The most common and recommendable convention nowadays is UTF-8, which encodes any character as a sequence of 1 to 4 bytes, including any ASCII character as 1 byte. For these, UTF-8 is compatible with many other earlier conventions that encode each character to a single byte. The Latin alphabet and Arabic numerals are encoded incrementally, per the poor man's ASCII table
    a $\to$ 0x61     b $\to$ 0x62     …   z $\to$ 0x7a
    A $\to$ 0x41     B $\to$ 0x42     …   Z $\to$ 0x4a
    0 $\to$ 0x30     1 $\to$ 0x31     …   9 $\to$ 0x39
      $\to$ 0x20 (space)
Note: the prefix 0x introduces hexadecimal in this answer, and some common computer languages.
Therefore, the two-character hi gets encoded to the two bytes 0x68 0x69 per UTF-8, ASCII, ISO/IEC 8859-1, Windows-1252, and many others conventions.
Encoding and decoding is built into many common computer languages, e.g. in Python
bytes('Hi', 'UTF-8') equals b'\x48\x69\xf0\x9f\x98\xb7' and
b'\x48\x69\xf0\x9f\x98\xb7'.decode('UTF-8') yields 'Hi'.
Other conventions are still in wide use, e.g. per UTF-16 LE with surrogate pair support, the three-character 'Hi' encodes to 0x48 0x00 0x69 0x00 0x3d 0xd8 0x37 0xde.
2. Padding
That is handling the last byte(s) to form the last (perhaps only) block for the cipher, of 64 bits or 8 bytes in the context of DES. There are several conventions around, the most common being:

Zero-padding. For a block cipher with $w$ bytes ($w=8$ in the case of DES), it is added $0$ to $w-1$ bytes at 0x00, as necessary to reach a multiple of $w$. That's fine for encodings (including UTF-8) that assign to byte 0x00 a no-operation or end meaning, but is not usable for arbitrary bytestring, because the decoder facing a last block ending in 0x00 won't know if that byte needs to be kept or removed.
hi per UTF-8 is padded to 0x68 0x69 0x00 0x00 0x00 0x00 0x00 0x00.
Various bytes padding, the most common of which nowadays being PKCS#7 padding. For a block cipher with $w$ bytes ($w=8$ in the case of DES), it is added $1$ to $w$ bytes which common value is the number of bytes added in order to reach a multiple of $w$.
hi per UTF-8 is padded to 0x68 0x69 0x06 0x06 0x06 0x06 0x06 0x06.
Note: The decoder handling the last block (if any) should get the value $x$ of the last byte, remove that byte, then remove the $(w-1+x)\bmod w$ byte(s) before that, thus leaving $0$ to $w-1$ bytes. That's compatible with some common variant of PKCS#7 padding such as ANSI X9.23, and minimizes the risk of padding oracle attacks.
Bit padding. It's common in cryptography for MACs, hashes, and sometime encryption (I know no official name; it's ISO/IEC 9797-1 Padding Method 2 in a DES MAC context). For a block cipher with $b$ bits ($b=64$ in the case of DES), it is added a single bit at one, then $0$ to $b-1$ bit(s) at zero as necessary to get to a multiple of 64 bits. In most contexts including DES, the bits are converted into bytes per big-endian convention, so that the single bit at one becomes byte 0x80.
hi per UTF-8 is padded to 0x68 0x69 0x80 0x00 0x00 0x00 0x00 0x00.

Finally, there's a specific
Bit numbering per the DES specification
and it matters when doing one's implementation of DES from scratch for educational purposes. Each of the 8 bytes is turned to 8 bits per big-endian binary, leading to a sequence of 64 bits numbered from 1 to 64. Bit $i\in[1,\,64]$ belongs to the byte at offset $\lfloor(i-1)/8\rfloor$ and extractible by shifting that right by $(64-i)\bmod8$ bit(s) then keeping the low-order bit.
In C: (blockOf8Bytes[(i-1)&7]>>((64-i)&7))&1 (the 64 can be omitted).
Thus hi per UTF-8 with zero padding is
0110100001101001000000000000000000000000000000000000000000000000
with the seven bits 2, 3, 5, 10, 11, 13, 16 set (at 1) and the other fifty-seven bits clear (at 0).

Note: Except in the insecure ECB mode of operation, the plaintext would be combined (likely, by exclusive-OR) with something before entering the DES block cipher.
Note: The question mentions “(…) 128 bit binary digit input for DES”, but nothing that requires more than one 64-bit block for hi.
Note: DES is insecure as a design choice due to its 56-bit key. It is obsolete at least for bulk encryption purposes in all its forms, including 3DES with 168-bit key, due to its 64-bit block size.


In ssh-keygen.c of the OpenSSH source code, there is the following call:

        if (prime_test(in, out, rounds == 0 ? 100 : rounds,
            generator_wanted, checkpoint,
            start_lineno, lines_to_process) != 0)

...and a comment for the function prime_test says:

 * perform a Miller-Rabin primality test

Therefore, it does indeed use a Miller-Rabin test. One can show that for composite $n$, at least half of the possible random choices prove the compositeness of $n$ (in fact, there are even stronger bounds), hence the confidence in $n$'s primality after $k$ runs of that test is larger than $1-2^{-k}$. In the particular case $k=100$, the probability is (larger than) roughly $1-2^{-100}=0.999999999999999999999999999999$, which is a lot.


NP complete problems related to permutations of binary vectors or block ciphers

In a strict sense, no.  NP is about worst-case hardness.  Cryptography requires average-case hardness.  $P \ne NP$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness.

For block ciphers, we need average-case hardness.  Therefore, there are good reasons to expect that $P\ne NP$ won't be enough.

(There are other reasons to think that $P\ne NP$ is not enough -- see, e.g., Impagliazzo's many worlds of cryptography -- but I'm trying to keep it simple for you.)

In a loose sense, you might be able to find some loose relationship, e.g., where someone builds a block cipher whose security they claim is "based" upon the NP-completeness of some problem.  But that kind of claim is on very shaky ground.  It's very unlikely they will have proven a theorem that says "if $P\ne NP$, then my block cipher is secure".  Instead, they will have some handwavy argument about how the problem is "related", and it'll all be just a bit sketchy.

The blog post you mention actually describes a relationship that goes in the opposite way: if secure ciphers exist, then a large class of natural ways of trying to prove $P\ne NP$ are doomed to fail.  That's a pretty nifty result.


How does Bluetooth pairing (SSP with numeric comparison) work?

I think that you miss the point of this method. You can think of this SSP as a key-exchange protocol between two devices which have nothing shared between them a priori and also the entire communication is inspectable and even temperable, that is, the adversary can modify/send messages as it wishes. The big advantage of this SSP method over a usual key-exchange protocols (i.e. between computers over the Internet) is that the devices have a human linking between them, or abstractly, authenticated communication channel that cannot be tampered with by the
adversary and can be used to send a short message.

Regarding the MITM attack, I'm not very familiar with the spec but looking at this makes it more clear: Assume that as an attacker you execute this key-exchange protocol with both devices A and B. Let $pk_A, pk_B$ be the public keys of A and B resp. and let $pk_A',pk_B'$ be the keys that you (the adversary) choose in the execution between you and A and between you and B resp. Now the number that appears on the screen is a function $H$ (truncated as needed) applied to the keys of the parties (and some more random strings but let's skip it for simplicity), that is, the number on A's device would be $c_A=H(pk_A,pk_A')$ (where the adversary behaves as device B) and the number on B's device would be $c_B=H(pk_B',pk_B)$ (where the adversary behaves as device A). The goal of the adversary is to make $c_A=c_B$ in order for the device to be "paired". The randomness of $pk_A$ dictates that $c_A$ is random as well, which means that in order to make $c_B=c_A$ the adversary has to find a $pk_B'$ such that $c_A=H(pk_B',pk_B)$. This is a hard problem (as finding a preimage for a hash function) and thus the MITM attack could not be held successfully.


computational complexity class of decryption of AES

The time of AES encryption/decryption in any of the standard modes like CBC or CTR or GCM is polynomial (more precisely, linear) in the size of the message.

Proof: One call to the AES encryption/decryption function takes some constant number of steps, which we can represent with the constant $c$.  For example, AES-128 makes one call to the key schedule to generate the round keys, one 'whitening' step with a round key, and then 10 calls to the round function, which itself takes a constant number of simpler steps - 16 parallel applications of the S-Box, one 'ShiftRows' transposition of bytes, 4 parallel applications of the MixColumns linear function (absent in the last round), and one AddRoundKey step.  AES-192 and AES-256 similarly make constant numbers of calls to the round function.

For any of the standard modes and a message of bit-length $\ell$, the number of calls to the AES encryption/decryption function is some linear function, $f(\ell)$.  For example, the cipher-call function for CTR is: $f^{CTR}(\ell) = \lceil \frac{\ell}{128} \rceil$.

Sometimes these modes have to do other things than make calls to the block cipher (e.g. GCM has to do one finite field multiplication per 128-bit message block), but in the standard modes these are also always linear or constant in the length of the message.  Let's say the function $g(\ell)$ returns the number of 'extraneous' (non-AES) steps as a function of the message length.

Therefore, the encryption/decryption time for AES in any of the standard modes is some linear function of the length of the message, $c \cdot f(\ell) + g(\ell)$.


In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$.

However, there are cases for which it's hard: for example, when $n=pq$ is the product of two unknown primes $p,q$ and $g\in\mathbb Z/n\mathbb Z$, then the task is equivalent to decrypting the RSA ciphertext $g^a$ with respect to the public key $(n,a)$, which is generally assumed to be hard.


Can "(input * X) mod Y" with N iterations be computed in less than N operations?

This algorithm is computing $$I'=I\cdot Y^N\bmod X$$. Using a standard square and multiply algorithm you need at most $\lceil 2\log_2(N)\rceil+1$ modular multiplications to compute $I'$.  This is about 33 multiplications for the given example of $N=10,000$ which probably counts as this algorithm being "predictable".


(Note: This answer is based on $k$ being generated by applying a pseudorandom function to a unique message-ID – counter – each time.)

It depends how many times you want to encrypt with it.

If you want it as a complicated OTP, then it's secure. In order to see this, just ignore the $x$ parts and note that $s_1m \bmod p$ and $s_2m \bmod p$ are to independent encryptions under random keys $s_1,s_2$ (note that $s_1$ and $s_2$ have to be uniform in $\{0,\ldots,p-1\}$. For this, you don't need $p$ to be large (just big enough to contain $m$).

If you want to encrypt many times, then it is certainly no longer information theoretically secure. However, just ignore $s_1,x_1,s_2,x_2$ and think of them as public constants. Then, you are encrypting by $m+k \bmod p$ where $k$ is pseudorandomly generated. This is like a type of "counter mode". As long as the RANGE of the pseudorandom function is $\{0,\ldots,p-1\}$ you should be able to prove it.

In both cases, it is overly complicated…


How HOTP values are validated according to RFC 4226

I agree that Gilles' interpretation in the comments is the only one that makes sense; the RFC clearly contains an editorial error, and should read either (emphasis indicates corrections):

  "If the value calculated by the authentication server matches the value calculated by the client, then the HOTP value is validated."

or:

  "If the value received by the authentication server matches the value calculated by the server, then the HOTP value is validated."

The first sentence in your quote isn't grammatical anyway: the words "HOTP client" appear to have been randomly and meaninglessly appended to it, perhaps as a result of careless copy-pasting.

The IETF has a whole bunch of errata for RFC 4226, but this particular mistake doesn't appear to be listed there.  You might want to report it yourself.


How secure will this be against brute-force attacks?

I don't know how you're adapting the digest of SHA-1 to meet the key requirement of AES-256 (stretching the 160 bit digest into a 256 bit key), but if you somehow have a way of doing that without seriously compromising key entropy, then you have a theoretical key space of $2^{256}$. That window is limited by the limitations on your encryption passphrase however. In an ideal case for decryption where the person cracking your cipher has your program and knows the limits on your passphrases, they don't have to test all $2^{256}$, only your possibilities.

Say you limit passphrases to $10$ keys, alpha-numeric. That's $62$ characters to work with. The practical key space for you is $62^{10}$.

Arguably, it is currently impossible to decrypt even in the above worst-case scenario. This is largely due to another factor: verification of success. Say you only had $200$ possibilities. Someone trying to decrypt the file needs a way to check if each of the $200$ attempted keys yielded accurate results. Given that they may not know the nature of the file, that seriously complicates the process.

You're good for a while.


The way you worded the question is misleading, as the entropy test is performed AFTER they have extracted an AES key from memory. The test is used to confirm whether it is a likely encryption key or an AES key used for benchmarking or algorithm verification.

The actual procedure involves cycling through the entire memory space, and examining each block of memory that could be the size of a computed key schedule, which may look daunting, but is actually quite fast, due to the simplicity of the key schedule. They cycle through the memory space in word increments and compute the first iteration of the key schedule. If it matches the next words in memory, the entire key schedule is performed and compared. This is about 134 million iterations in total on a 4GB memory space, which only takes a few minutes; it is especially if the testing system has AESNI instructions on multiple cores, the search may only take seconds. The full key schedule is 10 iterations for a 128-bit key.

Update: It looks like they used an automated entropy test to eliminate memory blocks before the final (manual) entropy analysis of the key. This is done by cycling through memory blocks and counting duplicates. If any one byte value comprises 5% or more of the block, it is flagged as non-key. The block search size is 11 round keys or 176 bytes. This is faster than computing the key schedule in their code, but slower if you have code with AESNI instructions (3rd party code to perform the same search).

The only time this becomes slow is when there is memory corruption, such as in a cold boot attack. In that case, the missing bits need to be extrapolated, and a slower algorithm needs to be used to find candidate keys.

The key schedule only performs 4 operations on the master key, and these can be computed forward and reverse at almost any point in the key schedule. Additionally, 3 of the operations are not done on every word of the key. If memory corruption is present, a 4 word block is selected, and the key schedule is computed in both directions (128-bit key). If there are word matches in either direction, that area will be flagged for reconstruction of the entire key space.

Once AES keys are identified, an entropy analysis is performed to determine if it is a likely key for the application using AES. Then the various combinations of found keys are used with the application until a successful decryption is performed.


No, you can reuse a message as often as you want with the OTP. (But never reuse the key!)

What happens if you reuse a key? The attacker can xor the two encrypted messages (ciphertexts) and gets the xor of the two plaintexts. The xor of two messages is highly insecure and can be easily turned into two plaintexts with some know patterns.

What happens if you reuse a message? The attacker can xor the two encrypted messages and gets the xor of the two keys. What happens if you xor two fully random keys? The resulting string is also fully random, and it's not possible to get any information out of it. You see, there's no problem with reusing the message.


Are there low-bit hashing or encryption functions for teaching cryptographical concepts?

Actually, lecturers/professors build simplified version of block ciphers and hash functions so that the students can understand better.
For Block ciphers there are;

Simplified DES by  Edward Schaefer in 96. You can also set it in Stinson's book Appendix G.
Simplified AES is first appeared on Cryptologia, 2003 by Musa, Schaefer, and Wedig.
Another Simplified AES Version again by Edward Schaefer
A Tutorial on Linear and Differential Cryptanalysis in 2002 by Hayes contains a simple SPN based block cipher to teach the Linear and Differential Cryptanalysis.

For hash functions;

Luhn Algorithm is a starting point.

A toy hash function  by Joshua Holden

In this paper I will discuss the requirements for a secure hash function and relate my attempts to come up with a “toy” system which both reasonably secure and also suitable for students to work with by hand in a classroom setting

Once  the Simplified version of AES is grasped, you can use them to build a hash function based on the Merkle–Damgård construction.

Also, this question Is there a simple hash function that one can compute without a computer? contains some others hash functions.


(Re) How to validate AES decryption was successful?

What you are trying to do is called Authenticated Encryption, the combination of encryption and authentication in on scheme.

The simplest form of it is doing encryption and authentication seperately either by authenticating the plain text (Mac-Then-Encrypt or Mac-And-Encrypt) or doing it the other way round: Encrypting first and then calculating the checksum over the ciphertext. None of the three variants are inherently insecure, but the latter version is considered the most secure these days and it is also the easiest one to get right.

What has to be noted is, that you should not just calculate a hash as you suggested but a MAC instead (like HMAC-SHA256), which can not be forged by an adversary. A hash alone only protects the integrity of the message helping you against errors but not against attackers.

Apart from these, there are also encryption modes which combine the encryption and authentication in one operation. If you do not have a particular reason for sticking with AES-CBC, these modes would be preferred.
The most popular of these modes would be AES-GCM, other options include AES-CCM, AES-OCB or ChaCha20-Poly1305..


Can you help me understand the Common Modulus Attack in a Lucas Group?

Just find the modular multiplicative inverse $x_C$ of $x_A$ using the extended Euclidean algorithm:

$$(x_A)^{-r}\equiv(x_C)^{|r|}\mod{R}$$

and

$$x_Ax_C \equiv 1\mod{R}$$

Then, once you have $x_C$, you'll be able to compute:

$$(x_C)^{|r|}(x_B)^{s}\mod{R} \equiv M$$

http://en.wikipedia.org/wiki/Modular_exponentiation


Scalar Multiplication on Elliptic Curves

The typical way to do this is the double and add method.

You start with the binary expansion of the scalar $57_{10}=111001_2$

Then scanning right from left, for each bit you double and if the bit is set to $1$ you add.

With elliptic curves it would look like this:

$Q\gets\infty$ (or the point at infinity since it is the identity element)
$P_{tmp}\gets P$
$bin\gets [1,0,0,1,1,1]$ (i.e., the binary expansion of the scalar reversed)
for $i$ in $bin$:
$\ \ $if $i==1$:
$\ \ \ \ \ Q\mathrel{+}=P_{tmp}$
$\ \ P_{tmp}=P_{tmp}+P_{tmp}$
return $Q$


Why do we focus on polynomial time, rather than other kinds of time?

The focus on polynomial time comes from cryptography's historical origin as a branch of computational complexity.

It makes sense for a theoretical field to develop technology-independent ways of measuring efficiency. Actual clock time or number of clock cycles are technology-dependent. Talking about running time in an asymptotic sense is convenient because it makes specific technology irrelevant. No matter how fast machine A is compared to machine B, if machine A runs a $\Theta(n \log n)$ algorithm and machine B runs a $\Theta(n)$ algorithm, then eventually (for large enough $n$) machine B will be faster in terms of actual time.
Algorithms that run in time $\Theta(n)$ are objectively fast/scalable/"efficient".
Suppose an "efficient" algorithm makes calls to a subroutine (we don't count the cost of the subroutine against this algorithm), and the subroutine can also be realized by an "efficient" algorithm. Then, intuitively, the overall system (accounting for both the calling program & subroutine) should be "efficient" too. This is a basic composition property, and without it you have a very messy theory. Polynomial-time is the minimal way to define "efficient" that contains running time $\Theta(n)$ and enjoys this composition property.

It is for these reasons that "polynomial time" is synonymous with "efficient" in computational complexity. Its minimal nature makes it a natural and well-motivated definition.

However, just because it's well-motivated and natural doesn't mean it's sacred. Mihir Bellare points out asymptotic complexity as one of the arbitrary aspects of cryptographic research, to be critically examined.

As others have said here, there is plenty of work that follows a concrete (rather than asymptotic) style. There is nothing wrong with working in this style. The main differences are: (1) things are a little messier; you can't hide all the mess inside an unspecified polynomial; (2) you forfeit the (very convenient) composability property.


Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?

There are two cases. In the first case, $m$ is very small, and in such a case you can find collisions by the birthday paradox. In the second case, $m$ is not very small, and $2^m$ is too large to be considered feasible. This argument is obvious in the concrete setting (consider $m=64$; this is ridiculously small and collisions can be found in just $2^{32}$ time, but a message of $2^{64}$ size is not feasible).

Asymptotically, the same argument can be made. In order for the function to be collision resistant, you must have $m=\omega(\log n)$, where $n$ is the security parameter.  This is necessary since otherwise $\sqrt{2^m} = \sqrt{n}$ which is very small (in particular, it's polynomial). Otherwise, just to be concrete, consider $m=\log n\log\log n$. In this case $2^m = 2^{\log n\log\log n} = n^{\log n}$, which is not polynomial. However, this means that it's not possible to run the function with an input of length $2^m$.


Is PKCS #1 v1.5 RSA encryption padding secure under these conditions?

Though Bob may potentially delay his response by one year or more, the attacker may probably assume that, in practice, Bob will respond rather promptly. Thus, an active attacker can infer from Bob's response, or lack thereof, whether decryption occurred or not. This is a setup where Bleichenbacher's attack seems to apply.

However, one must take the fine print into account: Bleichenbacher's attack works by knowing whether, upon decryption, Bob found a seemingly correct padding, i.e. one that begins with the two bytes 0x00 0x02. When Bob finds that padding, he will then extract the "message" by removing the leading non-zero bytes (after the 0x02), which are supposed to be random padding bytes, as per PKCS#1 specification. In the case of Bleichenbacher's attack, the message will then be random junk.

If your setup is exactly the following:

Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
otherwise, Bob always respond, possibly with a "Alice, you sent me random junk";

Then Bleichenbacher's attack applies.

However, if Bob does the following:

Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
if the message, after padding removal, does not make any sense, then Bob does not respond;
otherwise, Bob always responds;

Then Bleichenbacher's attack may be thwarted, or not, depending on the exact notion of "make sense". For instance, if Bob expects each message to have the format m||SHA-1(m) (concatenation of the message itself and its hash with SHA-1), and won't respond if the hash does not match, then Bleichenbacher's attack won't be feasible.

Note that I do not claim that PKCS#1 v1.5 is secure. To my knowledge, we have no proof of security of PKCS#1 except the usual criterion: the scheme has been widely used from quite some time, and Bleichenbacher's attack is the best attack that has been found. So far.


Where is the password hash calculated, locally on or the server?

I can imagine a protocol like this, where $n$ starts from a high value, and gets decremented by the server at each login attempt. Characteristically:

The system has a degree of resistance against passive eavesdropping, which is no more susceptible to password search than server-side iterated hash is should the hashed password leak. That's a significant security benefit (especially if the client implements a minimum on $n$, which at least prevents a Man-in-the-Middle to find the password without heavy search; beware however that it does not prevent the MitM from obtaining a hash allowing to log-in many times).
The server can verify the password with one hash (or $k+1$ hashes if there has been $k$ consecutive failed logins). The bulk of the password hashing work is on the client side, which is a benefit for the server.
As long as $n$ remains high, and salt is used (there's none in the question), leak of the password database is no worse than in a normal system with hash on the server.

I have never seen this used. Main problem is, there's no support in browsers, thus the code doing the hashing on the client side will be JavaScript (for acceptability by users/prescriber), thus

that code is at best authenticated using https, and then there is little security benefit compared to password in clear over https, which is the norm.
JavaScript is sizably less efficient than native (the difference used to be huge, and still is on many platforms/devices), and the number of iterations much be chosen low enough to be acceptable on the less efficient platform.

About the same issues have killed all attempts to use PAKE that I have seen.

Also, the question's system is not really immune against active attackers able to impersonate the server, which is a serious drawback compared to some other PAKE. And password search is still possible from passive eavesdropping, which other PAKE manage to avoid.


You normally want to use a fully invertible padding scheme, i.e. a padding scheme with an associated unpadding scheme such that $unpad(pad(X)) = X$ for every $X$.

Assuming you only append data at the end, and don't do different things depending on the content of the message, this means that you always have to append something, even if the message is already of the right length.

In your scheme, in the case of a message which has already the length of a multiple of the block length, you'll have to append a full block ending with a 16 (assuming a 16-byte block cipher like AES).
Your unpadding function then reads the last byte, and knows it has to strip off 16 bytes.

You shouldn't do any special-casing with a block of a certain structure only in the case of a full block appended.

But note that you should preferably use standardized schemes to help interoperability - for example PKCS#7-padding works just like your scheme, but with a bit different filling of the padded data. (This, just like your scheme, requires that the number of appended bytes is encodable in a byte, i.e. a block size of less than 256 bytes = 2048 bits. I'm not aware of any common block cipher with a larger block size, but you would need a different padding scheme in this case.)


Explanations for the complexity values for second preimage attack on GOST?

Preliminary: Almost the same article is available for free without breaking any law, nor downloading 5GB (formatting is shifted by at most one third of a page). It is also (as well as all other articles of IACR crypto conferences from 2000-2011) in the IACR Online Proceedings, specifically in the FSE 2008 section, but then you need to subtract about 223 from the page numbers quoted in the question to get the page number in the PDF. For this reason it is best to use section (rather than page) numbers to designate a section of an article.

I have now answered all the points (and learned along the way), but anyone remains welcome to improve that answer, made community wiki.

1) In section 3, why does the probability that two pairs lead to the corresponding values $x_1$, $x_2$, and $x_3$ amount to $2^{−192}$?

By construction, $x_i$, $y_i$, $z_i$, $s_i$ are 64-bit. We assume that the process that uncovered each pair, being independent of the relations $x_i=y_i\oplus z_i\oplus s_i$ for $i\in\{1,2,3\}$ (only concerned with that relation for $i=0$), makes each of these relations for $i\in\{1,2,3\}$ true with odds about $2^{-64}$; hence makes the three true with odds about $2^{-192}$ (again, without proof of independence).
That's typical in cryptanalysis: we assume odds that $a=b$ holds with odds $2^{-n}$ when $a$ and $b$ are $n$-bit with at least one of these quantity produced by a process that is engineered for a purpose independent of matching that relation, and that process's output or the other quantity has no clear bias. That probability would follow from assuming either quantities is uniformly distributed.

2) In section 4.1, how is $2^{128}$ used in the calculation of the complexity?

In section 4.1 it is considered a multicollision of $t=256$ message blocks, with for each block a pair of values that can be used interchangeably without changing the result in $H_{256}$:

For each of $t$ message blocks, the pair is found by the birthday attack on the output of $f$, which has $n=256$ bits, thus with about $2^{n/2}$ evaluations of $f$ using a technique such as Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications. Here comes the $2^{n/2}=2^{128}$ term!
The total cost of finding the multicollision is about $t\cdot2^{n/2}=2^{136}$. Notice that this is already totally impracticable in a foreseeable future: we are discussing a theoretical attack

3) In section 4.2, why construct $2^{32}$ pseudo-preimages for the last iteration of GOST?

That's a compromise between the work required in 4.2, which increases proportionally to the number $w$ of pseudo-preimages made; and the work required in 4.3, which decreases proportionally to $w$. The sum of work required for the two steps is thus of the form $a\cdot w+b/w$, and the minimum for that is for $w=\sqrt{b/a}$.
Here $a=2^{192}$, and $b=2^{256}$ (not quite in the same unit unless I err, but since this is a purely theoretical attack, that does not matter much), and it comes $w=2^{32}$ for the minimum.
In other words: one can change $2^{32}$ a little, the attack will still (theoretically) work. With an increase of that to say $2^{33}$, the expected work in 4.3 will be halved, but that's at the price of twice more work in 4.2, and twice more memory. Thus if we increase too much the work will be raised overall (dominated by 4.2), and if we decrease too much the work will be raised overall (dominated by 4.3). The value $2^{32}$ balances the work in 4.2 and 4.3, and is in the right ballpark for a minimum overall attack effort.

4) In section 4.3, how was the probability of finding the right $M_{257}$ in the list $L$ obtained?

The list $L$ contains $w=2^{32}$ pairs $(H,M)$ with $H$ of $n=256$ bits (distinct with high odds since $w\ll2^{n/2}$, under the standard assumption that the $H$ are random-like for reasons discussed in 1).
We want to find an $M_{257}$ that makes $H_{258}$ matching the $H$ of some $(H,M)$ in $L$. $H_{258}$ is next to uniformly distributed (no matter how we enumerate distinct $M_{257}$, because that's a design goal for $f$) thus each value tried has odds $2^{-n}$ to match any particular $H$ in the list, thus odds (only very slightly above) $2^{-n}\cdot w=2^{-224}$ to match one $H$ in the list, and that's the probability we wanted.
That part of the attack alone is expected to require trying $2^{224}$ values of $M_{257}$, thus $2^{225}$ evaluations of $f$, and that's also the stated cost of the attack: at this degree of impracticality, it is common to consider $u+v\approx u$ whenever $v<u$ and we repeat such approximation only a few times.

5) What operation is referred to by the $\boxminus$ symbol?

Indeed, $\boxminus$ (written $\boxminus$ on this website) is used in this article for subtraction modulo $2^{256}$. That is quite clear in the context of use of section 4.3 of the paper, given the definition of $\boxplus$ ($\boxplus$) in section 2 as addition modulo $2^{256}$. Note: to determine how to render a symbol in $\TeX$, I often try a detexifyer, and in that case it worked.

6) In Section 3, why does the system of equations with $5⋅64$ equations in $8⋅64$ variables results in $2^{192}$ solutions?

A linear system of $x$ linearly independent equations in $y>x$ variables is under-determined, and $y-x$ variables can be fixed to any value. If these are binary variables, that leads to $2^{y-x}$ solutions. We obtain $2^{192}$ as $2^{8⋅64-5⋅64}$.
The same occurs when solving the system of equations with $6⋅64$ equations in $8⋅64$ variables leading to $2^{128}$ solutions: we obtain $2^{128}$ as $2^{8⋅64-6⋅64}$.


How many bits shift is a TEA encryption?

TEA is neither considered a 4-bit nor 5-bit algorithm (these are not categorized by their shift count). TEA:

Is a 64-bit block cipher, meaning encrypt modifies 64 bits: the block is v[0] v[1] and the code shown (non-portably) assumes unsigned long is 32-bit.
Has a 128-bit key k[0] k[1] k[2] k[3] ; notice that each key has 3 other equivalent ones (obtained by complementing the high-order bits of even or/and odd numbered words), thus key is effectively 126-bit.
Performs 32 double rounds, with in each double round (focusing on shifts because that's asked) two left shifts by 4 bits and two right shifts by 5 bits (on a 32-bit quantity). That's 128 shifts on a machine with a 32-bit barrel shifter, and 5760 shifts with a 32-bit ALU without barrel shifter.

Addition: the only two common reasons to count the shifts in an algorithm are:

Determine how much computational effort is spent on that, to predict how the CPU influences the performance. Continuing on that track: on 8-bit CPU, 32-bit shifts are quite expensive, and naive code with likely have 23040 shift instructions executed per bloc encrypted, with shifting representing I guess like 3/4 of the effort. In assembly language at least, it is possible to do significantly better by realizing that most bits of v1>>5 can be obtained as ((v1<<4)>>8)>>1, with the shift by 8 efficient on an 8-bit CPU. Also, many 8-bit CPUs have an instruction that swaps the halves of an octet, and might be put to use for the shift by 4.
Determining is there's enough diffusion. In TEA, it is used shift rather than rotations (largely because there is no built-in rotation in the C language, and building one would have made at least the source code more complex), and therefore diffusion across bits of the 32 ranks in 32-bit words is mostly by shifting (exclusively so for right diffusion, and with carry propagation contributing slightly to left diffusion). Full diffusion requires about 8 rounds, and that is significantly slower than say in DES, which diffuses I'd say more than twice faster. That's one of several reasons TEA must have a lot of rounds (64 rounds versus 16 in DES).


The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm.

If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher and Silverman. Sadly, the Wikipedia article about it is of quite low quality.


What affect does the permutation layer have on the avalanche effect?

Permutation layer diffuses the small changes globally(tries to spread over the complete block).

If permutation is not well thought out, then diffusion may be weak and changes may not spread throughout the complete block. The cipher output may be treated as concatenation of output from multiple identical ciphers with smaller block length. For Example

Consider there is no Shift-Rows operation in AES, then Change in a state will stay in a Column and will not diffuse to other columns. Thus Ciphertext can be treated as output of 4 independent 32 bit block ciphers.

In Case of PRESENT, if the permutation P was not spread over the complete block(64 bits, keeping the change within small set of bits), or there was a chunk of bits which does not get effected by change in other bits over multiple rounds, the cipher will have a major weakness.


What place do prime numbers have in cryptography?

No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications.

You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private keys must be related, but not in an obvious way.  What means that whatever scheme is used has some mathematical structure.  Number theory is a place where we find 'related-but-not-in-an-obvious-way' mathematical structures, and primes are rather, err, primary in number theory.

Exactly how the primes are used depends on which asymmetric algorithm is used; in RSA, we exploit the fact that, given $M^e \mod N$ (and $e$ and $N$), there's no known way to recover $M$ without knowing the prime factors of $N$ (but with that information, it's easy).  In DH/DSS, we exploit the fact that, given $G^x \mod p$ (and $G$ and $p$), there's no known way to recover $x$ (and we have $p$ be a prime because the problem with composite moduli becomes a lot easier if someone finds the factorization).  In Elliptic Curve Cryptography, we exploit the difficulty of recovery $k$ given $kG$ (where $G$ is a known point); a prime is involved because Elliptic Curves are defined only a field, and the only finite fields (that is, fields with a bounded set of elements) have size $p^N$, for prime $p$ (and positive integer $N$).

Now, you occasionally see primes used in symmetric crypto; it's not nearly as common (and those primes aren't secret).


If H1 becomes known then the first part of H3 becomes known if you just concatenate, so that's not a good option.

A simple XOR could work as long as H2 remains secret to an attacker. However, if info about H3 can be retrieved by an attacker and H1 can be changed then the attacker can force H3 to a certain value. But XOR doesn't expand the hash value as you seem to require.

If H1 and H2 are hashed together, e.g. with a larger output hash then all the attacker can do is to try and change H1 until some kind of structure appears in H3. This is the best thing to do if you just rely on hash functions.

You state that you don't require a KDF because you're not dealing with passwords. This is however not a good argument; there are also KBKDF's that derive output key material from input key material (and do not deal with passwords).

HKDF is a KDF that does this: it takes input key material, extracts the entropy from H1 and H2 into a certain intermediate key material, and finally expands the key material to the requested size. So the most fireproof way of creating H3 is: H3 = HKDF(enc(H1, H2), "H3", outsize). Optionally you can also supply a salt or change the label ("H3") to create different output values. enc is an encoding of the values H1 and H2, it can be just concatenation if the size of H1 and H2 can never change.

HKDF just relies on HMAC, and HMAC just relies on a secure hash function. So it can generally be implemented even if it is not directly available.

But just SHA-512 will also work.


Decrypting AES256-CBC with wrong encryption key

Yes, that's correct, decrypting altered ciphertext data or data with the wrong key may result in the wrong plaintext without producing an error. Actually, the chance is slightly more than 1/256.

First of all, we need to assume that the data is still a multiple of the block size. If it isn't then it won't decrypt at all.
Furthermore, if the key is correct and the last (and the last few bytes of the first-to-last) ciphertext block are correct then the decryption will not fail, even though the resulting data in the first blocks may be incorrect.
If the data is a multiple of the block size then the AES-CBC decryption will never fail. However, OpenSSL uses PKCS#7 padding by default - that is if the high level EVP functions are used instead of the lower level AES functionality. That means that the plaintext data is always padded before being encrypted, even if the data is a multiple of the block size. This is also true for the command line interface of OpenSSL by the way.

During PKCS#7 unpadding there is a 1/256 chance that the decryption of the last block ends with 01 if the key is incorrect or if the last ciphertext block is incorrect.
However, there is also the chance that the last block ends with 02 02 which is also valid padding. The chance of this happening is however just 1/65536 so it is almost negligible compared to the chance that the last decrypted block ends with 01. This is even more true for 03 03 03, 04 04 04 04 of course. As padding / unpadding must always be performed according to PKCS#7 the chance that a random ciphertext block is accepted is therefore close to 1/256.

An adversary can always change any ciphertext block up to the last as the error propagation properties of CBC are limited to the current block and (part of) the next block. You need to authenticate the ciphertext to avoid this and to avoid padding oracle attacks where those are applicable. For that, calculate a HMAC over the IV and ciphertext or to switch mode to e.g. GCM and perform the necessary verification before decryption.


Calculate all possible keys for AES 128 encryption to exploit hardware encryption

Is this attack plausible using a modern PC?

No. For AES-128 (or any secure 128-bit symmetric cipher for that matter), there are $2^{128}$ possible keys. You would have to try on average half of those keys before finding the right one, which is $2^{128}/2=2^{127}$. At $100,000,000$ attempts per second (or around $2^{26}$), it would take around $2^{101}$ second. The universe is around 13.7 billion years old (about $2^{59}$ seconds). So the amount of time it would take you is $2^{42}$ times the age of the universe.

There are other ways you can calculate this, but the end result is the same. See How much would it cost in U.S. dollars to brute force a 256 bit key in a year?.

Finally, the relevant XKCD:


Why use IV like this in TLS 1.2 record layer AES-SHA block cipher?

I am curious why do we use IV like that. Why not derive IV in the key expansion and use it again again?

Repeating IVs is bad, both for CBC and GCM.  And, no, keeping the repeated IV secret from the adversary doesn't help.

  If we use it like above, the IV will be public to anybody.

Well, yes.  IVs do not need to be secret; we don't mind if an adversary hears them.

  Is it right that the recipient should use the IV to decode block-ciphered struct?

Yes.  In CBC mode, the IV is directly used as the CBC-mode IV input (effectively, as the "previous ciphertext block" to decrypt the first ciphertext block).  In GCM mode, it is combined with 4 bytes from the key expansion to generate a 12 byte nonce, which is used as the GCM-mode nonce input.


Relation between key size and PRNG state size

Your intuition is correct.

While more bits of entropy is better when generating a key, attacking RSA through the key generation process is an independent attack of factoring the modulus, and is predicated on a different computational hardness assumption, search of the keyspace compared to the hidden subgroup problem for finite Abelian groups (for factoring or discrete logarithm.) Factoring at least seems subexponential but superpolynomial, so is significantly easier than search; Many search problems appear to be NP hard, with exponential time complexity in the average case.

The attack on the key generation process depends on the cryptographic strength of the PRNG, and is analogous to attacking a symmetric ciphers in many ways. Since the attacks against PRNG's are so similar to attacks against symmetric ciphers, you can use the guides at keylength for symmetric ciphers as guides to the minimum state for key generation as its entirely appropriate. If you're using RSA for key exchange, and your symmetric key length is smaller than the key length of your PRNG seed, they won't bother attacking the key generation process.

The question does highlight a very important concern about prudent cryptography however, and that is that key generation is highly vulnerable to attack by poor implementation. A cryptographically secure PRNG is essential if using a PRNG for key generation.


Is there a hash function which has no collisions?

Your hypothetical hash function would need to have an output length at least equal to the input length to satisfy your conditions, so it wouldn't be a hash function. See the Pigeonhole principle.

Remember an n-bit hash function is a function from $\{0,1\}^∗$ to $\{0,1\}^n$, no such function can meet both of your conditions. Essentially, if it has length $n$ bits, it can only guarantee uniqueness for inputs up to $n$ bits, and even then it would not be a good PRF as it would be a permutation - which is not what hash functions are - so you would want the output size to be longer than the input size, which is now really far from the definition of a hash function.

Now, if you are willing to call it something else than a hash function, then, yes, it is possible to construct such primitives, under the assumption that the output length must be calculated in a way that if there are $m$ possible inputs for an $n$-bit output, then $m \leq 2^n$. The obvious one is a block cipher, which satisfies your conditions except that it has the additional property that all outputs have a corresponding input, which may not be what you want.

As you can see, if you don't want a permutation, you are basically left with a function which "expands" the input pseudorandomly, such that all inputs have outputs but not all outputs have inputs. For instance, CodesInChaos's example of $y = g^x \mod{p}$ is collision-free if $|X| \leq p$ where $X$ is the set of inputs to the function and is one-way for sufficiently large prime $p$ (actually, it needs to have a subgroup of large order, generally $p = 2q + 1$ is a common choice for large prime $q$), as you would need to solve the discrete logarithm problem to reverse it.


Why was there a need to create CP-ABE when KP-ABE already exist?

I think you may find the founding paper of CP-ABE pretty informative on that regard: in "Ciphertext-Policy Attribute-Based Encryption" by Bethencourt et al. you can read the following:

  In key-policy attribute based encryption, ciphertexts are associated with sets of descriptive attributes, and users’ keys are associated with policies
  (the reverse of our situation). We stress that in key policy ABE, the encryptor exerts no control over who has access to the data she encrypts, except by her choice of descriptive attributes for the data. Rather, she must trust that the key-issuer issues the appropriate keys to grant or deny access to the appropriate users. [... ] In our setting, the encryptor must be able to intelligently decide who should or should not have access to the data that she encrypts.

It's basically two different methods to achieve the same kind of goal, ie "Attribute Base Encrpytion".

You may further find this answer pretty useful and that question may also help you.


Can a 3rd party decrypt static Diffie Hellman?

I am wondering if static DH allows for the same sequence of 3rd party decryption as RSA?

Yes, if a third party learns the server's (or the client's) DH private value, they can recover the DH shared secret, and thus recover the premaster secret, the master secret and thus the traffic keys.

This is true for both static and ephemeral DH.  Of course, with ephemeral DH, both sides are supposed to discard their private values immediately after using it (and thus the window of opportunity for the attacker is less).  With static DH, this is obviously not possible (as the server will use the same DH private value for the next negotiation).


Why is proving "parties' views are simulatable" enough in semi-honest model?

I am having a hard time understanding your argument why you think this could be simulated. However, here is an explanation of why it could not.

Assume Bob is honest and has input $y$, now we have to simulate the view of Alice. As the simulator, as you state, we only get the input and output of Alice. I.e, we only know $x$ and $f(x,y)$. We only need to simulate the one message in Alices view, i.e., the first message where Bob sends $y$ to Alice. Since we do not know $y$ the best we can do is to randomly guess at some $y'$. Now the probability that $y' \neq y$ is going to be high, so the simulation is going to be clearly distinguishable from the view of Alice.

What might be confusing you is that, when we do the simulation we do not know the inputs of the honest parties. But when we try to distinguish the real view from the simulation we know all the inputs.


Yes, in the random oracle model, the hash of a BLS signature makes a VRF essentially as secure as the BLS signature scheme (provided the verifier accepts only the unique canonical encoding of each signature).

This works because BLS signatures are unique.  Fix a pairing $e\colon G_1 \times G_2 \to G_T$ on groups $G_1$ and $G_2$ of prime order.  For any fixed $A \in G_2$, the homomorphism $\phi_A\colon \sigma \to e(\sigma, A)$ is an injection (or the system is trivially insecure) because $G_1$ has prime order.  Let $B \in G_2$ be the standard base point.  A putative signature $\sigma \in G_1$ under public key $P \in G_2$ on a message $m$ satisfies the signature equation $$e(H(m),P) = e(\sigma,B) = \phi_B(\sigma).$$  Since $\phi_B$ is an injection, there is at most one possible signature $\sigma$ for any public key $P$ and any message $m$.


Is AES_CMAC specified to double ciphered zeroes during initialization?

Do I have to do all the "zero" stuff and doubling and XORing?

If you are implementing the S2V primitive, using an AES-CMAC function, then yes, you will need to do all that "zero" stuff and doubling and XORing.

Yes, if you peek inside the AES-CMAC function, you will find some logic that looks sort of like this; processing an all zero block, doubling the result, and doing some xor's with it.  However, CMAC is doing something a bit different with it (the result of the processed 0 block goes at the end of the chain, not at the beginning), and in any case, the S2V primitive assumes the CMAC logic as a primitive; what CMAC does internally is actually irrelevant to how to implement S2V.

  Would that mean, that AES-CMAC(key, plaintext) is equivalent to S2V(key, plaintext)?

No, if you look at the RFC, then the S2V of a vector that consists of a single plaintext (remember, S2V takes a vector of plaintexts) would be either:

AES-CMAC( key, plaintext XOR AES( key, 0 )) (for plaintexts >= 128 bits; the xor applies to the end of the plaintext), or
AES-CMAC( key, PAD(plainext) XOR double(AES( key, 0 ))) (for plaintexts < 128 bits).


Zero-knowledge proof for committing a choice?

Below is one possibility, but for a large set of values not a really efficient one as the work and the size is linear in the number of values. I additionally added a variant where the work and proof size is constant.

Standard OR Proof

Say we are working in a cyclic multiplicative group $G$ of prime order $p$ with generators $g$ and $h$ (such that the discrete logarithm between $g$ and $h$ is unknown to the users) and I assume that the values on the list (values $v_i$'s) are elements of $Z_p^*$ (e.g., by hashing the choices if they have a larger representation than values in $Z_p^*$ using a secure hash function).

You could publish an authentic list $(v_1,\ldots,v_{100})$ so everyone can check that these choices are indeed the possible choices or just give it to your users if you want to be the only one verifying the choices of the users.

Then, if a user chooses one out of the 100 possibilities, say $v_i$, the user computes an unconditionally hiding commitment to one of your choices (such that even knowning the 100 choices one cannot figure out which value is hidden in the commitment) as $H=g^{v_i}h^r$ for random $r\in Z_p^*$ (here by using a Pedersen commitment). In addition to $H$ the user publishes a non-interactive honest-verifier zero-knowledge proof of knowledge $\pi$ that the value in his commitment $H$ is equal to one of the values in the list. More precisely, with $\pi$ one proves the statement $$PoK\{(\beta):H=g^{v_1}h^\beta \vee H=g^{v_2}h^\beta \vee \ldots \vee H=g^{v_{100}}h^\beta\}$$ where this is a standard OR composition of discrete logarithm proofs and made non-interactive using the Fiat-Shamir heuristic.

So the user publishes the pair $(H,\pi)$ which convinces any verifier that the prover knows a secret value $r$ (the value $\beta$ in the proof, which is not revaled) such that his commitment $H$ is a commitment to one of the values $(v_1,\ldots,v_{100})$ without revealing which one.

If the user later on wants to open the commitment (reveal the choice) he publishes $(v_i,r)$ and everyone can check whether $H=g^{v_i}h^r$.

Efficient Set Membership Proof

In the above proof, the cost for the prover is $O(n)$ where $n$ is the cardinality of the set of values. You could also use the approach in this paper, which requires the publisher of the list to compute a (Boneh-Boyen) signature to each of the values of the list, i.e., costs of $O(n)$, but the cost for the proof is only $O(1)$, i.e., the prover computes a commitment and proves that he knows a value that has been signed, which can be efficiently done when using Boneh-Boyen signatures. The proof can also be made non-interactive using the Fiat-Shamir heuristic.


substract points on secp256k - result as moved to N-1

How to check that substract points cross the order of curve n?

You cant'; or at least, we hope you can't.
If you could, you could use that method to compute discrete logs.
Here is one approach; suppose you had a method that, given the points $[a]G$ and $[b]G$, would return you $[a-b]G$ and also informed you whether it "crossed the order of curve n", that is, if $a < b$.  Then, what you could do, given the point $[x]G$, you could use this method on the points $[x]G$ and $[\lfloor n/2 \rfloor]G$; that method would tell you if $x < \lfloor n/2 \rfloor$.  If it turned out (for example) if $x$ happened to be larger, you could repeat this with $[x]G$ and $[\lfloor 3n/5 \rfloor]G$; and continue to do binary searching until you have recovered the value of $x$.
That means that you've just recovered the discrete log of $xG$ with only circa $\log_2(n)$ calls to your method; we certainly hope that we can't do that.
BTW: why do you care if "the points cross the order of curve n"?


Following CodesInChaos request to turn the hint into a full solution, here's a full solution. Let $x$ and $y$ be square roots of $51733469$ modulo $n$. It follows that

$$0\equiv x^2-y^2=(x+y)(x-y)\,(\textrm{mod }n).$$

If we choose $x\not\equiv \pm y\, (\textrm{mod }n)$, then $x-y$ and $x+y$ are not divisible by $n$. On the other hand, $n\mid (x+y)(x-y)$, so $\gcd(x+y,n)\neq 1\neq \gcd(x-y,n)$. Choosing for instance $x = 38191887$ and $y=22222$ gives

$$\gcd(x-y,n) = 8887,\;\; \gcd(x+y,n)=9949.$$

A direct computation shows that $n=88416763 = 8887\times 9949$. It's easy to use the Sieve of Eratosthenes to calculate all primes smaller than $100$ and then check if any of them divide either factor, which will show that $8887$ and $9949$ are both prime.


Noise of ciphertexts in LWE/RLWE based FHE

This is because of the decryption equation: If two ciphertexts differ ($\mathbb{Z}$-component-wise..., not homomorphically) in a multiple of $q$, they both decrypt to the same thing because of the modular reduction. Therefore, upon reception of a 'big' ciphertext, it makes sense to take modular reduction of this ciphertext and then look at its noise. Conversely, to cheat silly attackers one could add 'false noise' in this fashion (severely augmenting ciphertext size, however)


Partition attack on the possible values of RSA modulus

But I don't see a good reason for the second.

One requirement for RSA is that, if $p, q$ are the prime factors of $N$, then $p-1, q-1$ must be relatively prime to $e$ (if this is not true, then it becomes impossible to uniquely decrypt, as $gcd(e,\phi(N)) \ne 1$).  Now, if $e=3$, that means that $p \not\equiv 1 \bmod 3$ (and $q \not\equiv 1 \bmod 3$).  And, since $p, q$ are prime (and presumably greater than 3), we have $p \not\equiv 0 \bmod e$, $q \not\equiv 0 \bmod 3$.  That leaves, as the only alternative, $p \equiv q \equiv 2 \bmod 3$.

And, multiplying two values which are both 2 (modulo 3) together gives a value which is 1 (modulo 3).  That is, if $N \not\equiv 1 \bmod 3$, then $N$ cannot be a two factor modulus that works with $e=3$

  Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?

My guess would be that Serge miscalculated here (however, his main point holds).  The first criteria (top and bottom bit must both be 1) eliminates $\frac{3}{4}$ of the possibilities.  As for the second point (which is independent), I suspect that they assumed that eliminating the $N=2 \bmod 3$ possibilities removed another half (and they they forgot about the $N=0 \bmod 3$ possibility); that miscomputation would have them eliminating $1 - (1 - \frac{3}{4})(1 - \frac{1}{2}) = \frac{7}{8}$.  However, if we recognize that $N=0 \bmod 3$ would be possible on an incorrect guess (and can also be eliminated), that means that step 2 eliminates $\frac{2}{3}$ of the possibilities (as you noted); that gives us an aggregate of $1 - (1 - \frac{3}{4})(1 - \frac{2}{3}) = \frac{11}{12}$ of the incorrect possibilities (and so the result is actually stronger than originally claimed).


If you want to unhide a random message you need your own proper tools.
If you want to unhide a message sent to you then you need to use the tools that the sender used.
Expecting random tools to work on a random message is nonsense even if you might get lucky once.


Formal Verification of DHKE protocol using ProVerif

I think it's because par1 and par2 start "out".
As you know, a client will start to send message to the server first. And after do thart, the server will receive the message.
It seems that it's probably possible to fine if your code in one of them code is fixed like below.

let par1 = out(..);
                  in(..);

let par2 = in(..);
                  out(..);


Does AES encryption of a NTRU pivate key reduce security?

No, 128-bit NTRU private key will retain its security when encrypted by AES-256 using a properly generated/derived key.

Suppose 2 ciphertexts, 1 NTRU, 1 IES-ECC, both are 128-bit secure, what you have right now is 2 ciphertexts requiring $2^{128}$ work to recover the plaintext without having the corresponding private key. This is true even if the encoded private key is longer than 128 bits (because of non-generic attacks such as lattice-reduction or Pollard's rho algorithm)

Now suppose the keys are encrypted with a 256-bit cipher, this doesn't reduce the security nor increase it. This is because one can always attempt recover the private key from the already known public key without attacking the encrypted private key anyway.


I'm assuming that you mean any time the file changes, it is re-encrypted with PGP. Here is a description of how PGP encryption works:

Whenever you change the file and re-encrypt with PGP, a new, independent session key is chosen. So what you end up with is a (potentially only slightly) modified file, being encrypted with a brand new session key.

All modern block ciphers, when used correctly, will protect against cryptanalysis, even when the analyst has access to multiple encryptions of the same (or slightly modified) plaintexts. Since PGP is generating a new, fresh, independent key, this would fall under the category of when used correctly. So, no, an attacker having access to all these encrypted versions gains no advantage in breaking the plaintext or the keys.


A key derivation function (KDF) takes in some secret keying material, which may or may not be uniformly distributed, and where the adversary may also have some auxiliary information about the keying material or its distribution, and outputs a uniformly distributed bit string. See definitions 5, 6, and 7, here.

Intuitively, a KDF's job is to take in some keying material which has some minimum entropy, but which might not be uniform as a bit string (or not be a bit string at all!), and output a "smooth" bit string of essentially the same entropy as the original input. A classic use case is a Diffie-Hellman (DH) secret obtained from a key exchange protocol. This secret is not a bit string, but rather a group element. Moreover, when encoded as a bit string, this group element will not be uniformly distributed over all bit strings of the corresponding length. However, it does have high entropy, and a KDF can then be used to extract from the secret DH group element a nice and uniformly distributed bit string (i.e., a symmetric key).

The security definition of a KDF (Def. 7 in the link above), is essentially that it should behave like a random function when evaluated on the secret keying material and some arbitrary additional input (there are some additional bells and whistles in Def. 7 provided in the link, but what I said contains the gist of it).
A pseudorandom function (PRF) takes in a secret key and a message, and outputs a bit string. The security requirement for a PRF (see Def. 5.6, here) is that it should behave like a random function when evaluated on arbitrary messages---provided the secret key is uniformly distributed.

Notice that PRFs and KDFs are quite similar, but that a PRF has a much more stringent requirement on its secret key. Essentially, a non-uniformly distributed secret key voids all security guarantees of a PRF.
A message authentication code (MAC) takes in a secret key and a message, and outputs a tag. There is also a corresponding verification algorithm that on input the secret key, a message, and a tag, outputs either VALID/NOT-VALID. The security requirement of a MAC is that for someone not knowing the secret key, it should be hard to come up with a message and a tag, such that the verification algorithm outputs VALID. (Note that this is a very weak form of MAC security, and usually we require something stronger called EUF-CMA security, see Def. 9.1 and Def. 9.2 here).

As for the relationships between them, it follows from what I wrote above that KDF $\implies$ PRF $\implies$ MAC. That is, since a KDF is supposed to behave like a random function even when given a non-uniform secret key, it of course also behaves like a random function when the secret key is uniformly distributed. That a PRF allows you to build a MAC is shown in Section 9.6 here.

In the other direction none of the implications hold generally. That is, it is not the case that all secure MACs are secure PRFs (can you think of a counterexample?), and not all secure PRFs are secure KDFs.


RSA - Finding all possible encryption exponents

We know that $\varphi(x) \ge\sqrt{\frac{x}{2}}$. The size of $\varphi(n)$ is roughly the same of $n$, so $\varphi(\varphi(n))-1$ is still a intractably large number. This means finding all possible e's is infeasible because there are too many. No matter what algorithm you use, there is no way you can find all of them in polynomial time (in the security parameter).


BOOLEAN FUNCTIONS: generate a function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ from a $n \times n$ S-Box

Your n x n S-Box can be seen as a set of $ n $ boolean vectors of size $ n $. Actually you have got $ n $ functions, each one is the truth table of one particular vector (or column).
In your example there are 2 columns thus 2 functions. For each column the number of 1's is 2.


How to prove the hardness of Rabin's function?

Let $\mathcal A$ be the hypothetical algorithm in the question, with input $(n,q)$, output $r$, such that $r^2\equiv q\pmod n$ for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$, running in random polynomial time w.r.t. $\log(n)$, restricting to $n$ product of two large distinct primes.

Let $\mathcal F$ be the following algorithm with input $n$ restricted as above, and output $d$:

select a random $s$ evenly distributed on $\{1\dots n-1\}$;
compute $q=s^2\bmod n$;
compute $r=\mathcal A(n,q)$; if algorithm $\mathcal A$ gives an indication of failure, loop at 1;
compute $d=\gcd(n,r+s)$ and if $d=1$ or $d=n$, loop at 1;
output $d$.

This factors $n$ because

Given that factors of $n$ are large, the proportion of $q$ that share a factor with $n$ is so low that they can't constitute a significant share of the $1/(\log(n))$ success rate of algorithm $\mathcal A$ over the whole set of $q$, thus the success rate of $\mathcal A$ is near $1/(\log(n))$ including for other $q$.
When step 2 of algorithm $\mathcal F$ invokes $\mathcal A$ with $q$ coprime with $n$ (that is on iterations with $s$ coprime with $n$, which are the vast majority), $q$ is evenly distributed over these other $q$, hence $\mathcal A$ will succeed with odds next to $1/(\log(n))$.
When $\mathcal A$ succeeds with $q$ coprime with $n$, and since $n$ has two factors, there are four square roots of $q$; since $s$ is random and was not an input of $\mathcal A$, which root $r$ was output by $\mathcal A$ is independent of which root $s$ is. For two out of these four possible $s$, thus with odds $1/2$, step 4 will compute a $d$ that is a nontrivial factor of $n$.

This proves that for $n$ as restricted of unknown factorization, inverting $r\to q=r^2\bmod n$ for random $r$ (or random $q$) is of hardness comparable to factorization of $n$.

Detailed proof with explicit bound on how large the factors of $n$ need be:

Let $p_1$ and $p_2$ be the two large (thus odd) distinct primes with $n=p_1p_2$. The $n-1$ possible values of $s$ can be split into two categories, which together form the whole set of quadratic residues $q$:

$p_1+p_2-1$ values with $\gcd(n,s)\ne1$, which generate $(p_1+p_2-2)/2$ quadratic residues $q$ with $\gcd(n,q)=1$,
$(p_1-1)(p_2-1)$ values with $\gcd(n,s)\ne1$, which generate $(p_1-1)(p_2-1)/4$ quadratic residues $q$ with $\gcd(n,q)\ne1$.

That gives us a total of $(p_1+1)(p_2+1)/4-1$ quadratic residues $q$. Algorithm $\mathcal A$ succeeds for at least an $1/(\log(n))$ fraction of this total, among which at least $((p_1+1)(p_2+1)/4-1)/\log n-(p_1+p_2-2)/2$ values of $q$ in the second category.
We can assume $\min(p_1,p_2)>4\log(n)$ (noticing that otherwise trial division would factor $n$ in polynomial time w.r.t. $\log(n)$ anyway). With that bound and even distribution of $s$, $\gcd(n,q)\ne1$ and $q$ is among those for which $\mathcal A$ succeeds for at least an $1/(2\log(n))$ fraction of $s$.
When this happens, we have $r^2\equiv q\equiv s^2\pmod n$, thus $(r-s)(r+s)\equiv0\pmod n$, thus $(r-s)(r+s)\equiv0\pmod{p_1}$ and $(r-s)(r+s)\equiv0\pmod{p_2}$, thus $r-s\equiv0\pmod{p_1}$ or $r+s\equiv0\pmod{p_1}$, and $r-s\equiv0\pmod{p_2}$ or $r+s\equiv0\pmod{p_2}$.
When this happens, $\mathcal A$ has worked without knowing $s$ randomly chosen at step 1; hence each of the four $s$ possible for the $q$ handed to $\mathcal A$ is equally likely, and with odds $1/4$ we have $r+s\equiv0\pmod{p_1}$ and $r+s\not\equiv0\pmod{p_2}$, thus $d=p_1$ at step 4; and with odds $1/4$ we have $r+s\not\equiv0\pmod{p_1}$ and $r+s\equiv0\pmod{p_2}$, thus $d=p_2$ at step 4.
It follows that algorithm $\mathcal F$ is expected to reach the final step 5 after no more than $\mathcal O(4\log(n))$ iterations, with each step of each iteration running in random polynomial time w.r.t. $\log(n)$; so the whole algorithm does, and outputs a factor of $n$, Q.E.D.


How are hash functions analyzed in an open competition?

To assert the security of a Cryptogaphic primitive, one usually uses differential cryptanalysis (that is the first tool but not the sole one).
From the report you can read:
1. Security

Grøstl and JH have differential properties that extend through most
or  all  of  the  rounds,  while  the  remaining  three  candidates  only  have  distinguishers that extend through about half of their rounds.

and also :

Keccak  received a  significant  amount  of  cryptanalysis,  although
not  quite  the  depth of  analysis applied to BLAKE, Grøstl, or Skein. This cryptanalysis left Keccak with a huge security margin –only five out of its 24 rounds has been broken by a near-collision attack. Keccak’s large security margin,  after  significant  cryptanalytic  effort,  suggests that  Keccak  will  remain  secure  in  the future.

The idea here is to have a kind of security feeling between the different kind of constructions. I was recently participating in the design of a new scheme, we were paying a really big attention to the constants we were choosing in order to avoid differentials (or even worse, iterative differentials)...
2. Speed and Hardware support
All the finalist have a the speed required, while the ARX designed scheme have the software advantage, using hardware instructions leads to even faster hashing. Thus Keccak being hardware friendly helped it to get the edge.

Keccak provides an excellent set of performance trade-offs – it is broadly competitive with SHA-2 in software, while providing much better throughput/area performance in hardware.

3. Scheme
Keccak also provide a new kind of scheme that is completely different to the usual Merkle–Damgård construction: the Sponge construction.
4. Conclusion

Keccak has a large security margin, good general performance, excellent efficiency in hardware implementations,  and  a  flexible  design.  Keccak  uses  a  new  “sponge  construction”  domain  extender,
which  is  based  on  a  fixed  permutation,  that  can  be
readily  adjusted  to  trade  generic security strength for throughput, and can generate larger or smaller hash outputs, as required. The
Keccak  designers  have  also  defined  a  modified  chaining  mode  for  Keccak  that  provides authenticated encryption.

TL;DR:
Lets say that you want to buy a new computer. You have $Computer_1$ and $Computer_2$ in front of you. Both have:

the same price,
the same CPU (speed),
the same RAM size (security),

but $Computer_2$ also provides you as a plus PCIe card support (sponge construction). You know that at the moment you don't need that PCIe support... Which one do you chose ? I get the feeling that you would go for the second one because you don't know what the future is made of and you will want to upgrade if possible later and that might use PCIe.


How to handle a lost key in Diffie-Hellman Key Exchange

You have to send the previously generated key securely and this is complicated and needs an additional protocol that you may not want.

Otherwise, the key-exchange algorithm is randomized, and re-run will not produce the same key. Better is send a key-lost event, re-execute Diffie-Hellman and re-send the message.


Scheme to verify AES key was correctly encrypted for public key recipient

This would be possible by using textbook RSA, where the ciphertext is deterministic

You have the right idea there, that a deterministic scheme is the way to go. However note that every scheme is deterministic if you explicitly fix the randomness used.

So suppose you encrypt $k$ for $C$ as $c=\operatorname{Enc}_{\text{pk}_C}(k;r)$ using $C$'s public key and the randomness $r$. Now for the arbitration you give $k$ to $B$ who checks that the $k$ actually is the correct one. Then you have $C$ send the received $c$ (call it $c_C$) to $B$ and have $A$ send the sent $c$ (call it $c_A$) along with the randomness $r$ used for the encryption to $B$. You could possibly encrypt the randomness here using $B$'s public key. Then $B$ re-computes $c'=\operatorname{Enc}_{\text{pk}_C}(k;r)$ using the received randomness and its own known $k$ and checks whether $c'$ matches $c_A$ and $c_B$. If it matches at least $c_B$ then $A$ was honest (because then $B$ got the right key). If it only matches $c_A$ then either of $A$ or $B$ is lying but we don't know which, because $B$ could have produced its own ciphertext and sent it to $B$ or $A$ could have produced a correct ciphertext for $B$ but sent a bad one to $C$. I don't think there is a way to resolve this issue and find out who lied at the end.


Why is prime factorisation computationally intensive compared to normal factorisation?

The problem are not prime factors, the problem are large prime factors. There are many rather efficient factorization algorithms (such as Pollard's rho) that are good at finding small factors. Actually in RSA we want $p, q$ to be approximately of the same size so this disproportion cannot be leveraged to factor $p*q$.

If you have a $p, q$ primes then $p*q$ has only two factors, smallest one is equal to $p$ or $q$. If $p,q$ are composite then the smallest factor of $p*q$ is smaller (upper bound on the factor is only $min(\sqrt{p}, \sqrt{q})$). Thus using composite numbers reduces your problem to much smaller instance. Moreover if your numbers have really small factors (such as $2$) then the reduction is even more straightforward (e.g. I can decide to divide $3016$ by $8$ just by looking at binary representation of $3016$, then it remains to factor $377$ which is almost 10 times smaller).


Python library that implements additive homomorphism of Elgamal Encryption on the Elliptic curve i.e X25519 or P-256

We'll say that asymmetric encryption is homomorphic below $\ell$ when, given the public key and ciphertexts $C_i$ obtained from plaintexts assimilated to integers $a_i\in\mathbb N$ such that $\ell>\sum a_i$, it can be efficiently computed ciphertext $C$ that deciphers to $a=\sum a_i$.
The best known example is Pailler encryption, which when the secret primes are 1024‑bit is homomorphic below $2^{2046}$. That's more than ample for many applications, so the limit $\ell$ is typically unstated.
The question asks an equivalent using ElGamal encryption on a standard Elliptic Curve group such as X25519 or P-256, with the stated goals:

reduce the ciphertext size
"improve the encryption operation", which I take as making at least encryption faster.

Both are possible, but as far as I know that comes with a serious limitation: the cost of decryption¹ grows about as $\Theta(\sqrt a)$ where $a$ is the plaintext. That's thus not even a cipher by the modern definition of that, which would require cost polynomial in $\log a$. However the question is "only encrypting small integers (32bit)", thus that might be tolerable.
Using the notation in the definition of P-256 aka secp256r1 in SEC2, that variant of ElGamal encryption goes:

The curve has a generator $G$ forming an Elliptic Curve group of prime order $n$ with $\log_2(n)\approx256$
A point on the curve other than the neutral can be defined by it's $x$ coordinate in $[0,p)$ and the parity of it's $y$ coordinate, and fits 257 bits or 33 bytes.
The private key is a random secret integer $d$ drawn about uniformly randomly in $[1,n)$
The public key is the point $Q$ of the curve computed as $Q\gets d\,G$. Recall that this scalar multiplication on the Elliptic Curve gives the same $Q$ as would computing $\underbrace{G+G+\ldots+G}_{d\text{ terms}}$, but can be performed with $\approx512$ point additions in the Elliptic Curve group (refer to SEC1).
Encryption of integer $a\in [0,n)$ goes:

Draw a random secret integer $k$ about uniformly randomly in $[1,n)$
Compute $R\gets k\,G$ and $S\gets a\,G\,+\,k\,Q$.
Output ciphertext $(R,S)$ (it's like 66 bytes).

Decryption of ciphertext $(R,S)$ goes

Check that $R$ and $S$ are on the curve
Compute $A\gets (n-d)R\,+\,S$
Find integer $a\in [0,n)$ with $a\,G=A$.

It's easy to verify that

decryption (if we can manage it's last step) recovers the plaintext $a$;
if $a_i$ has enciphered to $(R_i,S_i)$, and $n>\sum a_i$, then $(\sum R_i,\sum S_i)$ [where the summations are point additions in the Elliptic Curve group] deciphers to $\sum a_i$ [where the summation is ordinary addition]: our modified ElGamal encryption is homomorphic below $n$.

I think security is somewhat reducible to some well-studied problem (is it DDH?).
The catch is: we don't know how to perform the last decryption step for cost¹ less than $\Theta(\sqrt a)$. For plaintext $a$ limited to 32-bit, Baby-Step/Giant-Step is probably the method of choice: it's simple; has predictable runtime; is straightforward to implement in pure Python on a standard PC if we brush aside resistance to side-channel attacks.
The whole endeavor is a useful exercise, and can be done from scratch in like a day for one with a good understanding of Elliptic Curve Cryptography, programming, and some exposition to Python. About half the work is implementation of the code doing point addition and multiplication, which exists in many open-source projects²
Difficulty grows sharply if we want a secure implementation, or acceptable speed for much larger $a$. For the later, we'd want Pollard's Rho with distinguished points, which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

¹ This is the cost for a single decryption, including precomputations. These precomputations can be performed before the ciphertext is available, and amortized across multiple decryptions, see poncho's comment.
² For NIST's P-256, P-384, P-521 curves, pycryptodome's EccPoint looks like it can be used without re-engineering the interface. This is not a recommendation: I've not used or reviewed that code. And from the perspective of learning crypto (rather than the joys and pitfalls of code reuse), it's better to implement that too.


Building a cryptography system by combining a block cipher and a stream cipher?

I should begin by noting that this seems like an unusual assignment. I'm not sure why someone would explicitly have a goal of combining block ciphers and stream ciphers.

First, let's summarize the difference between block and stream ciphers, since this may be useful for future readers.

Block ciphers are so called because they operate over fixed lengths of plaintext. A block cipher will accept only an input of a specific block size, for example, 16 or 32 bytes, and output the ciphertext block of that size. Because of this input size limitation, block ciphers are usually employed in certain modes of operation that allow a block cipher to accept a plaintext input of arbitrary length. Some naive modes of operation, such as Electronic Codebook Mode (ECB) are considered dangerous and broken. Other modes, such as Cipher Block Chaining Mode (CBC) and Counter Mode (CTR) are considered more secure, but each comes with its dangerous drawbacks. The finickiness of block cipher modes is a big reason why many cryptographers today prefer stream ciphers over block ciphers, since stream ciphers can accept inputs of arbitrary length without any additional engineering. Examples of block ciphers: AES, DES.
Stream ciphers can accept an input of arbitrary length. Most of the time, they operate via a keystream design: this means that a stream cipher is usually a CSPRNG (Cryptographically Secure Pseudorandom Number Generator) in disguise, with your encryption key simply acting as the initial seed for the pseudorandom number generator! The output of the pseudorandom generator is called the keystream. The stream cipher proceeds to XOR every byte from the keystream with its corresponding plaintext byte in order, thereby producing the ciphertext. Examples of stream ciphers: Salsa20, Rabbit, NORX (and RC4, which I should warn is considered dangerous and obsolete).

Solution 1: Building a stream cipher using a block cipher

I think one way of addressing this assignment would be to use AES, a block cipher, in counter (CTR) mode. This is because counter mode effectively transforms AES into a stream cipher. Here's how AES in CTR mode works:

Notice that:

The AES block input is actually composed of a nonce and a counter. Generally, the nonce is a constant that is only used once per AES encryption key. Reusing a nonce with the same key can be catastrophic. AES has a block size of 16 bytes: the nonce is usually 12 bytes long, leaving 4 bytes for the counter, which is incremented for every block.
After we encrypt the block, we then XOR the AES output with our actual corresponding plaintext block, thus obtaining our ciphertext. Notice how this is working like a stream cipher now! We used AES to generate a keystream, which we then XORed with our plaintext, exactly like stream ciphers would generally work.

By using AES in CTR mode, you are using a block cipher as a component of what is ultimately a stream cipher.

Solution 2: Stream cipher for encryption, block cipher for authentication

You could use a stream cipher, such as Salsa20, to encrypt your data, and then authenticate your encrypted data using a Message Authentication Code (MAC) primitive that is dependent on a block cipher, such as Poly1305-AES. That way, you'll have deployed a stream cipher for encryption and a block cipher for authentication.


What does it mean that a semi-honest adversary can look at the internal state of a controlled party?

Yes, this is what it means. A semi-honest adversary knows the entire state of each corrupted party, including its input, any random coin tosses, and all incoming messages from all other parties. However, it cannot deviate from the specified protocol instructions. Note that in the multiparty setting, the semi-honest adversary may corrupt multiple parties. In this case, it sees all of the corrupted parties' states together.


Just expand it out.  You get $4\tau \cdot 2^\rho + 3 \cdot 2^\rho$.  Then,

$\tau \cdot 4 \cdot 2^\rho = \tau \cdot 2^2 \cdot 2^\rho = \tau \cdot 2^{\rho + 2}$

and

$3\cdot 2^\rho < 4 \cdot 2^\rho = 2^{\rho+2}$.

Put it back together,

$\tau \cdot 2^{\rho + 2} + 2^{\rho + 2} < \tau (2^{\rho + 2}+2^{\rho + 2}) = \tau 2^{\rho+3}$


Product of Vigenère ciphers is not a Vigenère cipher with length of LCM

I have tried with some lengths but it worked so that the product was Vigenère with length of LCM.

Actually, the statement really isn't "is encrypting with cipher $\mathcal{V}_1$ and the cipher $\mathcal{V}_2$ always equivalent to some cipher $\mathcal{V}_3$.

Instead, it's "are the set of transforms that you can express by first encrypting by some transform (I'll say key, even those the members in the set are technically transforms and not keys) in $\mathcal{V}_1$ and then by some key in $\mathcal{V}_2$ precisely the same as the set of transforms you can reach by encrypting by some key in $\mathcal{V}_3$."

Expressed that way, it should be obvious that, for some lengths $l_1, l_2, LCM(l_1, l_2)$ there are keys in $\mathcal{V}_3$ that cannot be reached by $\mathcal{V}_1$ followed by $\mathcal{V}_2$

To take a simple example, if $l_1 = 2$, $l_2 = 3$ and we're doing Vigenère in base 26.  In this case, the total number of transforms that can be expressed by $\mathcal{V}_1$ and $\mathcal{V}_2$ is at most $26^2 \times 26^3 = 26^5$ (and it's actually less than that).  However $\mathcal{V}_3$ contains $26^6$ transforms, hence there must be quite a number that are not reachable via $\mathcal{V}_1$ and $\mathcal{V}_2$


It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.

Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).

There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.

Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.


2466 digits for an RSA modulus is somewhat large, but not unseen. A larger RSA modulus, when it is properly sampled, can only lead to a better security guarantee. The ciphertext in RSA is $c = M^e \bmod n$, where $M$ is something derived from the input message $m$ - hence, it is perfectly normakl for $c$ to have the same bit length as $n$ (anything significantly smaller would be a weakness, anything significantly larger... would not be a valid ciphertext). This choice of $e$ is also the most common one. Hence, there is nothing wrong with your proposed choice of parameters, provided that $n$ was indeed generated as the product of two random length-$1233$ strong primes.

  n cannot be factorized. I checked on factordb.com and no factors were present.

Note, however, that this gives you essentially zero indication about the actual security of this modulus. It is only a secure modulus if it was generated as a product of two equal-length random strong primes, with a good random number generator. $n$ could be a very weak RSA modulus if it was not generated this way, yet you would not immediately find the factors with an online tool.


argon2i hashes with GPU using JTR or any other tool please help!

I am not able to use GPU with JTR i.e. no opencl mode for argon2. Thus the speed is very slow. Any suggestion how to proceed using GPU based attack?

This is exactly one of the reasons that argon2 exists.

It was explicitly designed so that hardware other than a general purpose CPU provides only a minimal advantage, if any.

Proceeding with GPU based attacks is probably a waste of a GPU. One of the core features of argon2 is a large amount of memory usage, which GPUs are not exceptionally good at.

Options

Your best bet is to have a large number of normal computers with sufficient RAM, or investigate FPGAs. FPGAs may not be able to provide a worthwhile advantage due to the memory requirement, and they will not be so easy to work with (unless you are already skilled with an HDL).

Neither option will be cheap, and I assume that they are not practical in your situation.

Most likely, you are stuck testing one password guess at a time using your CPU. In such a case, the best that you can do is to use a good word list and hope that the password is weak. Either that, or find some alternative method of finding the password that doesn't involve cracking argon2 hashes.


Cryptographic hash that supports efficient update after random-access plaintext modification

I don't have a proof, but I don't think an $O(1)$ R is possible. That would make it very easy to calculate the hash of a changed input, and while this wouldn't contradict any defining property of a hash, it would make the hash weak for constructs like key derivation. So it would have to be a pretty unusual hash.

The standard solution is hash trees, also known as Merkle trees. It's an old technique, older than all modern hash functions, but still very much relevant for filesystems with integrity checks. Hash trees give you an R function with $O(n)$ extra storage and $O(\log n)$ calculation time and data transfer to make an update. The idea is to divide the data into blocks and to maintain a tree whose leaves are the data blocks and whose inner nodes contain hashes of their children. Whenever a block is updated, you only need to update the path from that block to the root of the tree.


Most likely, the hardware engine has an API accepting an IV of 256 bits (32 bytes) and a data block of some size multiple of 512 bits (64 bytes), and returns a result of 32 bytes.

Given that SHA-256 is a Merkle-Damgård hash, in order to chain invocations of that API, you want to pass the SHA-256 IV (given by FIPS 186-4 section 5.3.3) as the IV of the first call, and the result of the previous call as the IV of the next invocation. The last result returned by the API will be the hash.

Assuming the API does not perform the padding, the data blocks passed to successive invocations shall be the padded message (that is the message of $S$ bits followed by a single bit at 1, then $511-(S+64\bmod512)$ bit(s) at 0, then $S$ on 64 bits in big-endian binary), truncated into blocks suitable for the API, in the order they have in the padded message.

If the blocks passed to the API could only have 64kB size, that API would be usable to process the whole message only when $2^{19}-576\le S\bmod 2^{19}<2^{19}-64$; otherwise, some of the end of the computation would need to be done in software.


Why does appending a message to a key before hashing not guarantee integrity?

It depends on the hash function you're using, but some hash functions work like repeated block ciphers (SHA1 and MD5, for example).  The point is (as you've been told), an attacker can use the hash and continue appending data to generate a new and valid MAC.

That is, given $H(k||m)$, a valid MAC for $k||m$, an attacker can generate $H(k||m||m')$, a valid MAC for $k||m||m'$.  This is undesirable behavior.  We want to avoid the possibility of an attacker generating a valid MAC for any message, even if they don't know the key.  This is why it invalidates integrity, because now an attacker can make valid messages and MACs (with limitations) when they don't know the key.

See Length extension attacks.


Disrupting MITM attack against 3DES by intermingling plaintext and inter-mediate ciphertext between rounds

3DES
What is described here is not 3DES (Triple DES or TDES and officially the Triple Data Encryption Algorithm (TDEA or Triple DEA)). Let us call the $E$ as DES encryption and $D$ as DES decryption. Then we can write 3DES encryption as
$$E(k_3,D(k_2,E(k_1,message)))$$ with independent keys $k_1,k_2,k_3$.
The provided security by 3DES with 3 key is not 192-bits. It is around 122-bit. Therefore the 2 key variant is preferable and it is called 2TDEA.
$$E(k_1,D(k_2,E(k_1,message)))$$ in 2TDEA $k_1 = k_3$ and $k_1$ and $k_2$ are independent.
To apply the Meet-In-The-Middle (MTIM*) attack one needs cascaded ciphers. So that one can divide the encryption/decryption calls and approach from left and right build a table and find the keys with a couple of known-plaintexts.
Your Design
Your design uses the internals of the DES in a way that you defined a new cipher that has a 192-bit block size with 168-bit keys size. There is no cascading there, therefore, MITM attack is not possible.

Is it secure ( i.e. does really provide 168-bit security), we don't know. It is a new design and needs a new analysis.

*The MITM here, should not be confuse with Man-in-the-Middle attack. The later attack is an active eavesdropping


How to identify the difference between two cryptographic schemes in terms of security?

Security of the Smart-Vercauteren scheme is based on the Short Generator Principal Ideal Problem (SG-PIP), whilst FHEW is based on (ring)-LWE. There have recently been several attacks on SG-PIP that are much faster than the best known LWE attacks, so it would seem that FHEW currently has stronger security foundations.

In particular, Cramer, Ducas, Peikert and Regev described a subexponential attack that solves SG-PIP in $O(2^{n^{2/3 + \varepsilon}})$ time.

http://eprint.iacr.org/2015/313.pdf

I don't know whether LibScarab takes this attack into account, but I suspect at least the original SV parameters are much weaker than first suggested.

There are also polynomial time quantum attacks on SG-PIP that are referenced in that work, whereas there are currently no known efficient quantum algorithms for (ring)-LWE.


ElGamal against chosen ciphertext attacks

As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the challenge ciphertext and the encryption of some random message; the homomorphism ensures that $Enc(pk, m_b) \cdot Enc(pk, m') = Enc(pk, m_b \cdot m')$, and therefore, the decryption oracle cannot refuse to respond to the query since the input is different to the challenge; now the adversary only has to remove $m'$ to recover the challenge message.

Also, something worth mentioning is that the proof given in that book does not follow the traditional conventions for proofs in provable security. First, they are not defining the security goal explicitly (i.e., are they trying to prove one-wayness? indistinguishability? some other notion?). And second, usually proofs are constructed as a reduction to a hard problem; that is, these proofs aim to reach a contradiction by which, if the scheme is insecure, then you could solve the hard problem. These proofs follow this template:

Define a security goal (e.g., Indistinguishability (IND)) and an attack model (in this case, chosen ciphertext attacks). Together they form a security notion (e.g., IND-CCA).
Assume the existence of an adversary $\mathcal A$ that breaks the scheme under the security notion.
Simulate the environment of $\mathcal A$. That is, you explicitly construct the oracles required by the attack model. Usually, you need to somehow embed elements from the hard problem instance you want to solve (e.g., elements from a DH tuple $(g^a, g^b)$).
Prove that using $\mathcal A$ you could solve the hard problem.
Since the hard problem is assumed to be hard, we have reached a contradiction, so the initial assumption (i.e., the statement in step 2) is false, and the scheme is actually secure.

However, the proof given in the book is doing something different. It is first assuming that there exists a decryption oracle, and then proving that you could solve the DH problem using it. Since the DH is hard, then the initial assumption must be false. In this case, the initial assumption is that there exists a decryption oracle, but this does not prove at all that the scheme is secure under chosen-ciphertext attacks.


How does Poly1305 in the NaCl library calculate a MAC?

I don't know if this is the standard way, but I do know that poly1305 is a single-use-only MAC function. You can never use the same poly1305 key twice for different messages or an attacker could forge MACs, apparently. So this sounds like an easy, safe, and computationally inexpensive way to use the encryption cipher you're going to use anyway to generate a unique strongly-randomized poly1305 key for each message.