Security in case of Malicious and Augmented Semi-Honest Adversaries

As pointed out in the comments, an augmented semi-honest adversary is one who can change its input before the protocol execution begins, but from then on the adversary runs the protocol specification exactly.

Note that if a protocol is secure for malicious adversaries, then the simulator must be able to work also for an adversary who changes its input and then behaves honestly. Thus, the protocol is secure also for augmented semi-honest adversaries.

The reason that this does not work for semi-honest adversaries is because the ideal-world simulator for a semi-honest adversary cannot change the input. That is, in the case of malicious adversaries, both the real adversary and the ideal simulator are stronger than for semi-honest adversaries. This fact means that security for malicious adversaries does not necessarily imply security for semi-honest adversaries (because the ideal simulator cannot run in the semi-honest case if it needs to change the input of the corrupted party). In the book, we give an explicit counter-example of a protocol that is secure for malicious adversaries but not for semi-honest. I know that this is extremely counter-intuitive, but that's the reality.


Asymmetry between public key and private key: digital signatures use the private key for “encryption”?

You use your private key for "encryption".

That's a common misconception, which has roots in history. The point is that for RSA calculations the signature generation operation uses the same mathematical operation - modular exponentiation - with the private key as the encryption operation with the public key. So in older versions of PKCS#1 - itself called "RSA encryption - this is called "encryption with the private key":

  The data D shall be encrypted with the signer's RSA private key as
     described in Section 7 to give an octet string ED, the encrypted
     data. The block type shall be 01. (See Section 8.1.)

This is also reflected in RSA encryption originally being used as object identifier within X509 certificates, such as those within your browser.

This over-simplification was fixed in PKCS#1 v2 and higher, where the modular exponentiation got a different name: RSASP1 (RSA signature primitive 1) instead of RSAEP (RSA encryption primitive). A primitive here is simply an underlying function within the algorithm, by the way.

Other signature standards such as the Digital Signature Algorithm (DSA) use a specific operation to perform signature generation. This specific operation cannot directly be used for encryption. So there isn't a direct encryption counterpart for DSA. The Integrated Encryption Scheme (IES) can be used but it depends on Diffie-Hellman (DH) rather than DSA. The same goes for the more modern Elliptic Curve implementations (ECDSA, ECIES and ECDH respectively).

  Now I have the impression that private and public key are symmetric in a sense that you can choose one for encryption and then the other one is for decryption but you could also do it the other way round.

Yes, and that's precisely what you should not be thinking, Poncho has given a good answer here.

But note that if an implementation expects a public key that the operation with a private key may fail. Furthermore, as explained in the last part of the answer, the operation may not be secured for keeping the private key, well, private. And finally it may not use CRT speedup / security either as a public key generally doesn't contain CRT parameters - there is no need and they are not present during key pair generation for the public key.

  What I dont understand here is: Where is the math with trapdoor function used here if it is in a sense completely symmetric?

This is an RSA specific question. It's during the modular exponentiation. The trick is to keep the right exponent (and possibly the parts used during key generation for calculations that use the efficient Chinese Remainder Theorem (CRT) secret.

But please remind that padding is required for a computation using RSA. Just the trapdoor isn't enough; there are certain requirements to make the trapdoor secure.

  Is it possible to easily derive the public key from a private key? I have heard that in theory NO but in practice YES...

I'm not sure about the theory, but if the public key has a large public exponent (e.g. almost the same size as the modulus) then the public key may have as much security as the private key when it comes to the algorithm itself. But there are many reasons why RSA decryption with the public key would still not be secure; e.g. side channel analysis may be performed that the implementation is not protected against (no reason to secure the public key after all). Large public exponents are not common at all and many implementations would even fail if they were to be used.

So you could just test all public exponents, combine them with the modulus and test if an RSA operation is successful. However, in practice the public exponent is simply set at the value 65537 (the fourth prime of Fermat). Besides that, the public exponent is often included in the private key structure as well. So you should not expect to keep the public key secret, period.


Here's a hint on one avenue of approach (actually, there are several possible):

Suppose we had two plaintexts $X$ and $X'$, which are identical except in one bit.  Now, consider $\text{SimpleDES}_K(X)$ and $\text{SimpleDES}_K(X')$; how are they related?

If that's too difficult, consider how both $\text{SimpleDES}_K(X)$ and $\text{SimpleDES}_K(X')$ are related after 1 round, after 2 rounds, etc...


How were codes in WW1 reciphered (to enhance security levels) without them turning meaningless?

The concept is called superencipherment or multiple encryption, and works as follows:

The original message M is enciphered using the code book, resulting in an enciphered message C1.
C1 is then treated as the plaintext, and enciphered using another method, resulting in a new ciphertext C2.
C2 is then sent to the receiver
The receiver uses the decryption algorithm for the second method on C2, obtaining C1.
The receiver then uses the code book to decrypt C1 and get the message M.

Creating an example:
Suppose I want to send the message "Small supplies of fruit expected. Buy as much as you can."
For my code book, I will use the A B C Universal Commercial Electric Telegraphic Code, 4th Edition.

Step 1: On page 128, we have the phrase "Small supplies of fruit expected.", with the corresponding code number 06375.  Moving to page 45, we find "Buy as much as you can." with the code number 02221. So in this example, C1 is "06375 02221".

Step 2: For the second level of encryption, I will add 13348 to each code number (ignoring any carry or borrow beyond 5 digits).  So to encrypt C1, we calculate 06375+13348=19723 and 02221+13348=15569, resulting in C2 as "19723 15569".

Step 3: The message C2 ("19723 15569") is sent to the receiver.

Step 4: The receiver decrypts C2 by subtracting 13348 from each code number.  So the receiver would calculate 19723-13348=06375 and 15569-13348=02221. This results in the message C1 equal to "06375 02221".

Step 5: The receiver then uses the code book to decrypt "06375 02221". Since I am using a one-part code here, again go to pages 128 and 45 to get the original message "Small supplies of fruit expected. Buy as much as you can."

As long as you maintain the sequence "Encrypt using A, Encrypt using B, send, Decrypt using B, Decrypt using A", the exact encryption steps can be replaced as long as the sender and receiver agree on the algorithms and keys.


Well, it is certainly possible to generate an RSA public/private key pair like what you're asking about -- I don't know what the OpenSSL API allows you can do, but if you don't restrict yourself to that, well, it is certainly possible to craft such a keypair.  You'll come up with a public key with an enormous exponent (and I wouldn't be shocked if not everyone would accept it), but it'd be possible.

On the other hand, I would argue that it's not a good idea.  For one, you're looking at only a 25% speed up.  You may be thinking "96 bytes is roughly a third of 256 bytes; given that modular exponentiation is linear in the log of the exponent (keeping everything else constant), shouldn't I see a not-quite 3 times improvement?

Well, no, you won't (or, if you do, you're doing it wrong).  The key is the Chinese Remainder Theorem optimization (already referenced by Ricky Demer); here, you do the private operation both "mod p" and "mod q", and then recombine the two halves.  That is, you compute:

$M_p = (C \bmod p) ^ {d\  \bmod\  p-1} \bmod p$

$M_q = (C \bmod q) ^ {d\  \bmod\  q-1} \bmod q$

Look at the exponents; you're not using the full $d$ (roughly 256 bytes); you're using $d\ \bmod\ p-1$ and $d\ \bmod\ q-1$; those are 128 bytes each.  So, if you replace $d$ with a 96 byte number, what you're doing is replacing those 128 byte numbers with a 96 byte number; that gives you a far smaller speedup than what you were thinking of.

We're not sure whether Weiner's attack can be extended to a private exponent of size 0.375 times the modulus size; however given the relatively small speedup this gives, it wouldn't appear to be worth the risk.

Instead, if you are concerned with performance, you might want to investigate Elliptic Curve certificates.


Can one extract a private key from a series of carefully constructed signed messages?

It is not possible if the signature scheme is secure, under the standard notion of "existential unforgeability under chosen message attacks". According to this definition, the adversary is given the public key and can then choose messages to be signed one after another. If it can forge any signature, then the scheme is not secure. As such, if the scheme is secure, it's not possible to form special messages that result in the key being revealed, or any other vulnerability.


Is there any chance of failure in Cryptography

What you are talking about is called collision resistance.
Base 64 is an encoding technique. It doesn't use a key and therefore it is not a cipher. Encoding techniques commonly have a 1:1 relation with the output of course, so no collisions there.
Pseudo-random permutations such as block ciphers have a 100% collision resistance as a permutation always has a 1:1 relationship between the input and the output. So AES and (3)DES will never repeat output for different input. Beware that this changes if a block cipher mode of operation is used to turn it into a real semantically secure (probabilistic) cipher; in that case you'd would expect collisions that depend on the output size, see the final part of this answer.
MD5 is a message digest or cryptographically secure hash function. Hash functions are supposed to have a certain collision resistance. Collisions are of course certain as there are more messages than output values (see the pigeon hole principle). However, it should be computationally infeasible to find them. MD5 is considered broken and fails on this principle, which is why it is not actually considered "cryptographically secure" anymore.
As for the "whatever": cryptography consists of many algorithms, and the outcome depends on the algorithm. If the output is supposed to be indistinguishable from random and there are $n$ different outputs then you'd expect a $1 \over n$ chance of that a value is equal to a preset earlier output value. However, due to the birthday bound you'd expect to compare only $\sqrt n$ values against each other before you find a collision with a 50% chance of success.
In the case of MD5 with an output size of 128 bits, so $n = 2^{128}$- you'd expect a collision in about $\sqrt {2^{128}} = 2^{64}$ compares. That means a collisions resistance of 64 bits in other words. However, because it is broken attackers can create collisions much more easily. Generally cryptographers aim to have a security margin of 128 bits, which means that MD5 is considered insecure with regards to collision resistance even if it was not broken.


How is McEliece chosen plaintext secure?

Does this attack work?

Yes, it works.
However, "textbook" McEliece was never claimed to be IND-CPA.
In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF).

They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many random bits and later simply ignore those bits at decryption.


How to provide secure "vanity" bitcoin address service?

I don't believe that there's any way to generate the vanity hashes without iterating. In base 58, there's $\log_2(58) \approx 5.858$ bits per letter, so fixing 8 letters would need in average $58^8/2 = 2^{\log_2(58)·8}/2 \approx 2^{46}$ iterations. Note that Bitcoin addresses always start with a 1 by convention (this comes from the version field), and the next character in the base 58 representation is usually among "23456789ABCDEFGHJKLMNPQR" (not the full 58 character set), which halves the number of tries once more (if your wished starting character is in this set, otherwise it gets impossible). If you allow your vanity string to appear anywhere in the hash, you can divide this number again by 25, leading to $2^{40.5}$ iterations (on average) (which also are quite good parallelizable).

Also, the actual example he gave had an "s" rather than an "i" in the vanity "ByteCoins" part, so the odds of that are a bit greater (i.e. the needed time is even smaller).

However, you can do it securely (i.e. without the service gaining access to your private key):

Let the user generate a private key, $a$, and submit the corresponding public key, $a·B$ (where $B$ is the base point of the group). The service can then generate public keys as $a·B + x·B$, where $x$ is incremented to generate different public keys.

Actually, if you have $a·B +x·B$, then $a·B + (x+1)·B = (a·B + x·B)+B$, i.e. you need only one EC point addition (of the base point) and the necessary hashes for each try.

Then, by telling the user x, the user has private key $a+x$ with public key $(a+x)·B$ and $H((a+x)·B)$ has the required property, if the service did its job.


Is it okay to use a variable-time RSA implementation to verify TLS certificates?

Two answers to the question:

It is about principles and reusability of the cryptographic primitives. Once there are implemented by insecure manner, nothing prevents reusing or misusing the insecure functionality later.
TLS validation (during the SSL handshake) involves a secret as well - during the SSL handshake a piece of data is encrypted and sent over to decrypt to proof ownership of the private key. This is the part when the side-channel attack needs to be mitigated.

Carpe diem

g.


Secret Sharing and Multiplication Triples

If you understand that $xy = c \oplus ex \oplus dy \oplus ed$ I am not sure what else is there to understand?

I wonder if you have understood how the $[x]$ notation works? $[x]$ means that $x$ is XOR shared between between Alice and Bob (I.e., Alice has $x_A$ and Bob has $x_B$, so that $x = x_A \oplus x_B$). When we write $[e] = [x]\oplus[a]$ this that Alice and Bob computes an XOR secret sharing of the value $e = x \oplus a$. Simlarly, if we write [f] = e[x], this means Alice and Bob compute an XOR sharing of $f = ex$. So by extension if $xy = c \oplus ex \oplus dy \oplus ed$ then $[z]$ means we have computed an XOR sharing of $z = xy$.


This method is fine (if it does actually check for short private exponents).

Any choice of public exponent is functionally and security-wise equivalent as long as it doesn't induce a short private exponent and as long as it is co-prime to $\lambda(n)$. The latter being caught by the fact that key generation won't be able to finish and the former being caught by the PKCS#1 v2.1 induced check (which I couldn't actually find, so beware!), which should check for short private exponents.


What is the best way to derive a encryption key from the serial number?

The standard way to make a key out of some information (like your serial number), is to use a Key derivation function (KDF). If you do not consider a brute force attack to the serial number a realistic threat, then HKDF would be the suggested route to go, otherwise you should use a password based KDF like SCrypt which is much slower (which is a good thing against brute forcing).

I feel obliged to add, that using nothing but a serial number as a secret will not give you a secure encryption. While 16 bytes are basically enuogh to thwart attackers these days, it has to be assumed that the serial numbers are not really random but do follow some pattern, thus making them nuch more easily guessable. So while this scheme will be ok if you just want to prevent accidental misuse or passive attackers, it will most certainly not be good enough against an active attacker.

Update after your comments to the question above:

SCrypt won't help you in that scenario, so should use HKDF to derive a key for symmetric encryption (probably AES). Since you obviously never have an online connection to your app, using a random salt also won't be possible.  The only additional secret you could use to strengthen the process would have to be hardcoded in your app, protected by some code obfuscation. All this will protect you from the casual file sharer who just copies the file to a different device, but not from anyone more active.


Static salt for PBKDF2, but unique salt for HKDF?

Yes, the salt in the HKDF can provide for key separation between the encrypt-then-mac applications. If that's needed depends on the system, maybe using an IV/nonce is enough, it depends on how many messages you want to encrypt and the used encryption and MAC scheme basically.
Some other remarks:

we derive keys - not passwords - for ciphers and MAC algorithms;
using an authenticated cipher such as GCM mode instead of encrypt-then-mac would be wise, in that case you only need to derive one key;
you'd use a static salt with PBKDF2 to derive the same master key, it's probably best to only use a static salt if you need to reuse the key (which of course assumes that you also use the same password);
you may want to additionally use a separate KDF invocation to derive a "key check value" stored with the ciphertext to check that you've derived the correct master key (instead of having to rely on authentication tag failures).


Hardness assumptions on composite order bilinear groups

The BGN (Boneh Goh Nissam) cryptosystem uses a Type-III bilinear pairing defined over composite order groups to have 1 homomorphic multiplication along with unlimited homomorphic additions.
You may want to have a look at their paper: Evaluating 2-DNF Formulas on Ciphertexts, or any lecture on this cryptosystem.

I hope this will help you.


Yes, after obtaining values for $X_3$ and $Y_3$ (and $Z_3$), in order to get back to affine coordinates, one would have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$.

However, in most cryptographic applications, we're making point multiplication with a large multiplier, which requires many point additions, which can be carried entirely in projective coordinates. We get back to affine coordinates only at the end of that. Therefore, the field inversion required to get back to affine coordinates is performed once per point multiplication, and represents a low proportion of the computational cost.

Whatever the base field, one can use the extended Euclidean algorithm to compute $1/Z_3$; or better the half-extended version there, which is specialized for the inverse; or $1/Z_3={Z_3}^{p-2}$ where $p$ is the number of elements in the base field. For the base field $\mathbb Z_p$ with $p$ prime, there's also the half-extended binary GCD algorithm there.


Will Fernet’s key function at any timeframe?

No, there is generally no time factor when it comes to decryption.
However, you should remember that even a single changed bit can cause decryption to fail. This is especially the case if that bit is part of the IV, authentication tag or nonce. So I'd rather worry about storage of keys and data. Disks may get stuck, flash may degrade or loose voltage differential.


How many bits of plaintext are required to verify a stream cipher key?

At least $n$ typically more. If you have no IV, as in classical setups, you need to do a state transition analysis. If there is an IV then the (key +IV) mixing phase also needs to be analysed and the answer is most likely probabilistic.

In short, the bijective mapping you're talking about is very very rare in a well designed stream cipher.


Replay attack prevention in connectionless UDP encrypted communication

The simplest way to deal with replay attack prevention (in some narrow sense of that, where the goal is to avoid that the receiver allows the same command to be played to it several times) is to have an incremental counter in an authenticated section of the packet, incremented by the sender before forming a packet to be sent. The receiver checks the authenticity of packets, and discards packets with counter field lower or equal than its own counter, then sets its own counter to the counter just received; initially, the counter is zero on both sides; it must be large enough that it can't overflow, 4 bytes are often enough.

Problems are:

This prevents replay of passively eavesdropped material, but not delayed play of actively eavesdropped and suppressed material. In many adversarial models, that is a devastating issue. Think of a garage door opener: the adversary intercepts "open door" command, count on the user re-issuing another, intercepts that too, plays the first command to garage door, door opens, user is happy; adversary plays the second command later when the user is away. On radio links with a CRC at the end of the packet, the attack can be carried by jamming the end of the CRC so that the receiver ignores the packet, but the eavesdropper has the data, perhaps with a fair amount of error-detection capability.
This requires a reliable atomic counter in sender and receiver, and this is hard, especially in a context where attacker can cut power of the sender or receiver at an instant precisely timed w.r.t. update of the counter. Even static RAM with battery/supercap backup out of reach of an attacker does not provide atomic update beyond wordsize (and then, not all do that, much less give a clear insurance that they do); and things are worse with EEPROM and Flash, which often can only be erased a smaller number of times than the range of the counter, and can enter metastable states where the value read becomes unreliable. That can be solved, but is notoriously difficult to get right.
There must be a distinct counter in the receiver for each sender (it is possible to live with a single counter on the sender side).
Out-of-order delivery of packets, which can occur with UDP, no longer works. This can be fixed with a sliding window, typically in RAM, at the expense of adding complexity (thus risk of error; some briefly crept in earlier versions of the following).
Addition per comment: the receiver maintains a bitmap of $b$ bit(s), for of up to $b$ past counter values less than the current counter that it is willing to accept nevertheless; that bitmap in RAM is initialized to all-zero at reset; and if $0\le j<b$, and bit $j$ in the bitmap is a one, and the receiver's counter is $c$, and $c>j$, then a packet having counter field $c-j-1$ will be accepted (when it would be rejected per the rule in the first paragraph of this answer), and bit $j$ in the bitmap will become zero. The receiver's job on receiving a packet becomes

check size and integrity of packet
extract counter field $x$ of the packet
if $x>c$

if $x-c>b$, set bitmap to all-ones; else shift the bitmap introducing a zero bit at index 0, then $x-c-1$ times (possibly zero) shift the bitmap introducing a one bit at index 0. In C or C++, with $b=32$ and m the bitmap as an uint32_t, this whole step could be: m = (x-c>32) ? 0xFFFFFFFF : ((m+m+1)<<(x-c-1))-1;
$c\gets x$ atomically
accept the packet as received in order (with no earlier packet possibly accepted later when the bitmap is all-zero), done;

else, if $0<c-x\le b$ and if the (now well-defined) bit $c-x-1$ of the bitmap is a one

change said bit to zero
accept the packet as received out of order (which can require special care), done;

else, reject the packet.

As stated in (1), all the above is insecure against an active attacker capable of delaying packets and gaining advantage of that. Alternatives that are secure in this scenario, and do not require the difficult atomic counter, include building a challenge/response protocol on top of UDP, with the challenge good for a certain delay measured by the receiver (which requires the ability to evaluate elapsed time, but not absolute time); main problem is, that requires two-way communication.

It is also possible to use an authenticated source of absolute time; the hard thing is to find a reliable free one, see this.


Does DROWN attack break 2048-bit key itself or just the plaintext encrypted with the RSA key

It breaks the secret key (master secret) that is encrypted using RSA; this secret key is the plaintext message; it is not the RSA private key.

Padding oracle attacks (DROWN uses a special form of the Bleichenbacher padding oracle attack) generally only attack the plaintext message, not the secret or private key used to create the ciphertext.


Problem with the signature of message using ECDSA over GF(2^m)

First of all I would like to thank @fgrieu, @kelelaka and the moderator Maarten Bodewes for their support to solve my question.
I had an error to determine K^-1, S, y S^-1, I was also missing an important piece of information which is the order of G (n = 29)
Correcting my mistake we have:
GF(2^7), m = 7
E: y^2 + xy - [x^3 + ax^2 + b]
y^2 + xy - [x^3 + 0x^2 + 1] with a = 0 and b = 1
Irreducible polynomial P(z) = z^7 + z + 1 mod 2
d = 17
G = (124, 68) = (z^6 + z^5 + z^4 + z^3 + z^2, z^6 + z^2), Generator a point that lives on the curve
Q = [d]G = (40, 19), a point that lives on the curve too.
k = 13
P = [k]G = (82, 100)
r = x(P) = 82
e = SHA(m) = 19
n = order of G = 29
k^-1 = 9 (Here was my first mistake when taking modularization with P(z) instead of n)
S = k^-1 (e + d*r) mod n (Here was my second mistake when taking modularization with P(z) instead of n)
S = 9 (19 + 17 * 82) mod 29
S = 15
Finally we obtained the value r and S that is the signature of the message(r,S)=(82,15)
Verifying the signature:
P = [S^-1 * e mod n] G + [(S^-1 * r mod n)] Q
S^1 = 2
P = (2 * 19 mod 29 )G + (2 * 82 mod 29)Q
P = [9]G + [19]Q
P = 9(124, 68) + 19(40, 19)
P = (76, 50) + (98, 104)
P = (82, 100)
x(P) = r
This is how we check that the signature is valid.


If you look in the OCB submission for CAESAR, you will see that the designers state the security is similar to that of GCM. I would note, however, that GCM has been shown to posses weak key classes, see for example:

https://eprint.iacr.org/2013/144.pdf
https://eprint.iacr.org/2011/202.pdf
http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_03.pdf
https://about.bozhu.me/paper/lgcm.pdf


Is there any reduction from Short Integer Solution to $\textrm{SIVP}_\gamma$

If $A\in\mathbb{Z}_p^{n \times m}$, then you can define $$\mathcal{L}=\{y\in\mathbb{Z}^m~:~Ay=0\,\bmod\,p\}.$$

$\mathcal{L}$ is an $m$-dimensional lattice, and if you solve (search) $SIVP_\gamma$ in this lattice, it implies that you found a vector $v$ (actually many such vectors) such that $Av=0\bmod\,p$ and $||v||\leq \gamma\cdot\lambda_m(\mathcal{L}).$  So that's a solution to SIS.  When $m>n$ (say $m>2n$) and  $A$ is uniformly random, you can actually tightly bound the value $\lambda_m(\mathcal{L})$ to be around (ignoring some constants) $$\lambda_m(\mathcal{L})\approx \sqrt{m}\cdot \det(\mathcal{L})^{1/m}=\sqrt{m}\cdot p^{n/m}.$$
So, in short, if you can solve $SIVP_\gamma$ for random lattices of the above form, then you can find short vectors $v$ such that $Av=0\bmod\,p$ with $||v||<\gamma\cdot\sqrt{m}\cdot p^{n/m}$.


How to improve entropy on a router running Linux kernel 2.6.x without TRNG or RTC?

You don't need to continually feed entropy into the system for security, so long as the OS random number generator was strongly seeded once.

If you're unsure about the seeding history of the device, add some entropy. Take a photo of the sky with your mobile phone. Upload to your router and pipe it into /dev/random. That's all the entropy you'll ever need on that particular device.

Seriously, there is so much nonsense surrounding entropy gathering out there it's almost funny. The Linux manual page for /dev/random is the cause of much of this pseudoscience; it is simply wrong. The "entropy counters" provided by the kernel are ad-hoc estimates which are meaningless from a security perspective.

You can't "use up" or "lose" entropy on a modern OS. As long as your entropy is used only to seed a CSPRNG (which is true in even very old Linux), 256 bits of entropy is enough for every possible use case. If you don't believe that 256 bits is enough to generate a infinite stream of secure randomness, you'd better stop using AES in counter mode for encryption as well.


This result is proven in the following research papers:

Johan Hastad, Mats Naslund.  The Security of all RSA and Discrete Log Bits.  Journal of the ACM, Oct 2003, pp.1--45.
W. Alexi, B. Chor, O. Goldrech, C. Schnorr.  RSA and Rabin functions: Certain parts are as hard as the whole.  SIAM Journal on Computing, vol 17 no 2, pp.194--209.

They show that if you can predict the least significant bit (or the $O(\log \log N)$ least significant bits), then you can break RSA.  See also the citations in that article for similar results.

I can give you a taste for why this might be true, by sketching how to prove a much weaker version: if you have a way to compute the least significant bit of $x$ from the RSA encryption $E(x)$, then I can break RSA.

Let me start with a warmup.  Suppose you have a black box that, given a ciphertext $E(x)$, can answer the yes-or-no question ``is $x$ in the range $[0, N/2)$?''.  Suppose your black box is perfect: it always gives the right answer.  Let me show you how I can use your black box to break RSA.

Notation: Here $E(x)$ denotes the RSA encryption of message $x$, i.e.,
$E(x) = x^e \bmod N$.  Notice that there is no padding and no randomization in my definition of $E(\cdot)$.  Also note that RSA is homomorphic, so $E(2x) = 2^e E(x) \bmod N$.  In other words, given $E(x)$, I can derive $E(2x)$ even without knowing $x$.  I will use the notation $[a,b)$ to represent the set of integers $a,a+1,a+2,\ldots,b-1$.

Now let's solve the warmup problem.  We are given $E(x)$, and we want to find $x$.  Basically, we're going to use binary search.

First, we query your black box with $E(x)$ to learn whether $x$ is in the range $[0,N/2)$ or in the range $[N/2,N)$.  Suppose we learn that $x$ was in the range $[0,N/2)$.
Next, we query your black box with $E(2x)$.  This tells us whether $2x$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[0,N/4)$ or in $[N/4,N/2)$.  Suppose we learn that $x$ is in the range $[N/4,N/2)$.
Next, we query your black box with $E(4x)$.  This tells us whether $4x \bmod N$ is in the range $[0,N/2)$ or in $[N/2,N)$.  Note that $4x \bmod N = 4x-N$ (given what we know about the range $x$ is in).  So, we know whether $4x-N$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[N/4,3N/8)$ or in $[3N/8,N/2)$.
Keep going like this, until $x$ is completely known.

This requires $O(\lg N)$ queries to your black box. If your black box always gives the correct answer, then at the end we learn the exact value of $x$.

In other words, if you have a black box like that, then given any RSA ciphertext $E(x)$, I can derive $x$: which is a total break of RSA.  (Conversely, if we assume RSA is secure, then such a black box is impossible to build.)

The warmup above might start to give you some idea of what it might look like to try to prove the stronger result.

For instance, suppose you don't have a black box that answers the question "is $x$ in the range $[0,N/2)$?", but you do have a green box that answers the question "is the least significant bit of $x$ one?".

Well, given a green box, we can build a black box.  Given $E(x)$, we query the green box on $E(2x) = 2^e E(x) \bmod N$; if it answers "yes", then $x$ is in the range $[0,N/2)$, otherwise $x$ is in the range $[N/2,N)$.  So, the green box's answer to $E(2x)$ reveals how the black box should respond to the query $E(x)$.

Therefore, if you have a green box that can compute the least significant bit, you can break RSA (by constructing a black box and applying the binary search method as above).  Conversely, if we think RSA is secure, then there should be no way to build a green box like this.
As another example of a generalization, suppose your black box doesn't always give the right answer; it answers correctly with probability $1/2 + \epsilon$, and incorrectly with probability $1/2 - \epsilon$, for some $\epsilon>0$.  Then we have an instance of a game of 20 questions, where we have only a noisy view of our answer.  It turns out there are algorithmic ways to deal with this noise, though it does take a lot of difficult technical work.  For the details, see the papers mentioned above.


What impact could general quantum computing have on BCrypt?

I'm not aware of any quantum-based cryptanalysis results of symmetric ciphers that would perform better than Grover's algorithm on any symmetric cipher.

Now here's the interesting part: Grover's algorithm. It allows you to search in an unsorted set of size $n$ in time $\sqrt n$. Now for Blowfish the implication is clear: It effectively halves the keysize from 448-bit to 224-bit which is still extremely strong. However you shouldn't use Blowfish because of its blocksize and the fact that it's nearly broken by cryptanalysis.

Now for bcrypt we need the following statement:

  Grover's algorithm is a quantum algorithm that finds with high
  probability the unique input to a black box function that produces a
  particular output value, using just $\mathcal O(\sqrt n)$ evaluations of the function, where N is the size of the function's domain.

Now Grover's algorithm allows you to find passwords much faster, but won't evaluate bcrypt faster but probably much slower. So suppose you have a password hash that has a strength of 80-bit, ie one would need $2^{80}$ operations to find the password. Chance are bcrypt takes 20-bits from that leaving you with 60-bits provided by the entropy of the password. Grover's algorithm can now half this value so you end up at $2^{30}$ bcrypt evaluations and thus $2^{50}$ operations overall.

TL;DR: Quantum computers will weaken password hashing but "as bad" as they weaken standard encryption.


This question can't be answered exactly, because it depends on a lot of the actual details of the realization. But as a rule of thumb: They cost a lot. In fact they cost so much, that in any protocol they are the sole determinator of the computation time and you can neglect the other operations.

First, keep in mind that usually bilinear maps are realized with elliptic curves. There is no straight forward bilinear maps in $\mathbb{F}_p$, which can be used for cryptographic tasks. Currently the only known constructions for (cryptographically useful) pairings are:

Weil pairing
Tate pairing

So first we need to consider the elliptic group operation, where the number of operations (addition, multiplication, etc.) can vary. Looking at the definition of the Weil pairings, we soon get to the following conclusion:

There is an integer $n$, which is chosen at the setup, but its role isn't that clear to begin with.
There is a function $F$ (on values $P,Q$), which just has to fulfill some property, but isn't specified any further. But the definition of the divisor has a sum, where the number of addends are linear in $n$, so the compuational complexity of $F$ will depend somehow on the choice of $n$.
The function definition $w(P,Q):= F/G$ has the $n$-th roots of unity as its image. Thinking of the bilinear map, this is the target group. And for cryptographic purposes we need a group where the discrete logarithm is hard in the target group, so we can conclude that $n$ has to be large.

This already shows, that unless you specify exactly what kind of elliptic curve and which kind of Weil pairing (or Tate pairing) you have, you can't state an explicit number of operations.

For further information I would suggest reading Pairings for beginners from Craig Costello, which also has plenty of examples with numbers.


How is block cipher padding verified for consistancy?

Let's say we are using PKCS#7 padding, and we'll stick to a single block message for simplicity. Modifying the ciphertext should result in an completely random decryption. To get proper padding, the resulting decryption would have to look something like this (RANDOM DATA)01 or (RANDOM DATA)0202, and so on.

Since the result is random, the probability that you would get (RANDOM DATA)01 is $1/256\approx 0.004$, the probability that you would get (RANDOM DATA)0202 is $(1/256)^2$, and so on. The sum of these is the probability $\displaystyle\sum_{n=1}^{16} (1/256)^n\approx 0.004$ (notice that all cases except padding of 01 are of negligible probability).

Looking at this padding method, it is easy to see how one would detect a modified ciphertext by simply looking at the padding. If the resulting plaintext is something like (RANDOM DATA)(SOMETHING OTHER THAN 02)02, the padding is not correct. Using this as a message authentication attack and reporting the result to the user (either directly or indirectly) would result in a padding oracle attack, which would be very devastating.

Other padding methods, for example, will have different probabilities. For example, ISO 10126 uses random padding with the last byte used to tell how much padding was used. If the block size is 16 bytes, a last byte of 01 through 0f would be valid. Thus the probability would be $16/256=0.0625$.


Two independent ideas:

In the Hill cipher, elements of matrices are in the ring of integers modulo the number of characters in the alphabet used, usually $n=26$. Therefore, as long as the denominator of a fraction is coprime with $n$ (that is, for $n=26$, if the denominator is divisible neither by $2$ not by $13$), that fraction reduces to an integer modulo $n$.E.g. $\displaystyle\frac23\equiv18\pmod{26}$ since $2\equiv3\cdot18\pmod{26}$.
The Hill cipher is sometime instantiated with a $3\times3$ or larger matrix.


Does the XML Encryption flaw affect SSL/TLS?

No; the problem with XML is that it doesn't include a Message Authentication Code (MAC), or anything else to validate the ciphertext; the only validation that XML does is checking if the CBC padding is sane.  The attack uses that as an Oracle to decrypt data; the attacker generates an encrypted region with the last two blocks being carefully chosen; if the last block decrypts to a sane padding, that gives him information on what the last block decrypted to).  SSL/TLS always includes a MAC along with the encrypted data; hence if the attacker generates his own encrypted data, the MAC will fail (because he can't generate that), and so the attacker will get no details on what the decrypted data looked like.

Now, there is one exception to that; when Vaudenay first discovered this attack (Password interception in a SSL/TLS channel), he realized that (because of the order of operations that TLS uses, it decrypts first and then checks the MAC) if the attacker could distinguish between a padding failure and a MAC failure, he could still use this attack.  Now, in this case, actually trying this attack always causes the TLS connection to drop on the first attempt (and hence it's useful only if you can get the system to set up repeated sessions with the same plaintext); nevertheless, nowadays I would hope that all SSL/TLS implementations try to be careful to not leak that to an attacker.


Login security and plaintext of a password stored in Argon2i to derive a key via halite safe?

1. Is this form of double authentication even helping security?

Possibly, but in general, asking users to remember two passphrases is asking too much. It is less likely that either one of them will be secure enough to be used as password.

  2. Is using the second passphrase to derive the key safe?

Probably, but sharing a password among all the other employees is certainly not secure.

Besides that, using both Argon2i and scrypt on the same input material only slows down your service, while an adversary only needs to perform the fastest one (from their perspective).

If a key is derived after verification of the password then a Key Based KDF such as HKDF can be used.

  3.  ... is this possible without re-encrypting all of the data using the new derived key?

No, for that you'd need a data key as you're describing.

  If that works would Halites Symmetric::encrypt be secure enough for the second key?

Sorry, but that's off topic here; we cannot vouch for the security of a crypto system or library. You can of course do worse than libsodium to encrypt data, but if it is secure also depends on system and implementation details.


Is there any relationship between Paillier Cryptosystem's random r and other factors

You made a mistake in decryption.

You wrote:

m = 1191*3 mod 35

You lost L(...) here. Instead of 1191 it should be L(1191):

m = L(1191)*3 mod 35
L(1191) = 34
m = 34*3 mod 35
m = 102 mod 35
m = 32

Voilà. We got the original message.


Can a KEM shared secret be used directly as a symmetric key?

The algorithms you mentioned use a secure hash function to derive this convenient 32-byte shared secret, but it is not necessarily true that all KEMs will do so. The answer to your three general questions would thus be all "it depends on the actual algorithm". In general, they use KDFs.
The Kyber KEM submission, for example, uses SHAKE-256:

As a modification in round-2, we decided to derive the final key using SHAKE-256 instead of SHA3-256. This is an advantage for protocols that need keys of more than 256 bits. Instead of first requesting a 256-bit key from Kyber and then expanding it, they can pass an additional key-length parameter to Kyber and obtain a key of the desired length. This feature is not supported by the NIST API, so in our implementations we set the keylength to a fixed length of 32 bytes in api.h.

The McEliece submission uses the same hash function:

3.1 Parameter set kem/mceliece348864
KEM with $m = 12$, $n = 3488$, $t = 64$, $\ell = 256$.
Field polynomial $f(z) = z^{12} + z^3 + 1$.
Hash function: SHAKE256 with 32-byte output.
This parameter set is proposed and implemented in this submission.


Outsourcing arbitrary computations securely

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation.

However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write:

  To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs.

Within recent years, two solutions to this problem have attracted much research interest, namely:

Garbled circuits (GCs)

Have initially have been proposed by Yao back in 1982 as a general idea to perform secure two party computation, i.e., to evaluate $f(a,b)$ between two parties with $A$ having input $a$ and $B$ having input $b$ without neither learning the other's input but the result.

One can generalise this to receiving $A$ and $B$ possibly different outputs for two possible different functions $f_A$ and $f_B$. We can also emulate this by a function $f$ to be evaluated as $f((a,r_A),(b,r_B))=(f_A(a,b)\oplus r_A\|f_B(a,b)\oplus r_B)$ for $r_A$ and $r_B$ being uniform random strings. Lets say that $A$ holds the input $a$ and setting the input $b$ of $B$ (the one computing the evaluation) to be simply nothing, allows $B$ to obtain the evaluation $f$ without learning $a$ and only learning $f(a)\oplus r_A$ but not learning $f(a)$. Sending this back to $A$, $A$ can retrieve $f(a)$.

Having this scenario it can be realised with GCs by letting $A$ build the GC and give it to $B$ along with the garbled input, $B$ evaluates the GC and learns only the garbled output, which is sent back to $A$ and $A$ receives the output.

Garbled circuits can be built using symmetric encryption and oblivious transfer.

You may look at the Might Be Evil project for an implementation of GC and further pointers.

Fully Homomorphic Encryption (FHE)

A first FHE construction has been proposed by Gentry back in 2009 and there has been much progress since then. Loosely speaking, FHE represents an (public key) encryption scheme which allows you to evaluate any function $f$ which can be represented as a circuit on encrypted data such that the input is a ciphertext $c$ for message $x$ and the output is a ciphertext $c_f$ containing $f(x)$. Consequently, $A$ can encrypt some $x$ to obtain $c$, give it to $B$ and $B$ can evaluate $f$ on $c$ without learning neither $x$ nor $f(x)$ but only $c_f$. Giving $c_f$ back to $A$, $A$ can decrypt to obtain $f(x)$.

Simple Operations

If you only want $B$ to add or multiply encrypted values you can use additively homomorphic or multiplicatively homomorphic encryption schemes which are entire practical, but leave you with very limited computations.

Some remarks

The practicality of GC and FHE largely depends on your setting and the circuit to be evaluated and is unfortunately not that nice as one would desire.

FHE is impractical at the moment, but since FHE schemes are typically constructed via a bootstrapping approach from certain somewhat homomorphic encryption (SHE) schemes (which allow to evaluate a certain class of circuits homomorphically), using a "customised" SHE scheme may be practical for some approaches, see e.g., here.

This is a very active field of research and one could write a lot about that. However, I hope this gives you some pointers to look at for further reading.


"brute force a PBKDF2-HMAC-SHA1" is not about collisions (at least, if a single hash is targeted, or if there's salt at the input of the password hash). It's a preimage attack.
The hash output by SHA-1 is 160-bit. That's 20 bytes (not characters; these are different notions, and why we have character encodings). It can take $2^{160}$ values. The output of PBKDF2-HMAC-SHA-1 has a parameterizable size that can be smaller (by truncation) or larger (essentially by aggregating 20-byte results), but the parameter is often set to 20 bytes, and we'll assume that.

Does this mean to brute force a PBKDF2-HMAC-SHA-1 an attacker only needs to consider passphrases of 20 characters or less?

No. It implies that a random value the size of the hash has probability $2^{-160}$ to match a given hash. The practical consequence is that trying at random is hopeless.
Passwords are often restricted to a subset of ASCII with about 95 characters, thus there are about $2^{131.714}$ passwords of 20 such characters or less (most of them exactly 20-character). If PBKDF2 is parametrized to perform 1000 SHA-1 hashes per PBKDF2 (which is the lowest parametrization ever consider by its definition, and has become grossly insufficient), hashing half these passwords would require over $2^{140}$ hashes, that is over $2^{40}$ (a million million) times more than wasted so far by humanity bitcoin-mining. That's just not an option.
Password search typically does not try all possible passwords over more than few characters; commonly ≈6 among ≈70 characters (only very powerful attackers could target all combinations of 10 characters when there's even mild password/key stretching). What password search does is try passwords that people could plausibly choose, approximately in decreasing likelihood of being chosen.


What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

This is the single-key Even-Mansour construction as was already noted in the comments of the question. The latest analysis I could find of this construction is by Orr Dunkelman, Nathan Keller, and Adi Shamir: "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" where they argue that any successful attack satisfies $DT=\Omega(2^n)$ with $D$ being the number of queries to the encryption oracle and $T$ being the number of queries to the permutation itself. This means that the product of these two numbers of queries scales exponentially in the width of the permutation for any attack with constant success probability. This result was also proven in the original work by Even and Mansour for the two-key case.
As for the candidate construction for a public random permutation, one should first note that this model is very close to the random oracle model (but with a permutation instead of a function). This means that any candidate construction can only offer (indirect) heuristic security. I don't have an attack on the permutation at hand though. However this is a model that is sometimes used in cryptography, e.g. in MPC applications, where one would use AES with a fixed key for such needs.


How many different ciphertexts in repeated substitution cipher?

What you are asking is how many times do you have to apply the substitution on a plaintext to arrive back at the plain text. One observation is that it will depend on the order of the substitution as an element of $S_{26}$, the permutation group on 26 elements. If your permutation has order $n$, than applying it $n$ times is the same as the identity permutation. For a given substitution, it is not hard to determine its order.
Your question is a little different. For a given plaintext, it could take fewer iterations to return back. You are interested in the permutation's action on a subset of elements and not the full set. It is going to have to do with the orbits of each plaintext letter under the permutation. So for a plaintext "abcde", how long does it take each of a, b, c, d, and e to cycle back? The answer is the LCM of those lengths. In particular, notice that the answer might be totally different for plaintext "fghij".


There is no such thing as the "strength" of the key space, just the size of the key space.

For DES and RSA the key size differs from the encoded size of the key.

DES may also contain parity bits.

For RSA the key size is usually regarded the size of the modulus as the key strength depends on the size of the modulus. But you would also have to encode the exponents and in case of the private key, possibly the CRT parameters as well. Then it is still missing padding and overhead.

Generally we still show the strength after attacks in bits. For instance, the strongest attack requires about $2^{49}$ plaintexts. As a plaintext block is $2^3$ bits, the strength of the cipher - if this attack is possible - is about 52 bits instead of the promised 56 bits. As can be seen, DES is just insecure because of the small key size rather than cryptographic weaknesses. This allows it to be used for Triple DES which may still provide adequate security even nowadays.

The original Caesar cipher just has 25 keys (not counting the 0 key of course). So the key size is 4 to 5 bits. I think we can forgo cryptanalysis here; brute force will be fastest. DES is therefore at least 47 bits stronger than the Caesar cipher.

Key size and certainly key strength can be pretty good estimates of how strong a cipher is. But never forget that these values are just extrapolations from the known attacks. We use them to simplify the world; you'd have to look into the actual attacks possible for more detailed information.

And if you use the ciphers incorrectly, you may never ever get even near the security promised.


Is it possible to carry out multiplication of BGW protocol without communication?

No, it is impossible. We do not know of any way to perform this randomization step without interaction; furthermore, it was shown in this paper that multiplication require interactions in secure computation, in a variety of important settings (including all forms of BGW-style secure computation). Share conversions work for some restricted type of functionalities, but do not allow to evaluate generic multiplication gate over $\mathbb{F}_2$ on secret shares without interaction.

Note, however, that we can have multiparty computation with no interaction (except for sending an encryption of the input and sending back an encryption of the output) in the computational setting, using fully homomorphic encryption (which we can build assuming the LWE assumption).


How to handle the extra 12451 elements in Sophie-Germain Counter Mode?

Should the value be equal to $2^{128}$ or larger and hence require more than 16 bytes of storage, the result should be truncated $\mod 2^{128}$

Note that this talks about the final tag value $Y_n$.  Truncating the final value will reduce security, but only slightly (e.g. possibly doubling the success probability of a forgery attempt, which is tiny even with a doubling).

Truncating intermediate values could potentially greatly increase the potential for forgeries.  At the very least, if you modify the proof giving a bound on the forgery probability, that bound will turn out to be 1 of a long (e.g. 2kbyte or longer) message.  I'm not certain how one could construct such a forgery, but the entire point of (S)GCM is that there is provably no high probability method.

  Is supporting multiplying by a 129-bit number required to handle this case?

Yup.

As an alternative, you might want to look up the Carter Wegman Counter mode; that is similar to SGCM, but uses the field $GF(2^{127}-1)$ (and divides the message into 15 byte blocks for the authentication pass).


The example of Wikipedia on steganography doesn't work

The Wikipedia example is something you probably would not really want to do, but does demonstrate just how much information you can add to a non-lossy image format without it being obvious to the human eye.

Importantly, the technique used in Wikipedia only works for hiding a lower-quality image of the same dimensions as the container in the low bits of the main image. More general steganography programs will attempt to store more arbitrary messages, and will use different storage strategies. It is unlikely that any would support the example approach for "hidden-image-in-image" shown in Wikipedia. Instead you can verify the Wikipedia example using a short program in e.g. Matlab, to mask out and re-normalise the low bits.

In pseudocode:

tree_image_pixels <- load_image( 'example.png' )
cat_pixels <- ( tree_image_pixels & 3 ) * 85
save_image_from_pixels( 'cat.png', cat_pixels )

The value of 85 is so that maximum pixel value is 3 * 85 = 255, using the full colour range. Lower values also work, but produce a less bright image.


What are the vulnerabilities of XOR in the following scenario?

What you basically have is a binary additive stream cipher, using your pseudorandom number generator as the keystream generator.  Used properly (i.e. in such a way that the same keystream is never used twice), the security of such a cipher depends entirely on the strength of the pseudorandom number generator.

If the output of the generator cannot be practically distinguished from a stream of truly random bits without knowing the seed of the generator, and if the seed itself is chosen randomly from a large enough space to make brute force testing of all possible seeds impractical, then such a cipher is indeed secure (in the sense of protecting the confidentiality of the plaintext; note that such XOR-based ciphers are generally malleable, and thus vulnerable to active tampering attacks).

Unfortunately, most pseudorandom number generators are not designed to remain indistinguishable from random even to a deliberate attacker; a typical PRNG's output only looks random to a casual observer, but can be easily distinguished from random if you know how the generator works.  Algorithms that are designed to resist such distinguishing attempts are generally described as CSPRNGs, or simply as stream ciphers.

If the keystream were truly random, then what you have would be a one-time pad, and would therefore indeed provide perfect secrecy (but still be malleable).  The randomness of the plaintext does not matter here — the whole point of perfect secrecy (and its computational variant, semantic security) is that a cipher with perfect secrecy will reveal no information about the plaintext whatsoever (except for its length), no matter what the plaintext may be or how it's chosen.

That said, if you intend to use the plaintext as the key to another cipher, then it certainly should be generated in such a way as to make it impractical to guess (even using massive amounts of computing power to test possible guesses).  Otherwise an attacker could just ignore your XOR stream cipher / one-time pad entirely, and simply try to guess the key to the other cipher directly.


Why do we need Euler's totient function $\varphi(N)$ in RSA?

What we really need is a number $\lambda$ satisfying $x^{\lambda+1} \equiv x \pmod n$ for all integers $x$ (which, by induction, then implies that $x^{k\lambda+1} \equiv x \pmod n$ for any $k$).

Given such a $\lambda$, and an arbitrary encryption exponent $e$ which is coprime to it, we can then find the multiplicative inverse of $e$ modulo $\lambda$, i.e. a number $d$ such that $ed \equiv 1 \pmod \lambda$, or in other words, $ed = k\lambda + 1$ for some integer $k$.  Such $e$ and $d$ then satisfy $$(x^e)^d = x^{ed} = x^{k\lambda+1} \equiv x \pmod n,$$ meaning that, if we encrypt a number by raising it to the $e$-th power modulo $n$, we can recover the original number by raising the result to the $d$-th power and again reducing it modulo $n$.  This is what we need for RSA encryption and decryption to work correctly.

The smallest such number $\lambda$ is given by the Carmichael totient function, which, for a product $n = pq$ of two primes, is $$\lambda(pq) = \operatorname{lcm}(p-1, q-1)$$ where $\operatorname{lcm}(p-1,q-1)$ denotes the least common multiple of $p-1$ and $q-1$.  However, since we don't necessarily need the smallest such number, it's also possible to use the Euler totient function $$\varphi(pq) = (p-1)(q-1)$$ which is, by definition, always a multiple of $\lambda$.

I'm not aware of any particular reason for preferring $\varphi$ over $\lambda$, except that it's slightly easier to compute $\varphi$ and to explain why it has the necessary property $x^{\varphi+1} \equiv x \pmod n$, which may be why introductory texts tend to prefer it.  I do believe, however, that actual practical RSA implementations (insofar as they explicitly compute the decryption exponent at all, rather than e.g. using the Chinese remainder theorem) generally use $\lambda$ rather than $\varphi$, since doing so yields the smallest possible decryption exponent $d$.

Addendum: The reason why $\lambda$ (and $\varphi$) satisfies $x^{\lambda+1} \equiv x \pmod n$ is basically Fermat's little theorem, which says that, for any prime $p$ and any integer $x$, $$x^p \equiv x \pmod p.$$

This can be easily generalized to show that, for any multiple $k\lambda(p)$ of $\lambda(p) = p-1$, $$x^{k\lambda(p)+1} \equiv x^{\lambda(p)+1} = x^p \equiv x \pmod p.$$

In particular, since $\lambda(pq) = \operatorname{lcm}(p-1,q-1)$ is, by definition, a multiple (and in fact, the smallest common multiple) of both $\lambda(p) = p-1$ and $\lambda(q) = q-1$, it follows that $x^{\lambda(pq)+1} \equiv x$ modulo both $p$ and $q$, and therefore, also modulo $pq = n$.

Of course, since $\varphi(pq) = (p-1)(q-1)$ is also a multiple of both $p-1$ and $q-1$, it also has the same property, as does any other common multiple of those numbers.

The fact that $\varphi(n)$ also happens to be the order of the multiplicative group modulo $n = pq$ is basically a red herring; there's nothing special about $\varphi(n)$ among all the other multiples of $\lambda(n)$ as far as RSA is concerned.  What's more relevant is that $\lambda(n)$ is the exponent of this group, which is essentially another way of stating the crucial property that $x^{\lambda(n)+1} \equiv x \pmod n$ for all $x$.


Is steganography valid only for digital images or also for printed images?

It depends on the steganography method you're using, and on how the image is printed.

Most steganography methods designed for digital images probably won't survive printing and scanning the image, or at least doing so will introduce a significant amount of noise into the concealed data that will exercise the error correction pretty hard and significantly limit the maximum payload capacity.

However, there are also steganography and watermarking methods that are designed to survive printing, or even designed specifically for printed images.  Indeed, you may have already unknowingly included such watermarks in your prints, if you've printed them on a printer that embeds a machine identification code in its output.


Can I select a large random prime using this procedure?

This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still gazillions of them. OpenSSL uses this prime generation technique.


Fix a group $E(k)$ on an elliptic curve over a field $k$.  Suppose $P \in E(k)$ is a public key.  If a signature on a message $m$ under $P$ is the encoding of a pair $(R, s)$ of a point $R \in E(k)$ and an integer $s$ satisfying (various criteria and) the equation $$[s]G = R + [H(R \mathbin\| m)]P,$$ where $G$ is the standard base point, then you can recover $$P' = [H(R \mathbin\| m)^{-1}]([s]G - R),$$ where $H(R \mathbin\| m)^{-1}$ is the inverse in the scalar ring of $E(k)$, if there is an inverse, which is guaranteed if $E(k)$ has prime order like secp256k1.  In groups of composite order like edwards25519 or FourQ, $P'$ may not be equal to $P$ but it may serve as equivalent to $P$ for the purposes of signature verification.

However, while that equation is discussed as an option in the BIP-Schnorr document, that's not the option they chose.  Rather, they chose a design where a signature is the encoding of a pair $(r, s)$ of a coordinate $r \in k$ and a scalar $s$ satisfying (various criteria and) the equation $$r = x([s]G - [H(r \mathbin\| P \mathbin\| m)]P),$$ somewhat like Ed25519, about which see for a related discussion of key privacy as even further from key recovery.  This leaves you with the snag that to compute $H(r \mathbin\| P \mathbin\| m)$ you must know $P$ already, or know some black magic to break the hash $H$.

So no, the signature scheme in the documented you cited does not enable recovery of the public key from signatures.


Show how an efficient algorithm for computing discrete logarithms with base a can be used to efficiently compute discrete logarithms with base b

Is this correct and the end of the exercise?

I can't say to what extent your professor wants you to be explicit, but it is essentially correct (and I'd accept it as an answer if I were grading it).  Now, your professor may be expecting you to explain (or give a proof) why this is correct.


Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying

Bruteforce appears to work well enough. The following Sage script finds an instance quickly:

from sage.libs.fplll.fplll import FP_LLL
from sage.libs.fplll.fplll import gen_uniform

n = 5 # dimension
q = 16 # size of matrix entries

while True:
    M = gen_uniform(n, n, q)
    L = M.LLL(delta=0.999)
    S = FP_LLL(L).shortest_vector(algorithm='proved')
    if min([ row.norm() for row in L]) != S.norm():
        break

print M
print L
print min([ row.norm() for row in L])
print S
print S.norm()

As a concrete example, the lattice (column vectors)
$$L =
\begin{pmatrix}
16252&  5541& 48769&  2593& 22395\\
 2404& 46418&  5335& 59631& 29390\\
41816& 27475& 56363& 50417& 62371\\
27419& 53783&  1412& 42344& 55983\\
62503& 52719& 22160&  3940& 64256\\
\end{pmatrix}
$$
can be reduced with LLL ($\delta = 0.999$) to
$$B=
\begin{pmatrix}
  1855&  31849 & -6182&  -5480&  16007\\
 23160& -24484 &  2259& -11807&  10586\\
 29450&   -465 &  8167&   2997& -19059\\
 10069&  -8429 & 24671& -21117& -18320\\
  4328& -17879 & 30280&  29190&  24708\\
\end{pmatrix}
$$
Yet, none of those vectors is the shortest. The shortest vector is $$(-19381, -7964, 16504, -24114, 739),$$ which can be written as $2L_0 - L_1 - L_2 + 2L_3 - L_4$, where $L_i$ is the $i$th row of $L$. So we have $n = 5$ and $r = 2$.


Trying to understand the constant factors (19 and 38) in Ed25519 ref10 function 'fe_mul'

The section 'Radix-$2^{64}$ representation' on page 11 of the Ed25519 paper ("High-speed high-security signatures" by Bernstein et al.) actually explains the technique. I should have read the paper more carefully.

As pointed out by CodesInChaos, the order of the field is $p=2^{255}-19$ and the 38 corresponds to $2p=2^{256}-38$.


$\quad$ chosen-prefix partial collisions for scrypt

This does somewhat better at #3 than your second option because

working requires storing previously obtained scrypt outputs.

(I think it would be better to require a at most a given Hamming distance between the outputs rather

than equality of a specific set of bits of the output. $\:$ The first of those would require storing the

entirety of the outputs, while the second would only require storing the relevant bits of the output.)


symmetric AES encryption with php produces different result than openssl MacOX

Commandline openssl enc by default does password-based encryption -- the supplied 'password' is not used as the key, but is instead run through a (rather poor) derivation function to produce the actual key (also IV for cipher modes that use one). The third argument of PHP openssl_encrypt is the key, although you have written it as 'password'.

You can give enc the actual key instead of a password by using -K (uppercase, not -k) with the key in hex. When using this option you also need to provide the IV explicitly with -iv and hex if the cipher mode requires it, but ECB doesn't. See http://php.net/manual/en/function.openssl-encrypt.php#104438 .

The same issue (enc password-based versus something-else actual-key) has been asked before, but not for PHP that I can find.
https://stackoverflow.com/questions/37354200/blowfish-encrypt-in-java-scala-and-decrypt-in-bash
https://stackoverflow.com/questions/45855972/different-results-when-encrypting-with-openssl
Discrepancy between 3DES in OpenSSL and PyDES

PS: if you don't set OPENSSL_RAW_DATA, openssl_encrypt does base64 for you.


How would I go about breaking Playfair cipher with the alphabet and the encrypted message?

If by alphabet you just mean that you know the letters A-Z are being used apart from identifying I with J, the best place to start is by looking for common digraphs (pairs of letters). There are lists of the most common digraphs in English and if you have a long enough message you should be able to identify likely candidates. Indeed, if your ciphertext is long enough just digraph frequency will be enough.
For shorter ciphertexts, try to chain common digraphs together in the text to form words and guess less common digraphs. For Playfair note that recovering a digraph also gives you the reverse. Also specifically to Playfair, look for plaintext digraphs that contain the same letter (e.g. digraphs of the form E or E) the ciphertexts corresponding to these digraphs should give you strong clues to letters in the Playfair square that are in the same row and column as E. For example, if you see the digraph HE encoded as BX then there's a good chance X is in the same row as E and B is in the same row as B is in the same column.
Some good news is that there are many different Playfair squares that lead to the same encryption method.
Depending how much ciphertext you have, the rest is less science and more art. Don't be afraid to make wild leaps or assumptions, but equally don't be afraid to throw away large amounts of work and start again from scratch. A fuller treatment for breaking Playfair can be found in Chapter XXI of the classic text Cryptanalysis by Helen Fouche Gaines.


With the numbering in your comment: 1 yes, 2 no.

If you just need to encrypt files, use age if you can.

I'm going to answer the rest of this in the context of using libsodium as your cryptographic library. You might have a different choice, like NaCl or , but any choice should support a high-level API like I'll describe. If your library doesn't, it's not safe and you should pick a better one.

For generating random numbers (nonces, salts, etc), use your library's secure random generation function(s). For libsodium, this is almost always going to be the randombytes_buf function.

For turning a password into a key, use your library's password hashing function. If that's libsodium, you want to hash it using the crypto_pwhash function. That takes in a random salt generated via randombytes_buf, some parameter limits, and a password, and outputs a key. You'll need to store the parameters and the salt with the encrypted data.

The reason to use the password-derived key as a KEK instead of using it directly is to allow the user to change their password without needing to re-encrypt all the data. You'd just need to re-encrypt the actual data key. The encryption method used should be your library's preferred authenticated encryption function. For libsodium, that's crypto_secretbox_easy (and decryption is crypto_secretbox_open_easy). If you don't actually need this functionality, don't include it, just use the output key of the PBKDF to encrypt the data.

You don't need to check that the data has been decrypted successfully. That's handled by the Authentication part of an AEAD (Authenticated Encryption with Associated Data) mode. If the authentication tag verifies, it decrypts correctly. If it doesn't verify, it discards the (potentially very dangerous) decrypted data without doing anything else to it.

Assuming you have to use libsodium or similar and are going with the KEK system, you'll need a random salt, a unique nonce for the AEAD encrypting/decrypting the data key with the password-derived KEK, and a second unique nonce for encrypting/decrypting the data.


The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, for a good cryptographic hash, we don't know any way of finding a string with a particular hash, except for trial and error.

In particular, cryptographic hash values are close enough to truly random that the birthday paradox applies. That is, if there are $k$ different values the hash can take and they're all equally likely, you have to hash roughly $\sqrt{k}$ documents before the probability of finding two with the same hash is greater than a half.  So, if you're using a 256-bit hash, you'd need to look at about $\sqrt{2^{256}}=2^{128}\approx 3\times 10^{38}$ documents to even have a 50/50 chance of finding two with the same hash. For comparison, that's about 200 documents for every nanogram of mass in the Earth.


Why isn't ElGamal a symmetric-key scheme?

g^x is the public key of Alice and x her private key, while g^y is the public key of Bob and y his private key.

s=g^(xy) is the shared secret between Alice and bob, that can only be computed by them.

Thus, ElGamal is an asymmetric algorithm computing a shared secret that can be used as a symmetric key.


PBKDF2 uses HMAC-SHA1 to generate keys, but what is the key for the HMAC?

PBKDF2 uses the password as the PRF key.

From the RFC:

  The first argument to the pseudorandom function PRF serves as HMAC's
     "key," and the second serves as HMAC's "text." In the case of PBKDF2,
     the "key" is thus the password and the "text" is the salt.


Why is a proxy needed in proxy re-encryption?

If Bob has the re-encryption key from Alice, then he can re-encrypt all Alice's ciphertexts stored online and then decrypt these messages. This is not good because Alice may only want to reveal some small subset of messages to Bob but not all. Similar things happen if Alice knows Bob's re-encryption key. Furthermore, the proxy is also not fully trusted, i.e., knowing Alice and Bob's re-encryption keys is not enough for the proxy to decrypt the online ciphertexts either (because it does not know Alice and Bob's private keys). On the other hand, if the proxy and, say, Bob collude, then they can decrypt all Alice's ciphertexts.


How expensive would running a practical application on full homomorphic encryption be?

This will likely be rather expensive. This is because the problem you describe seems like it would be hard to express as a shallow arithmetic circuit, which is a rough estimate of how difficult the computation is with FHE.
In particular, a naive algorithm for solving your problem is:

Instantiate some hashmap
Iterate through your textfile, when you see the character " ", chunk off the previous block of text and add it to the hashmap.
Throughout this, record the last bit of text you chunked off for future use in computing what to chunk
Return the hashmap

This has $O(n)$ complexity, and in practice should be only slightly less efficient than reading the entire array of text. Essentially no part of it translates well into FHE though. FHE evaluates programs on encrypted data where the programs are expressed as circuits (essentially standard programs where the computational path may not depend on the data).
The above program seems difficult to implement as a circuit efficiently. Both of the non-trivial parts of the program (instantiating/using a hashmap, and the iterative "chunking" operation) seem pretty bad for this.
This can be worse if you use a variable-length text encoding such as UTF-8, but even for a fixed-length encoding (such as ASCII) it seems pretty bad.
If you want to get an explicit estimate of the complexity, you would first need to generate some fixed circuit implementing your desired function.
There are some transpilers for "standard" programming languages to arithmetic circuits (this paper describes a transpiler (implemented here) from some subset of C to arithmetic circuits.
I haven't checked if it suffices for this program) that you can leverage to do this, but I won't bother for this answer.
Even some of the more basic parts of the computation (checking if a character is equal to " ") is rather difficult in FHE --- equality testing is difficult to express as a low-degree polynomial, and therefore difficult to express as a low-(multiplicative) depth circuit.
Anyway, I would guess it would cost $\gg\\\$1$.
I don't have order-of-magnitude estimates, but whatever the final number if I doubt you could convince customers to pay it rather than buying their own (trusted) server that they outsource plaintext computations to (this is both more generally useful, is a one-time cost vs a per computation cost, etc).
The big draw of FHE are for computations where:

Buying a trusted server is not an option (say computing functions of data from several mutually non-trusting sources)

"Simple" computations (where simple means something like "is expressible as a low-depth arithmetic circuit", or equivalently "is expressible as a low-degree polynomial").

An example application is that of computing statistical tests on medical data, which is (from my perspective) still the most compelling application of FHE, rather than "renting cloud-compute in a `trusted' way".
Note that there is currently a big push for hardware implementation of FHE, which may change this picture in the near-term.


Do any other factors aside from length of input affect the runtime of the SHA-256 hashing algorithm?

Your question is not very clear, but I assume you're asking whether the runtime of a SHA-256 invocation depends on anything about the input other than its length. In other words, if an adversary knows how long it takes to calculate SHA-256(M1) and SHA-256(M2), does this leak any information about M1 and M2 other than their length?
The answer, with plausible implementations, is no. SHA-256 (like all common hash algorithms: MD5, SHA-1, SHA2, SHA3, Blake, etc.) only uses the message for bitwise operations (and, or, xor, shifts by a constant size, negation) and additions. All of these operations use a constant time on all common (and most imaginable) hardware, and compilers are very unlikely to turn them into non-constant-time operations. There are no multiplications or divisions (which on many CPU are not constant-time), no shifts by a message-dependent amount, no conditions or table lookups based on a value that's derived from the message content (other than the message's size).
So unlike, say, AES (where the most natural implementation involves a table lookup based on values derived from the key), you generally don't have to worry about timing-related side channels in SHA-256 or other common hash algorithms.
On the other hand, leaks from power consumption can be a worry.


Iterative hashing increases number of security bits?

how does iterative hashing affects security (measured in) bits?

It does so by increasing the number of operations likely required to solve the problem by brute force, because an operation is what's iterated in each attempt of break.

  (iterative hashing) does not affect entropy

Indeed, iterative hashing does not increase¹ entropy. It can still increase security.

  $n$-bit security means that adversary needs to perform $2^n$ operations to break the system.

Yes, for some definition of operation, and certainty to break the system.

If there's an attack with $N$ operations that succeeds with probability $p$, and $p$ grows linearly with $N$ until $p=1$ as in key search, then the system has at most $$n=\log_2(N/p)=\log_2(N)-\log_2(p)\text{ bit security}$$

This formula works including for low $p$ and any $N\ge1$. Customarily, it is used also when $p$ only grows about linearly with $N$ until $p$ reaches a non-negligible value, e.g. because $p=e^{-N_0/N}$ as in preimage search.

The question's Whatsapp system re-formats 32-byte ECC public keys into 30-decimal digit strings that appear nearly uniformly distributed. The main design goal is to make it hard to generate a private key which matching public key re-formats to one (or more) given strings obtained by re-formatting one (or more) target public key(s); that is, make second preimage search difficult.

A brute force preimage attack against this system generates key pairs; hashes the public key 5200 times with SHA-512; and makes a test against the targeted value(s). Each private key test has probability $p=10^{-30}$ to match a given string. Each test costs 5200 iterations of SHA-512 and comparatively little else (an increment of the private key, an ECC point addition of a constant point to the previous public key, typically one (at most 6) comparison against 5 digits of the given string of the modular reduction modulo $10^5$ of part of the SHA-512 hash).

It follows that security is $\log_2(5200)+30\log_2(10)\approx112.00$-bit when the cost is counted in SHA-512 hashes, which is the natural metric here, and there's a single target key. For $s$ target strings/keys, the probability of success of each test is increased by a factor $s$, thus security is reduced by $\log_2(s)$ bit.

Notes:

A former version of this answer was about the security increase with increased iteration count in a cryptosystem where there are sizably much other operations beyond iterated hashing. That's not relevant in the question's context, thus removed.

¹ : The simplest forms of iterative hashing, including the one in the question's Whatsapp context even slightly reduce entropy; see this.


Sign a plaintext accepted by a secure function without revealing private key

The cryptographic primitive you're looking for is known as functional signature: in a functional signature scheme, there is a standard signature and verification key pair, as well as an algorithm to derive functional signature and verification keys, for any function $f$. The signature scheme then allows to sign any message $m$ in the range of $f$. The notion was introduced in this paper (see also the papers that cite it on Google scholar, for more recent constructions).

To get a solution to your problem out of this, let me call $P$ the program that checks whether $m$ is a good recipe. Define $f$ as follow: $f(m)$ returns $m$ if $P(m) = 1$, and the symbol $\bot$ otherwise. Now, if Bob (who knows the signing key for this function $f$) can sign a recipe $m \neq \bot$, this means that $m$ is in the range of $f$, hence that $P(m)=1$.

From your scenario, I suppose that you additionally have a function-privacy requirement: $f$ should not be publicly known (otherwise anyone could always check whether a recipe is nice, without the help of Alice), hence the functional signature key should hide $f$. This is known as function-private functional signatures, and is also defined and constructed in the paper I mentioned above. Such a scheme can be constructed for any polytime-computable function, assuming one-way functions and succinct non-interactive zero-knowledge arguments. The latter is a strong assumption, but we now have relatively efficient constructions of such arguments for functions of reasonable size (although probably not standardised implementations) - for example, this one was published a few days ago on ePrint, and seems quite efficient.

Note that none of this would be "incredibly efficient", but still fairly feasible.


There's not a word about the data to authenticate! Update: we are told that's data from a row in database with 4 different columns: Date(YYYY-MM-DD), Time (hh:mm:ss), String(xxxxx), Number (1000.00). It is of paramount importance to specify how this data is transformed into byte before entering HMAC. Concatenation would be dangerous for the last two fields, because in digitsfollow12 34.56 and digitsfollow123 4.56 would give the same MAC.

The hash you want to specify is usually designated SHA-1, not SHA1.

SHA-1 is obsolete, even though when combined with HMAC it remains safe and thus tolerated. A modern replacement would be SHA-256 or SHA-512, followed by truncation of the final HMAC result if a 160-bit output is desired.

The data block size B is redundant with specifying SHA-1, and will need to be kept in sync with the hash. I would suppress that.

Ipad and Opad, and their repetition count, are redundant with the specification of HMAC. I would suppress that.

"Charset = UTF-8" does not make sense to me, unless you want some encoding (like Base-64), or it applies to the data to authenticate, in which case that should be told.

It is not specified how various parameters are passed: array of chars, string, and nature of that; and if the length (e.g. of data to authenticate) is separate or some attribute of an object, and in what unit (bytes, bits), and the maximum. It is not told wether data to authenticate is passed in one block or iteratively.

Giving an example in a spec helps immensely.


Publicly verifiable secret sharing scheme

Here's my understanding:

The input of the hash is $x_i,y_i,a_{1i},a_{2i}$.
The output of the hash is $c$.

The wording is '$c$ is computed as ...'

And later the verifier checks if $c$ matches the Output of the hash function used on the same input variables. If different values were used in the original run, the hash would differ.

So yes, you misunderstood the statement.


The notion of proofs (resp., argument) of knowledge was introduced in [GMR] (resp., [BCLL]), but the definition in both the papers is more intuitive than formal. Attempts were made at more formal definitions in [FFS] and [FS]. The culmination of these lines of work (I believe) is [BG], which is what I would recommend reading since (i) it post-dates the other works and (ii) it provides a good summary of the previous definitions (see Appendix A). [BG] focuses on proofs of knowledge, but the definitions for arguments of knowledge is similar (see §4.7).
Addendum. As @Yehuda Lindell points out, the textbook definition in [G] is worth looking into and it seems that the definition there closely follows [BG] (see the historical notes in §4.12.1).
[BCLL], Brassard, Crépeau, Laplante and Léger, Computationally Convincing Proofs of Knowledge, STACS'91
[BG] Bellare and Goldreich, On Defining Proofs of Knowledge, Crypto'92
Feige, Fiat and Shamir, Zero-knowledge proofs of identity, STOC'87
Feige and Shamir, Witness indistinguishable and witness hiding protocols, STOC'90
Goldwasser, Micali and Rackoff, The Knowledge Complexity of Interactive Proof-Systems, STOC'85
Goldreich, Foundations of Cryptography, Volume 1


No, the set of AES-CTR keystreams is not closed under XOR.  That is to say, in general, for any two AES keys $K_A$ and $K_B$ there will not exist a third key $K_C$ such that $$\textsf{AES}_{K_A}(x) \oplus \textsf{AES}_{K_B}(x) = \textsf{AES}_{K_C}(x)$$ for all $x$.

At least, there is no reason to expect that such a key $K_C$ could be found.  Offhand, I can't think of an obvious way to prove that one could not just somehow magically exist, but that would seem to require either a truly astronomical coincidence or a deep and fundamental weakness in AES.

In fact, there's a simple counting argument suggesting that this should never happen, simply because the set of possible CTR mode keystreams is immensely larger than the (already very large) set of AES keys.
Specifically, AES keys are 128, 192 or 256 bits long, depending on the AES variant used, but an AES-CTR keystream repeats with a period of $128 \cdot 2^{128}$ bits.  Thus, out of the $2^{128\cdot2^{128}}$ theoretically possible keystreams with that period, only $2^{256}$ can actually be generated by AES-256-CTR (and even fewer for the other AES variants).

Since the mapping from AES keys to the corresponding keystreams is supposed to be effectively indistinguishable from random, that also means that the probability of the XOR of any two AES-CTR keystreams just happening to itself be an AES-CTR keystream is at most one in $2^{128 \cdot 2^{128} - 256}$, i.e. effectively zero for all practical purposes.*

Of course, we do know that the mapping from AES keys to keystreams is not actually random, and there are even some known related-key attacks on AES that demonstrate this.  But as far as I know, nobody's ever found anything to suggest that the XOR of two AES-CTR keystreams would be any more likely to match another AES-CTR keystream than the infinitesimally small probability of that happening by chance.

*) Literally.  That's a probability of about $1/10^{10^{40}}$, i.e. about 0.00000...0001, where the ... stands for about 10 000 000 000 000 000 000 000 000 000 000 000 000 000 more zeros, give or take a few (or a few decillion).


Is this a correctly formatted PGP session key packet?

Here's what pgpdump thinks of it:

New: Public-Key Encrypted Session Key Packet(tag 1)(142 bytes)
        New version(3)
        Key ID - 0xF940C4301A67779D
        Pub alg - ElGamal Encrypt-Only(pub 16)
        ElGamal g^k mod p(511 bits) - ...
        ElGamal m * y^k mod p(511 bits) - ...
                -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02

So there's nothing obviously wrong, but you'd have to pass it through a full PGP implementation to verify that it's all OK.


Misuse-resistant authenticated encryption based on SHA-3/Blake2b and AES-CTR/ChaCha20

256-bit confidentiality

Let's assume that we're using AES256-CTR and a 256-bit hash.  A new 256-bit key $S$ is derived for each message.  Since AES256 requires a 256-bit key, there are no extra bits in $S$ available for use in the nonce, suggesting that a constant nonce is used.  I believe this is vulnerable to a multi-target attack.

The first block of ciphertext $C_0 = \text{AES256}(S, 0^{128}) \oplus P_0$, where $P_0$ is the first block of plaintext.  Suppose that this block is predictable to the attacker (think of SMTP for example: it's not unusual for the first 16 bytes to be predictable) or attacker-controlled.  The attacker can compute $K_0 = C_0 \oplus P_0 = \text{AES256}(S, 0^{128})$ to get the direct output of the block cipher.

Suppose that the attacker can observe (and maybe encourage the sending of) lots of encrypted messages.  The attacker can compute $\text{AES256}(x, 0^{128})$ for many values of $x$, and check to see if any of those values match any of the $K_0$s the attacker observed.  With $2^{20}$ messages (and therefore $2^{20}$ $K_0$s), the attacker should find an $x$ that works after about $2^{256-20} = 2^{236}$ tries, allowing the attacker to decrypt a single message.  I believe this violates the claim of 256-bit confidentiality.

A similar attack can be applied to ChaCha20 when it is used with a constant nonce.  In the case of a 512-bit hash, this seems to leave enough bits of $S$ for a complete nonce, which should mitigate this attack.

  The message is rejected unless $t=t'$.

This is an implementation issue, but this is vulnerable to timing attacks unless a constant-time comparison is used.


How to use HMAC for authenticating multiple messages

If the hashing function $H$ is secure, then $H(H(K, m_1), m_2)$ is secure. But at the cost of applying $H$ twice.


The scheme as you describe it in itself may be secure in some (especially) theoretical environment.
However, I don't suggest to use it, because any attempt to use of values passed between the peers can possibly undermine the security of the scheme as can e.g. insecure RNGs.

I have expressed a few concerns below.

I'm bit concerned about calling the scheme OTP anything, because this this is not OTP. A comment from daniel already mentioned when this practice is secure:

As long as you have after each use, n+1 unknowns on n equations, that's the preshared value plus each key value, seems hard to break (or impossible). Another thing is if it's advisable to use such a protocol for other reasons.

This was in the question:

  I was thinking of ways to pass encryption keys and IVs - which, if properly generated, should be very random data - between two systems.

What do you do with these keys and IVs? Consider they are for instance, used to encrypt data. Also suppose the adversary gets hands on ciphertext and (partial) plaintext processed with these encryption keys (unknown to adversary) and IVs:

The block cipher modes of operation (generally) do not protect IV from disclosure. This is because IV should be value unpredictable by the attacker before it is used. It may be, however, possible for attacker to determine the used IV afterwards; occasionally even pretty easily.
The adversary can use computational attacks the keys instead of information theoretic attacks (like against OTP. This may not be great deal, as for many algorithms keys are pretty hard to break).

Example of foul play

I decided to write an example of foul play, based on my understanding of the scenario written. It is not illustrated very clearly in the question what are the possible uses of communicated values, but this explanation tries to capitalize my point that using the exchanged values easily causes security issues. It is possible the example as-is does not apply here.

Assume that the Key+IV secured with multi time pad is used to do AES-CBC. Also assume that each Key+IV is "secured" with the same pad. The attacker can alter data messages sent (known as $M_i$ below).

We get for first keys and IVs (assuming this scheme uses "XOR" operation), A is multiply used pad:

$M_1 = A \oplus (Key_{1} || IV_{1})$
$M_2 = A \oplus (Key_{2} || IV_{2})$

The attacker may affect contents of $Key_{1}$ and $Key_{2}$. It may be possible to e.g. set keys and IVs to be the same for two different uses. (By replacing $M_2$ with $M_1$.)

Some other concerns

  Let's presume they have a trusted channel by which they can exchange the one-time pad, but wish to use an untrusted channel for exchanging more voluminous data.

How much faster your untrusted channel is than trusted channel, i.e. how many times you intent to reuse "OTP"?

Where do you get the "plaintext stream" containing passwords and IVs? It is common that random number generators do not provide completely i.i.d. as is required by the scheme you describe.

If you have "OTP" that is kept scret and you use it multiple times to pass secret, this actually becomes some sort of secret sharing scheme. You should examine them to understand how to use them correctly.


what's the purpose of passphrase in hybrid cryptography?

Some systems like SSH will use passphrases to control the use of private keys: instead of storing the private key unencrypted on disk it's stored encrypted (symmetrically) by a key derived from a passphrase. That ensures that only an authorized user can use the SSH key pair to access a remote system.
There's no requirement for passphrases in hybrid cryptography in general. EG TLS doesn't use passphrases and involves hybrid cryptography (asymmetric key exchange + symmetric encryption).


It would be disastrous if an RSA key generation procedure had a sizable probability to end with $e=d$, because in that case, the public key reveals the private key, which must be secret from a security perspective.
But $e=d$ is a symptom of a larger problem lying in steps 1 and 2 of the key generation procedure: RSA can only be secure if $p$ and $q$ are selected in a way such that factoring $n$ is hard, and that means $p$ and $q$ should be large primes. The modern baseline is $n$ of $2048$ bits, that is $617$ decimal digits, not $4$ decimal digits. For this, $p$ and $q$ are chosen randomly among a sizable subset of primes of about $309$ digits. There are over about $10^{305}$ such primes, thus generating them all then picking within that is infeasible. The right procedure is to directly generate $p$ and $q$.
With $p$ and $q$ random primes this large, and a random choice of $e$ such that $\gcd(e,\phi(n))=1$ (or a random choice of primes $p$ and $q$ with the only dependency on $e$ that $\gcd(e,p-1)=1$ and $\gcd(e,q-1)=1$, as is common practice), it's infinitesimally improbable that $d=e$, or more generally that one or a few re-encryption(s) lead to decryption. See these questions on the cycling attack.

There are RSA key generation procedures in FIPS 186-4 appendix B.3. Ignore the proposed $1024$-bit key size, which is obsolete. The proposed $2048$ is the baseline, $3072$ increasingly common, extending to $4096$-bit not unreasonable. These procedures differ from those used in the question by several points including:

Generating large primes $p$ and $q$ unpredictably in a prescribed interval $[2^{(k-1)/2},2^{k/2}]$, where $k$ is the desired bit size of $n$ (e.g. $3072$)
Requiring odd $e$ with $2^{16}<e<2^{256}$ (the lower because that acts as a safeguard against poor choices of RSA padding, the higher for interoperability and to make some other poor choices impossible)
Using $d=e^{-1}\bmod\lambda(n)$ (where $\lambda$ is the Carmichael function) rather than $d=e^{-1}\bmod\phi(n)$. Both are mathematically fine, but using $\lambda$ insures generating the smallest positive private exponent $d$ working for a given $(n,e)$.
Requiring a minimum size of $d$ (much larger than $2^{256}$, which incidentally insures $d>e$), more as a safeguard against errors than out of mathematical necessity.


The adversary $\mathcal A$ is an entity (think of a computer program) designed to participate in the experiment $\operatorname{PrivK}^{\text{eav}}_{A,\Pi}$.

So the adversary produces two messages, then is given the encryption of one of them, and has to guess which one it was.

Of course, you can give the adversary other "ciphertexts" too, but this wouldn't be the same experiment, and the results of this thus don't matter for the experiment (they might be interesting in other experiments, though).

The proof does only have to consider the behavior of the adversary in the experiment, not in other cases.


What is the RFC order of peer certificate verification, trust chain or expiry first?

Untrusted certificate or expired certificate?

If you go strictly by RFC 5280 ordering, "untrusted certificate" should be returned.

More specifically section 6.1.3 starts with

   The basic path processing actions to be performed for certificate i
   (for all i in [1..n]) are listed below.

      (a)  Verify the basic certificate information.  The certificate
           MUST satisfy each of the following:

         (1)  The signature on the certificate can be verified using
              working_public_key_algorithm, the working_public_key, and
              the working_public_key_parameters.

         (2)  The certificate validity period includes the current time.

As RFC 5280 goes the from signer to signee, the current working_public_key is the ones of all trusted CAs (section 6.1.2 (h)). As the CA in question is not trusted, no public key will yield a successful validation. As this is checked before the expiration, it should yield the error.

Note that this also makes sense from a cryptographic standpoint, as you always want to make sure that your data is authentic before parsing it to avoid malicious data (like maliciously crafted certificates) to break and exploit your parser.


How to attack a classical cipher using known partial plaintext?


What are the issues of look-up table based implementations?

The disadvantages are simply the side-channel attacks that you mention.  I can think of no other disadvantages from either a cryptographic or hardware angle.    I have a description of cache and attacks from a hardware perspective.

The advantages are pretty clear:

simplicity in implementation so that the mathematics is correct;
it's faster than a bit-slice implementation, and
it's smaller than doing the inverse mathematics for the irreducible polynomial.

Also, in non-x86 environments, these attacks are be mitigated through a cache lock where you do not flush the cache so you cannot miss.