Are Anonymity and Authentication possible together? Anonymity and authentication look to be seemingly contradictory but are both possible together ? I tried reading couple of papers but could not get the big picture. So what are the major approaches tried in solving anonymity preserving authentication ? (Am not really looking for references or recommendations but the solution approaches tried so far, there is not any wikipedia page too to get a summary)

First, authentication is not really “proving that someone is who they say they are”, but linking an action, message or situation with an identity. If I show my passport to prove who I am, what I am really doing is linking my physical presence with the identity conferred to me by the state of which I am a national.

A person may well have multiple identities. For example, people with dual citizenship have two passports and what they do with one is somewhat decoupled with what they do with the other.

Multiple identities are the basis of anonymity. Indeed, as soon as you interact with anyone else in any way, this creates an identity: you're the person who did this thing at that time. Anonymity is not a lack of identity, but a lack of a link between a certain identity and any other identity that you may have.

Coming back to authentication, it is a link between two identities: the person who did that thing at this time is the same person who owns these credentials. Phrased this way, authentication is exactly contradictory with anonymity. However, there are many situations where it is useful to have partial authentication or partial anonymity.

An obvious solution to partial anonymity is to have a trusted third party as an intermediary. I'm using one right now: you know me by my Stack Exchange account, and you can use this identity to authenticate my Stack Exchange activity. Stack Exchange knows me by an identity with an OpenID provider, but isn't telling you. My OpenID provider in turn knows some things about me, but they only know the name on my passport if I've been telling them. There is a chain of links between identities (which could be traced all the way to, say, my home address via ISP logs), but you need the collaboration of multiple parties to resolve the chain.

How satisfactory such situations are depends on how the identification linkage chain is set up and what parties you're prepared to trust. Having identification linkage chains that are practically impossible to trace is the basis of anonymity systems such as TOR.

Going in another direction, authentication is very often used for authorization. I may use this account because I am the account owner. I may enter this building because I am an employee. An authorization system can be set up to decouple the action that is being authorized from the identity that led to the authorization. A well-known example is voting systems: they have both strong authorization requirements (only registered voters may vote, and only once per election) and strong anonymity requirements (even I cannot prove who I voted for, at least not if I want my vote to be counted). In traditional voting systems, anonymity is ensured by stepping into a booth to put a standardized piece of paper in an opaque envelope. Anonymity is ensured by observers who control that everyone steps into the booth and by rules that make non-anonymous ballots void.

Reference: https://security.stackexchange.com/questions/47913/is-the-concept-of-authenticated-anonymity-possible


Is Caesar cipher perfectly secret? The only time a shift cipher considers to be perfectly secure is when used on a single letter of plaintext and no more. Having that in mind, we can say it is certainly not perfectly secure.
Caesar cipher is perfectly secret only in the special case with the assumption that 26 keys are used in equal probability. Suppose that we have a plaintext of 50 characters long if each key for each character is chosen equiprobably then you end with
26^50 possible keys.
That is my answer, is it correct?

Yes, because instead of a Caesar cipher you now have a One-time pad.
In particular, it meets the requirements of a key that is random and as long as the message. So as long as the key is kept secret and never used for another message, you have OTP security.


modular reduction algorithm over $F_{2^m}$ doesn't seem to work when order of polynomial being reduced is small I was considering algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography and...  it doesn't appear to work when the order of the polynomial you're trying to reduce is less than the order of the reduction polynomial.

Say you have a reduction polynomial of $x^{128}+x^7+x^2+x^1+1$ (the GCM reduction polynomial) and are trying to reduce $x^{127}$.

With polynomial division the quotient is $0$ and the remainder is $x^{127}$ but algorithm 2.40 in the ... seems to give $0$ as the answer.

In the for loop $i$ is going from the $2m - 2$'th bit (more specifically, the coefficient of $x^i$) downto the $m$'th, where $m$ is the order of the reduction polynomial ($128$). So you never actually get to $x^{127}$ and so nothing is ever added to $C\{j\}$ and thus the return value is $0$.

Is my analysis correct? If so that would seem to imply that the algorithm given n the Guide to Elliptic Curve Cryptography is insufficient and it's inclusion probably ought to be considered errata?

In the for loop $i$ is going from the $2m - 2$'th bit (more specifically, the coefficient of $x^i$) downto the $m$'th, where $m$ is the order of the reduction polynomial ($128$). So you never actually get to $x^{127}$ and so nothing is ever added to $C\{j\}$ and thus the return value is $0$.

Actually, $C$ starts off initialized to the input polynomial $c(z)$, and so by not adding anything, the final $C$ value is precisely the initial value, which is the correct answer.

They could have written the algorithm clearer by explicitly stating that, and using the same case for $C$ consistently...


If the first key-bit is flipped, which DES s-boxes are affected? Instead of the input bit being flipped... if the 1st bit of the key is being flipped, which s-boxes are affected during encryption/decryption of DES?

Permuted Choice 1 determines how an input block is loaded into C and D Registers:

Permuted Choice 1 is selection permutation describing how to load C and D registers from 8 successive bytes of input key, noting the LSB is only used for parity. (The big endian bit in byte ordering is from IBM).

Permuted Choice 2 determines which C and D Register bits are used as input to f(R,K):

Permuted Choice 2 is also a selection permutation selecting two 24 bit values from each of the C and D 28 bit registers which are shifted according to the key schedule.

The DES standard also defines which selected Key bits are associated with each S Box:

This shows the E Permutation as values of R exclusive OR'd with selected key bits as input to the 8 S Boxes.

The Key Schedule causes rotations in the C and D registers bringing different key bits into play in different rounds.

The program keytab.c reproduces two tables from the Meyers Metyas book Cryptography.

Invoking keytab -b will fill an input block with input block indexes for each position convert those locations to the appropriate locations in the C and D Registers, iterate the key schedule and produce the selected Key for each round through PC2 giving a list of Ks bits referencing the input block indexes:

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
   1  10 51 34 60 49 17 33 57  2  9 19 42  3 35 26 25 44 58 59  1 36 27 18 41
   2   2 43 26 52 41  9 25 49 59  1 11 34 60 27 18 17 36 50 51 58 57 19 10 33
   3  51 27 10 36 25 58  9 33 43 50 60 18 44 11  2  1 49 34 35 42 41  3 59 17
   4  35 11 59 49  9 42 58 17 27 34 44  2 57 60 51 50 33 18 19 26 25 52 43  1
   5  19 60 43 33 58 26 42  1 11 18 57 51 41 44 35 34 17  2  3 10  9 36 27 50
   6   3 44 27 17 42 10 26 50 60  2 41 35 25 57 19 18  1 51 52 59 58 49 11 34
   7  52 57 11  1 26 59 10 34 44 51 25 19  9 41  3  2 50 35 36 43 42 33 60 18
   8  36 41 60 50 10 43 59 18 57 35  9  3 58 25 52 51 34 19 49 27 26 17 44  2
   9  57 33 52 42  2 35 51 10 49 27  1 60 50 17 44 43 26 11 41 19 18  9 36 59
  10  41 17 36 26 51 19 35 59 33 11 50 44 34  1 57 27 10 60 25  3  2 58 49 43
  11  25  1 49 10 35  3 19 43 17 60 34 57 18 50 41 11 59 44  9 52 51 42 33 27
  12   9 50 33 59 19 52  3 27  1 44 18 41  2 34 25 60 43 57 58 36 35 26 17 11
  13  58 34 17 43  3 36 52 11 50 57  2 25 51 18  9 44 27 41 42 49 19 10  1 60
  14  42 18  1 27 52 49 36 60 34 41 51  9 35  2 58 57 11 25 26 33  3 59 50 44
  15  26  2 50 11 36 33 49 44 18 25 35 58 19 51 42 41 60  9 10 17 52 43 34 57
  16  18 59 42  3 57 25 41 36 10 17 27 50 11 43 34 33 52  1  2  9 44 35 26 49

  Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
   1  22 28 39 54 37  4 47 30  5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31
   2  14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55  7 12 37  6  5 54 47 23
   3  61  4 15 30 13 47 23  6 12 29 62  5 37 28 14 39 54 63 21 53 20 38 31  7
   4  45 55 62 14 28 31  7 53 63 13 46 20 21 12 61 23 38 47  5 37  4 22 15 54
   5  29 39 46 61 12 15 54 37 47 28 30  4  5 63 45  7 22 31 20 21 55  6 62 38
   6  13 23 30 45 63 62 38 21 31 12 14 55 20 47 29 54  6 15  4  5 39 53 46 22
   7  28  7 14 29 47 46 22  5 15 63 61 39  4 31 13 38 53 62 55 20 23 37 30  6
   8  12 54 61 13 31 30  6 20 62 47 45 23 55 15 28 22 37 46 39  4  7 21 14 53
   9   4 46 53  5 23 22 61 12 54 39 37 15 47  7 20 14 29 38 31 63 62 13  6 45
  10  55 30 37 20  7  6 45 63 38 23 21 62 31 54  4 61 13 22 15 47 46 28 53 29
  11  39 14 21  4 54 53 29 47 22  7  5 46 15 38 55 45 28  6 62 31 30 12 37 13
  12  23 61  5 55 38 37 13 31  6 54 20 30 62 22 39 29 12 53 46 15 14 63 21 28
  13   7 45 20 39 22 21 28 15 53 38  4 14 46  6 23 13 63 37 30 62 61 47  5 12
  14  54 29  4 23  6  5 12 62 37 22 55 61 30 53  7 28 47 21 14 46 45 31 20 63
  15  38 13 55  7 53 20 63 46 21  6 39 45 14 37 54 12 31  5 61 30 29 15  4 47
  16  30  5 47 62 45 12 55 38 13 61 31 37  6 29 46  4 23 28 53 22 21  7 63 39

These represent Table 3-10 First Set of 24 key Bits in K(i), the Key used at Round( i) and Table 3-11 Second Set of 24 Key Bits in K(i), the Key Used at Round(i) found in Chapter 3. The Data Encryption standard the section Description of the Data Encryption Standard and subsection Generation of Key Vectors Used for Each Round of DES, of Cryptography A new Dimension in Computer Data Security subtitled A Guide for the Design and Implementation of Secure Systems, by Carl H. Meyer and Stephen M. Matyas published in 1982.

The tables demonstrate the Permuted Choice 2 selected C and D register contents given in input block indexes for the 16 rounds of DES.

The KS bits tell us which S Boxes each input block key bit is used on in each round.

Note that for input block bit 1 (the most significant bit of the first byte of key) is used as input to S Boxes 1 through 4 in 14 rounds.

Taking in to account e-suishi's comment the answer is achievable through research either reading or applied practice.  You could also note the process undertaken by the keytab program matches that described by fgrieu's comment.

In this case keytab generates the schedule key for each of the 16 rounds by providing an integer value representing the input block index instead of a 1 or 0 representing a binary value.

The idea comes from the original BSD libcrypt implementation of DES (des0.tar.gz, file crypt.c) which used integers to represent individual bits.

Doing algorithm-design or cryptanalysis can imply validating what you read.


Hybrid encryption with RSA and AES versus spliting into multiple RSA messages? I've done research about this subject, but I can't find the answer I'm looking for.
The problem is that the string I want to send doesn't fit into the RSA key that the client have, and during encryption getting ValueError: Plaintext is too long.
The proposed solution is to do hybrid encryption by generating a secret key, sending the secret key encrypted with the clients public key, and then send the rest of the data encrypted using AES and the secret key.
I understand the performance is much better in this manner, but for me this feels like opening an extra door to the data. Even though no one would ever find my service interesting enough to try to decrypt the RSA or AES data. But now I have to trust and support two(!) algorithms for the client applications.
Everyone only seems to be speaking good about the hybrid solution, and I understand that it would be the best solution for anything with a lot of traffic going on. Since it's probably about serving users as fast as possible and its not good to waste resources on encrypting/decrypting data.
But theoretically the data is open to two attacks, either by brute-forcing the RSA and get the secret key to decrypt the AES, or directly by brute-forcing the AES. But then again, using 2048-bit RSA and 256-bit AES wouldn't be possible to brute-force any of them any time soon.
So the 256-bit AES must be harder than the 2048-bit RSA, else the data is now less secure somehow, but since AES is 'thousands of times' faster than RSA this doesn't feels true.
Guessing a 32-byte AES password seems easier than guessing the much longer private key.
How secure are they (AES-256 vs RSA-2048) relatively to each other?

The idea I have is that I split my message into chunks, and encrypts each one of them using RSA, then concatenate them into one packet, and the client can then read each encrypted chunk and decrypt them and then concatenate them back to the original message.
Other than it's slower than a hybrid method, Is there anything wrong with this approach?
How much slower it would be to use RSA in this way relatively to AES? For a 512B string and a 2kB string? Or if the speed is constant, the answer expressed in MB/s

PS: Now you don't need to bother and fight about the protocol, which I happened to explain earlier. I just thought the background would help you to answer the question easier, but instead more comments and downvotes on the wrongs in the protocol than the real questions.

The question has several aspects:

it asked (initially) about any security issue in breaking a piece of data into separately RSA-encrypted chunks;
it asks what's the weak link in the security chain when doing hybrid encryption with a 256-bit AES key transfered enciphered using 2048-bit RSA;
it asks how much slower 2048-bit RSA would be for bulk encryption, compared to AES-256;
it (formerly) outlined a protocol where a public key is RSA-enciphered (causing the Plaintext is too long error); that protocol turned out to be unsafe not protect the confidentiality of data enciphered with that public key, basically because that public key was sent enciphered, rather than signed.

On the first aspect: if the goal of encryption is limited to protecting the confidentiality of some data (which is the only goal assigned to encryption in its modern definition), and RSA encryption is done properly (that is, with random padding), then there is no security issue, only performance and message size issues.

However the protocol formerly outlined used RSA encryption for other purposes than encryption. So maybe breaking the encrypted material into chunks worsens things; like, multiple cryptograms can be reordered by an adversary.

When doing hybrid encryption with 2048-bit RSA used to transfer a 256-bit AES key, the weak link is, from an academic point of view, the 2048-bit RSA key. According to the multiple sources considered by this well-respected website on key length, 2048-bit RSA is somwhat less secure than a block cipher with a 128-bit key, which itself is (theoretically) $2^{128}$ times less secure than a block cipher with a 256-bit key. Two levels of explanations to that:

Qualitative: in RSA, an adversary is given a lot of information about the key (the whole public modulus); whereas in AES, the key is assumed secret, being exposed to the adversary only through the complex layers of the cipher.
Quantitative: factoring $N$ is known to require less than $\exp\Big(\big(\sqrt[3]{\frac{64}{9}}+o(1)\big)\cdot(\ln N)^{\frac1 3}\cdot(\ln\ln N)^{\frac2 3}\Big)$ operations, and plugging $N\approx2^{2048}$ into that, ignoring the $o(1)$ term, gives less than $2^{117}$.

But reality is, the true weak link (beyond using a bad protocol) is the ability to keep undisclosed the secret material involved (e.g. the secret AES key and the private RSA key). Many things conspire to make this hard, both for RSA and AES, including implementation goofs, side channels, and NSA-planted backdoors.

How much slower RSA-2048 is compared to AES-256 depends on many things:

Is the cost of key generation to be considered? That is the case in the protocol formerly described, where a 2048-bit RSA key is generated for each user connection, and used only a few times per session, unquestionably making RSA key generation the performance bottleneck: generating an RSA key is much slower than using it, and can be like $2^{20\pm12}$ times more costly than AES-256 key generation or encryption (methods used for RSA key generation vary widely, and what we should include on the AES-256 side is unclear).
What is the hardware? If there is hardware for AES, but not for RSA, which is common on many modern CPUs, AES-256 encipher and decipher bulk data like $2^{20\pm 8}$ times faster than bulk RSA can. Even with hardware for RSA but not AES, like on this Smart Card with ARM Cortex M3 CPU, RSA is slower than AES is.
What is the software? Poorly written software can slow anything without limit. It is very common that two deployed implementations of a cryptographic algorithm differ in performance by a factor of $2^4$ on the same hardware.
Are we considering RSA encryption or decryption, and in the former case what's the public exponent? With $e=3$ and simple implementations, RSA-2048 decryption is $2^{10\pm1}$ times slower than encryption is; make that $2^{7\pm1}$ for $e=65537$.
The size of what's encrypted: AES's speed advantage is least when the data enciphered exactly fits the capacity of the RSA encryption scheme.

On the last aspect (now no longer part of the question):

Whatever exactly the protocol outlined was and aimed at, it was bound to be vulnerable to a Man-in-the-Middle attack during the "upload" of the "uniquely already known (user) public key"; a sure sign is that the client starts without any credential.
The protocol included an explicit step of encrypting something designated as "public key" (see end of step 4 in the protocol); this is a tale-tale sign of a design error.
Even if that "public key" was not made public, the confidentiality of commands normally sent enciphered by the user using that key (in step 5 of the protocol) was not ensured, for an adversary could inject another public key to be used instead.
In some most common uses of RSA for signature, an unknown public key is easy to infer from a few signatures;  keeping that public key confidential during its transfer does not prevent its later disclosure when and if it is used for signatures (as alluded in comments but not in the former description of the protocol).


Does re-transmission really reduce security? I am using AES with GCM and a colleague told me "Repeating a VCC with the same key and a different message reduces the security of the key." He did not have any additional detail to offer.

What he meant was since the encrypted VCC is in a fixed location in a packet, bad guys could intercept the messages and correlate the two messages, somehow making it easier to crack the message or key because the VCC was repeated. (I don't understand how bad guys would know if the VCC was repeated or not...)

My understanding is the VCC is there to prevent replay attacks, nothing more, nothing less. I understand they should not be repeated.

So my question is this: does repeating the VCC with a different message and the same key actually make it easier to crack the encryption key? If so, how?

Your colleague is wrong; assuming that the GCM nonces are generated correctly (that is, never repeats for the same key), there is no risk to GCM in repeating the VCC.

GCM has the property that, as long as you never repeat the nonce for the same key, GCM guarantees both the privacy and integrity of the encrypted plaintext (assuming that AES is a strong block cipher and that the AES key cannot be guessed).  This remains true even if you repeat the same region (such as the VCC) for multiple plaintexts.  Actually, the guarantee is even stronger; you could let the attacker choose the plaintexts for you to encrypt, and he still cannot learn either the AES key, or the plaintext for an encrypted message that he did not choose.


How to decide whether to use digital signature (RSA) or HMAC I found multiple posts regarding the differences between HMAC and RSA. Why should I prefer one or the other?

These are some examples:

HMAC SHA256 vs RSA SHA256 - which one to use

What are the different use cases between an HMAC and digital signature?

I am designing an SSO (single sign on) scheme to enable registration from one entity to a third party.

From my perspective HMAC should be used as we only want to check that the first entity is a known one. Furthermore HMAC can be faster than RSA (openssl speed hmac rsa gives 1 magnitude difference).

On the other hand, would it be better to use digital signatures to avoid risk case either of the two sides of the system is breached?

I have tried to look on many other schemes for similar use cases and it seems like almost everyone uses HMAC-SHA256. I am not sure if this risk is something should be considered as I couldn't find any crypto notes regarding this matter.

HMAC (and any other MAC) are totally different from Digital Signatures (RSA, DSA, ECDSA, EdDSA).

MACs require a shared secret key that both the communicating parties have. The same secret is used to create the MAC as is used to verify it. Anyone with the shared secret key can create a MAC, and anyone with the shared secret key can verify a MAC.

Digital Signatures don't use a shared secret: Each entity has two keys, one public and one private. Only they can sign messages (only they have the private key) but anyone can verify those signatures. There's no need to exchange a shared secret.

MACs are generally much faster than Signatures.

That said, the fact that you are asking this question indicates that you have some fundamental learning to do before even starting to design an SSO mechanism. Have you considered using OAuth? There are many libraries for various languages that support it, it's secure, and it avoids many of the hidden pitfalls you won't have thought of.


How much data does a session/data key typically encrypt? I believe the masker key, $MK$, of a block cipher might be used for several years and is used only to encrypt $\textit{key encrypting keys}$, which in turn are used only to encrypt $\textit{data keys}$. These data keys are the ones actually used in cryptographic computations and are often also called $\textit{session keys}$. They have short lifetimes and may be used only for a single session. My questions are:

What is a 'single session'?
How much data might the same session key be used for (max or min?)
How long would a session key be used for?

I know answers to these questions depend on many things, such what is being encrypted, how long must it remain secure, etc. but just some ideas or real-world examples would be helful.

The most common encryption protocol is probably TLS, as used in HTTPS. AES (with a 128-bit block size) is probably the most common encryption algorithm. Therefore the maximum amount of data that can be sent safely is $2^{128/2}=2^{64} blocks = 256EiB$.

Typical sessions end when the user closes the web page, and so send significantly less data. Even binge-watching an entire season of a TV show on a streaming site will only use a few GiB for a session.

Of course some users rarely close their browser tabs, but the most common PC OS is Windows which updates requiring a reboot at least once a month. Thus the longest duration of a session is likely to be around a month.

This answer has ignored session resumption, because it isn't that widely used. Even where it is used most protocols (including TLS) provide a way to re-negotiate keys.

TLS 1.2 recommends that sessions last no longer than 24 hours (section F.1.4).


Breaking a small-scale Example Diffie-Hellman? I started to read about Diffie-Hellman exchange and I encountered a problem which I don't know how to solve.

Given $g=3$, $p=131$, $g^x\bmod p=112$, $g^y\bmod p=74$, compute $g^{xy}\bmod p$

$113$
$110$
$112$
$111$

How could I compute $g^{xy} \bmod p$? Or at least verify which one is correct.
Any idea?

Actually, given $p,g,g^x\bmod p,g^y\bmod p$ deciding whether a given number is actually $g^{xy}\bmod p$ is also known as the Decisional Diffie-Hellman Problem (DDH), which sits at the basis of the (formal) security for the ElGamal cryptosystem and is assumed to be hard for properly chosen values of $p,g$ and $x,y$ in general.

For your particular scenario the best solution is to "just" solve the discrete logarithm problem, ie computing $x$ or $y$ and then computing $g^{xy}\bmod p$ to see which number falls out (113).


Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use? A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using just a single core-month". They credit a 2012 paper by Antoine Joux: Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite field for paving the way they explore. In 2013 Joux published A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, and very recently announced he "is able to compute discrete logarithms in $GF(2^{6168})=GF({(2^{257})}^{24})$ using less than 550 CPU.hours". It seems the field (pun intended) of DLP in $GF(2^n)$ is in ebullition.

Current French official recommendations (section 2.2.1.3), updated June 2012, do distance themselves from schemes based on the DLP in $GF(2^n)$, but only mildly. If such scheme is used, the requirement is that $n\ge 2048$ bits up to year 2030, and $n\ge 3072$ bit afterwards, with subgroups of order a multiple of a prime of at least 200 bits. It is recommended to prefer a scheme not based on the DLP in $GF(2^n)$, and if one is used, that the order of the subgroup is prime.

How do the progress reported in the above papers translate into actual breaks for schemes proposed for cryptographic use, based on arithmetic in $GF(2^n)$, and conforming to the quoted recommendations? What are such schemes?

Note: related to this old question; and even closer to this recent one, except that I am not only interested in pairing-based schemes, but also more mundane things like a DSA analog over $GF(2^{4099})$, if there can be such a thing.

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor.

Not all binary fields are affected equally, however. Both Göloğlu et al and Joux's approaches descend from the medium-prime function field sieve, and require the field $\mathbb{F}_{2^N}$ to be representable as (among others):

$\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k' \cdot d_1}$, $d_1, k'$ constant  (Göloğlu et al);
$\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k'} - 1$, $k'$ constant  (Göloğlu et al);
$\mathbb{F}_{q^{2n}}$, where $q = 2^{l}$ and $n \le q + \delta,\, \delta \ll q$ (Joux).

When the exponent of the binary field is smooth, we get many choices to try and represent the field in the forms above. Example: $1778 = 7 \cdot (2 \cdot 127)$; $6120 = 24 \cdot (2^{24/3} - 1)$; $6168 = 257\cdot (2\cdot 12)$; etc. When the exponent is prime, however, we have no such luck.

Instead, as Joux suggested, one may embed the target field within a larger field that does: $\mathbb{F}_{q^{2N}}$, where $q = 2^{\lceil \log_2 N \rceil}$. While this solution may be asymptotically satisfactory, the blow up in size increases the bitlength where Joux's algorithm is faster than the regular function field sieve. It is currently unknown what this size may be, but it is likely that is is higher than current common key sizes (1024-4096 bits).

As for actual uses of binary fields, I do not know of any real-world usage of schemes based on the DLP over binary fields (beyond pairings). We have long been avoiding composite degree binary fields for elliptic curves due to their increased susceptibility to index-calculus; it seems that finite fields are now forced to do the same.


Why is Paillier Cryptosystem called probabilistic? The definition of Paillier Cryptosystem says that it is a probabilistic asymmetric key algorithm for public key cryptography. Can some body explain why it is called "probabilistic"?

As user curious said in a other answer probabilistic means that the encryption of the same plaintext under the same key gives as output a different ciphertext.

This is a more general property and it is known as a basic security property: it is usually refered to as semantically secure or indistinguishability (roughly: an attacker cannot guess which one of two plaintext he provided has been encrypted). It was firstly defined and introduced by Goldwasser and Micali in their seminal paper "Probabilistic Encryption" on 1984. This property is usually achieved introducing a random token into the encryption algorithm.
A very simple way to transform any deterministic encryption algorithm into a probabilistic one is to pad the plaintext with a random string before to encrypt it and do unpad it after the decryption. Under symmetric encryption it can be easily achieved using a random IV (or counter) for a secure block operation mode (as CBC or CTR).

More precisely about Pallier cryptoscheme, the encryption algorithm uses a random $r$ element per encryption.

Encryption

Let $m$ be a message to be encrypted where $m\in \mathbb Z_{n}$;
Select random $r$ where $r\in \mathbb Z^{*}_{n}$;
Compute ciphertext as: $c=g^m \cdot r^n \bmod n^2 $.


Standard serialization format for libsodium-based messages Does anyone know of a standardized serialization format which can be (or already is) widely used for encrypted messages? For a variety of reasons (mostly complexity, age and poor support across a lot of languages) we don't want to use OpenPGP for this case.

The use case is fairly simple, we want to create "stateless" (from the server's perspective) authorization token across a wide variety of our web-based applications, without having to implement an OAUTH-handshake as users transition from application to application. The applications are written in a variety of languages, some .NET, some Java, some Node.js, and Python.

It seems a reasonable, modern solution to this problem is to use libsodium's crypto_secretbox_easy to authenticate a user and then encrypt a message of the form:

{identity: 'someuser@example.com', expires: '2015-02-27T09:45:35.886Z'}

...and send it to the client for cookie storage. Assuming secure configuration of keys in all the various applications, we could use the libsodium variants for each platform to authenticate a user based on this encrypted and authenticated token.

The problem, of course, is how to format the message? I need to transmit the nonce as well, but that isn't part of the output of crypto_secretbox_easy, and nothing I've found during research seems to indicate there is a standard serialized message format for use with libsodium. Lots of people are rolling their own.

So, is it safe to use a general cross-platform message serialization library such as MessagePack to transmit a message of the form:

{nonce_value: 0x44ec53c1235daa22d3e0322931ce2d2c47ece2a5ae46a00e,
secretbox_message: 0xa3ce9f0edb35a058eaf90d87f871ecdf6fb7f88ec547f377fdb27780716e1904ab8663dbce724d1bfcc7ee1f40108400}

I know enough about crypto to know "there be dragons" when inventing your own protocols, and assembling crypto primitives naively has repeatedly shown to be disaster. So if there is a standardized and secure way of doing this sort of encrypted and authenticated messaging (other than OpenPGP) I would of course like to use that. If there isn't a modern standard for this task, I ask:

do you think my proposed construction is secure?
are there any reasons that general structured serialization libraries are unsuitable for use in cryptographic protocols? Looking at various PGP, TLS, and PKCS specifications, it seems this wheel gets re-invented quite a lot, and I don't quite understand why.

Any serialization library that can efficiently encode binary data can be used, and MessagePack is an excellent choice for this purpose.


Is it possible to mathematically extract an AES key from black-box encrypt/decrypt hardware? I presented our mathematician with an idea:

  If you have a black box that encrypts or decrypts AES with the same 128 bit key (you don't have any direct access to the key), and you control the input and the direction (enc/dec) and can see the output,
  can you mathematically derive the key? How many tests will you have to run to be able to derive the key?

He said he remembers there was a paper that said it will take only $2^{16}$ tries to derive the key. Does this paper exist? Dan anybody point me in the right direction?

What you describe is Chosen-Plaintext Attack (CPA) and AES and secure block ciphers are designed to be secure against this.

Having $2^{16}$ chosen-plaintext under one key doesn't help you to extract the AES key. You have to go to the full-brute force to find the key.

Since you have one target, you cannot get help from attacking many keys simultaneously. In some cases, the black box may reside in many days in front of you, thus, during those days, you will get many target keys.

For $t$ targets, the expected cost breaking one of the $t$ keys is $2^{128}/t$ and that will be far below $2^{128}$. If you have a billion target (~$2^{30}$) the cost will be ~$2^{98}$ to find one of the target keys.


Is Dropbox's hashing method cryptographically secure? Dropbox uses CRC32 and md5 to create a checksum of each 4 mb "block" as part of the their compression/file system.

I suspect that Dropbox uses an additional cryptographic hash to check if there's a collision, but let's assume that doesn't happen.

Is using CRC32 and md5 in combination cryptographically secure?

Disclaimer: I have no first-hand knowledge of what hash (or MAC, or whatever method) DropBox uses for de-duplication; about if it is enough to know that (and its key, for a MAC) in order to download something from DropBox; and I see slightly diverging opinions about these points.
If we consider the problem of finding a collision, the 160-bit hash defined by
$$H(M)=\text{CRC32}(M)||\text{MD5}(M)$$
is NOT cryptographically secure, for it is only marginally stronger than $\text{MD5}$ is.
$\text{MD5}$ no longer provides a good protection against collisions: with this Fast Collision Attack on $\text{MD5}$ we can find a collision (for messages at least 128 byte) with cost about $2^{18}$ compression functions (finding collisions for $\text{CRC32}$ is totally trivial). Finding a collision for $H$ is harder than for $\text{MD5}$, but by a dumb method (finding $\text{MD5}$ collisions until one is also a collision for $\text{CRC32}$) only like $2^{32}$ times harder, and $2^{50}$ compression functions is non-trivial but feasible. Update: And as pointed by poncho we can (for messages at least 4 kiB) make that only like $32$ times harder, or about $2^{23}$ compression functions, which is nothing. As the saying attributed to the NSA goes, attacks only get better, they never get worse.

If we consider the problem of finding a second-preimage, $\text{MD5}$ remains impractical to attack as far a we know, and $H$ is at least as strong as $\text{MD5}$ is.
If we consider the problem of finding a first-preimage, $H$ can't be more than $2^{32}$ times easier to attack than $\text{MD5}$ is, likely that can only be approached for short messages where brute-force is the best attack, and for long messages likely this is (at least) about as hard as for $\text{MD5}$, which remains impractical to attack as far a we know.


Where can I begin to study the math behind modern cryptography? Why do I start the word buffers in MD5 with those values specifically? What in the world motivated the decision to use the numbers 1, 1, 2, 3 for the mix columns stagein AES? And what kind of witchcraft is going on in SHA when I call the sigma_x functions?

What kind of math should I be starting with, assuming I only know how to add, subtract, multiply, divide, and mod?

One of the best avenues for study is to practice breaking existing cyphers.  Start small, with classic cyphers such as monoalphabetic substitution, polyalphabetic cyphers, transpositions, etc.  Do the daily Cryptoquip in the newspaper!  Learn what makes them weak, what makes them exploitable, and what makes them strong.  Then move on to stream cyphers, to mechanized cyphers like the Hebern and Enigma machines, and then to modern electronic block cyphers.

With each cypher you attack, you first learn how to attack a simplified or reduced round variant, then apply it to the more complex and complete implementations.  Along the way, learn how some of the various protocols and implementations have made cyphers weak, or provided defenses against certain forms of attack.  Finally, study some of the advanced attacks, and replicate their results.

To implement these attacks, you'll discover new topics you need to understand in order to pull them off:  statistics, modulo arithmetic, algebra, recursion, protocols, zero knowledge proofs, bignum math, game theory, Feistel networks, whatever.  These are the same tools you will later use to understand and construct cyphers and protocols of your own.

Once you study attacks on cyphers, protocols, and implementations, you'll better understand why some of the more esoteric design decisions were made, or why certain mechanisms were added.  A fascinating case study for the value of this approach can be a found by reading the history of the Lucifer cypher.

Good luck!


Geometric Cryptography and Zero-Knowledge Proofs Trying to understand zero-knowledge proofs, I came across this page, which provides an excellent example of a simple cryptographic protocol. I will reproduce the protocol here for the sake of completion.

Assumptions: Let us assume that only (classical Greek) geometric construction is allowed. So we can only use a compass and a straight-edge and we can only perform those operations which can be geometrically constructed. Specifically, an arbitrary (given) angle cannot be trisected but any arbitrary angle can be tripled easily.

Initialization: Alice has a secret, an angle $X_A$. Maybe she wants to sell it or use it to prove her identity later. Alice constructs $Y_A=3*X_A$ and publishes it. Because trisecting an angle is impossible, Alice is confident that she is the only one who knows $X_A$.

Identification Protocol: Bob comes along and wants to buy $X_A$ or verify Alice's identity.

Bob initiates a check.
Alice selects an angle $K$ at random. Alice constructs $R = 3*K$ and gives $R$ to Bob.
Bob flips a coin and tells Alice the result.
If Bob says "heads", Alice gives Bob a copy of the angle $K$ and Bob checks that $3*K = R$.
If Bob says "tails", Alice gives Bob a copy of the angle $L = K + X_A$ and Bob checks that $3*L = R + Y_A$.
Bob can rinse and repeat as many times as he wants.

Question: Why are steps three and four a part of the protocol? Specifically, why is step four even necessary? What is wrong with

Bob initiates a check.
Alice come up with a new random $K$ and gives $R=3*K$ to Bob.
Then Alice gives $K+X_A$ to Bob and Bob checks it.
Bob initiates as many checks as he wants and stops when he is satisfied.

Why isn't this enough?

Suppose that the second approach is used, this would allow an attacker to impose Alice. The intuition is that, as long as an attacker knows what is Bob going to ask him, he will be able to make things as he wishes in order for verification to pass.

Basically, the attacker wants to give Bob a (chosen) value of $R$ such that when he gives $L'$ to Bob verification holds ($L'$ would be $L = K + X_A$ in the case of Alice). This means that $3\ast L'$ should be equal to $R + Y_A$. This is easy since he can choose at first a random value for $L'$ and then set $R$ to be $3\ast L' - Y_A$ (recall that $Y_A$ is public!), you can check that verification will pass.

Notice that this works since the attacker sends $L'$ and $R$ simultaneously. This fails in the former protocol since Alice is asked to commit to $R$ at the beginning and then compute $L$ from there depending on Bob's choice.


Does the size of the cryptogram affect the possibility of breaking it? Does the size of the cryptogram affect the possibility of breaking it?
In the context of symmetric and block algorithms.
Does the format and earlier processing of the document (compression, changing the document format) affect the possibility of its cryptanalysis?

Maybe you can share some more information about what the attack model is?
For all practical purposes it does not matter how much data an adversary obtains - a secure cryptosystem (when used correctly) guarantees the secrecy of the data it encrypts.


Zero-knowledge authentication to commercial VPN For VPNs which only connect to the greater internet (as opposed to a VPN for accessing a private network), it is only necessary for the server to know that the client is a paying customer. It doesn't need to know which customer.

How could such a system be made? One method is to use Chaum's digital cash method, but have the "cash" instead be a claim ticket for data transfer.

However, if you know of any other methods, please post them.

A modern approach might be to use blinded tokens like PrivacyPass based on a VOPRF.  There are two parts to the protocol: an OPRF to negotiate blinded tokens with a payment that can later be redeemed for service, and DLEQ proof to verify that the tokens are unlinkable.

VOPRF, verifiable oblivious pseudorandom function family.  This is a combination of a series of related concepts:

A PRF or pseudorandom function family is a family of functions $F_k$ that is hard to distinguish, if $k$ is chosen uniformly at random, from a uniform random function.  In other words, for distinct $x$, $F_k(x)$ appears to be independent uniform random to anyone who doesn't know $k$.

(PRFs are ubiquitous in cryptography.  Typical examples: ChaCha, AES, HMAC-SHA256.)
An OPRF or oblivious PRF is a protocol by which a client and a server jointly compute a PRF using a key known only to the server and an input known only to the client, so that the client learns $F_k(x)$ but not $k$, and the server learns nothing.

(OPRFs are used in protocols like the password-authenticated key agreement OPAQUE (paywall-free preprint).)
A VRF or verifiable PRF is a public-key cryptosystem for computing a PRF $F_k(x)$ giving a value $v$ together with a proof $\pi$ so that (a) without knowledge of the public key, $v$ is indistinguishable from uniform random (i.e., $F_k$ is a PRF to anyone who doesn't have the public key and $\pi$), but (b) with knowledge of the public key, a verifier can use $\pi$ to confirm that $v$ is the unique output of $F_k$ on $x$.

(More on VRFs, and an application in DNSSEC.)
Finally, a VOPRF or verifiable OPRF is a protocol by which a client and a server jointly compute $v = F_k(x)$ and give the client a proof $\pi$.  Then even the server—with knowledge of the public key, $k$, and $\pi$, but not $x$—can't distinguish $v$ from a uniform random string, but the client can verify with $\pi$ and the server's public key that $v$ is in fact the unique value of $F_k$ at $x$.

How does it work?  Here's the OPRF used by PrivacyPass—ignoring the ‘verifiable’ part for the first approximation.  Fix a group $G$ of prime order (written additively) with standard base point $X$, and fix hash functions $H_1\colon \{0,1\}^* \to G$ and $H_2\colon G \to \{0,1\}^n$.  A public key is a group element $Y \in G$ and a private key is the secret scalar $k$ such that $Y = [k]X$.  The PRF is $$t \mapsto H_2(t, [k]H_1(t)).$$  The client and server jointly compute it as follows:

  PrivacyPass OPRF.

  Client picks a secret bit string $t$.
  Client picks a secret blinding scalar $r$ uniformly at random, and sends $P := [r]H_1(t)$ to the server (along with, say, a payment for purchase).
  Server, given $P$, sends $Q := [k]P$ back to the client.
  Client, given $Q$, reverses the blinding scalar $r$ to compute the group element $$[r^{-1}]Q = [r^{-1} k]P = [r^{-1} k r]H_1(t) = [k]H_1(t).$$
  Client finally computes the bit string $z := H_2(t, [r^{-1}]Q) = H_2(t, [k]H_1(t))$.

(The client could alternatively do additive blinding: send $P := H_1(t) + [r]X$ to the server, and use $z := H_2(t, Q - [r]Y)$, like OPAQUE does.  The two provide essentially equivalent security.  Multiplicative blinding requires computing scalar inverses, which may be a little expensive.  Additive blinding requires, well, computing addition, so it can't be used with, e.g., $x$-restricted scalar multiplication only like X25519—although X25519 can't be used directly anyway because it's not a prime-order group, and we'll want addition later on for the DLEQ proof of anonymity.)

How do we use an OPRF in a purchase and redemption protocol?

  Purchase.  The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$.  The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

  Redemption.  The user then redeems a token $(t, z)$ to authenticate a request for service $m$ by sending $(t, \operatorname{MAC}_z(m))$ as an authenticator for $m$.  The server recomputes $z = H_2(t, [k]H_1(t))$ using the private key $k$ to verify the authenticator, and keeps a database of spent tokens $t$ to prevent replays; the server can also periodically—say, weekly, or monthly—rotate the public key so that the spent token database doesn't accumulate indefinitely.  If the token is unspent and the authenticator matches, the server provides the service.

This protocol guarantees that the client is unable to forge tokens, no matter how many tokens they've already acquired from the server, and guarantees—if the server follows the protocol and uses a single key for every client—that the tokens submitted by each client are indistinguishable from one another to the server.

But wait!  How do we know that the server doesn't use a different key for every client, enabling the server to track clients from purchase to redemption?  We need a way for the server to prove to the client that the tokens are made with the same private key $k$ each time.  This is where the verifiable part of the VOPRF comes in, using a zero-knowledge proof of discrete log equality.

DLEQ proof, a receipt for a non-interactive zero-knowledge proof of discrete log equality.  A DLEQ proof is a proof that two group elements $Y, Q \in G$ have the same discrete log with respect to two bases $X, P \in G$: $\log_X Y = \log_P Q$.  In other words, that $Y = [k]X$ and $Q = [k]P$ for the same $k$.

We start with an interactive zero-knowledge proof by a $\Sigma$-protocol due to Chaum and Pedersen between a prover and a verifier who share $(X, Y, P, Q)$ a priori:

  Chaum–Pedersen interactive zero-knowledge proof of discrete log equality.

  Prover picks a uniform random per-session secret $u$, and commits to it by announcing $A := [u]X$ and $B := [u]P$.
  Verifier picks a uniform random scalar $c$ to challenge the prover.
  Prover answers the challenge by returning $s := (u - c k) \bmod \ell$, where $\ell$ is the order of the group $G$.

  Verifier accepts if $A \stackrel?= [s]X + [c]Y$ and $B \stackrel?= [s]P + [c]Q$.

Using a hash function $H_3$, with the Fiat–Shamir heuristic we can turn this into a non-interactive zero-knowledge proof system that gives a verifiable receipt, much like the Schnorr signature scheme is derived from the Schnorr identification protocol:

  Chaum–Pedersen non-interactive zero-knowledge proof of discrete log equality.

  Prover picks a uniform random $u$ and computes $A := [u]X$ and $B := [u]P$.
  Prover computes challenge $c := H_3(X, Y, P, Q, A, B).$
  Prover computes $s := (u - c k) \bmod \ell$ and returns $(c, s)$ as receipt.

  Verifier accepts if $c \stackrel?= H_3(X, Y, P, Q, A', B')$ where $A' := [s]X + [c]Y$ and $B' := [s]P + [c]Q)$.

We can even efficiently extend a short receipt $(c, s)$ to work on a batch of discrete log pairs $\{(P_i, Q_i)\}_i$ by hashing $(X, Y, \{(P_i, Q_i)\}_i)$ into a sequence of challenges $\{c_i\}_i$, deriving $P' := \sum_i [c_i]P_i$ and $Q' := \sum_i [c_i]Q_i$, and then doing the one-point DLEQ proof on $(X, Y, P', Q')$.

Batch DLEQ proofs are important if you want to allow a single payment to purchase many unlinkable instances of service at once—like exchanging one robot overlord training session for the high privilege of just reading the fucking newspaper without having to do another robot overlord training session for every newspaper you want to read, as is the dominant application of PrivacyPass with the global active adversary Cloudflare: to reduce $n$ captchas down to one captcha.

Armed with a DLEQ proof technique by which to turn an OPRF into a VOPRF, the server can now commit to a public key $Y$ relative to the standard base point $X$ in some very public verifiable space (e.g., a well-known URL like https://www.example.com/tokenkey that the user fetches through Tor), and prove to the user that the tokens are unlinkable with a minor variant of the purchase protocol:

  Purchase with proof of anonymity.  The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$, together with a DLEQ proof that $\log_X Y = \log_P = Q$.  The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

  Before redeeming the token, the user verifies the DLEQ proof; if it fails, the user tells all their friends that the server is a lying sack of gastrointestinal distress and loudly demands to speak to the manager of the cryptocurrency scam by which they bought their tokens.

By the way, you could also just use Tor.


Dan Boneh's explanation of why Davies-Meyer requires the final step of XOR with the previous Hash This is from this video
https://www.coursera.org/learn/crypto/lecture/XZt5V/constructing-compression-functions
At 2:44, Dan Boneh explains why the XOR is required.
This is his explanation
m - message to be hashed
H - output of previous hash (chaining input)
h - hash function
E - Encryption function
D - Decryption function
h(H, m) = E(m, H)
(instead of h(H, m) = E(m, H) XOR H )
You can choose a random H, m & m' & construct a
H' = D(m', E(m, H))
which will give you a collision for m & m'
He says that the Decryption will cancel out the Encryption which will result in the collision.

Can someone explain how?
Why is he allowed to choose H'? Shouldn't you be allowed only to choose m' for an attack? Why do you get to choose H' also?

IMP: I have read other explanations for why the XOR is needed & I am convinced also.
However, here I am trying to understand Dan Boneh's explanation.

Dan Boneh's explanation is about finding a collision for the compression function $h$ defined by $h:\ (H,m)\mapsto h(H,m)\underset{\text{def}}=E(m,H)$ where $E$ is a block cipher with first parameter as key. Notice that the input of function $h$ is neither $H$ nor $m$; it's the pair $(H,m)$, or equivalently the bitstring $H\mathbin\|m$.
Finding a collision for $h$ is finding two distinct inputs to the function $h$ such that the output is the same. That is finding an $(H,m)$ and a different $(H',m')$ such that $h(H,m)=h(H',m')$.
The method Dan Boneh uses is to choose arbitrarily $H$, $m$, and $m'\ne m$; then compute $H'=D(m',E(m,H))$, where $D$ us the decryption function for the block cipher $E$. We'll use that $D$ is such that $\forall k,\ \forall c$, $E(k,D(k,c))=c$. This can be readily proven from the more usual $\forall k,\ \forall p$, $D(k,E(k,p))=p$.
From $H'=D(m',E(m,H))$, it follows $E(m',H')=E(m',D(m',E(m,H)))$. And then applying the above property of $D$ with $k=m'$ and $c=E(m,H)$, it comes $E(m',H')=E(m,H)$. And since we have chosen $m'\ne m$, it holds $(m',H')\ne(m,H)$. Dan Boneh's method thus always exhibits a collision for $h$.
Dan Boneh is allowed to chose $H'$ because he aims at exhibiting a collision for $h$. He would not be allowed that if he was trying to exhibit a collision for the different functions $h_H:\ m\mapsto h_H(m)\underset{\text{def}}=E(m,H)$, where $H$ is a fixed parameter rather than part of the input. Neither would he for a collision of a hash function built per the Merkle-Damgård construction using $h$ as the compression function.


Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem? As in the title, given $g$, $g^{ab}$ are big elements in a prime group $Z_p$ and $b$ in prime group $Z_r$ ($p > r$, $g$ is one generator of $Z_p$). $a$ is unknown and also in $Z_r$, is finding $g^a$ a hard problem?

update $a$, $b$ and $ab$ are group elements of $Z_r$..

Not at all. It's very trivial:
$$(g^{ab})^{b^{-1}}=g^a$$


NTRU Backdoor and NewHope TLS Protocol The pre-print, Unstructured Inversions of NewHope was posted yesterday and uses a backdoor method against NTRU to claim that Grover's algorithm and an inversion oracle could be applied to NewHope.

My question is whether the backdoor from the Unstructured Inversions article could actually be used against NTRU?  I'm not interested about the impact it may or may not have against NewHope, just forms of NTRU.

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010.
The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated.
For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$.
In particular, the cited paper suggested that one can use Grover to accelerate the search for $f$.
This is a known issue to the community for a while.
The NewHope paper [2] addresses this by having $a$ to be an output of a hash function at the run time of the client.
So under reasonable assumptions, no one is able to manipulate the public matrix $a$.
Will this affect NTRU? The answer is NO, if NTRU is used correctly.
NTRU uses structured public key $a$ to enable efficient computation. Hence it has a trapdoor by design.
So if NTRU is used in a Diffie-Hellman type key exchange, where $a$ is generated by a (trusted) third party,
then yes it may be vulnerable to this threat.
However, the correct use of NTRU, in a key exchange protocol, is to instantiate it via a
key encapsulation mechanism (KEM), such as [3] [4].
In those cases, the client generates the public key (as the public parameter $a$ in R-LWE based schemes).
And only the client knows the trapdoor.
In this case the attacker need to run the Grover's algorithm to find the trapdoor.
This is as hard as using Grover's algorithm to break NTRU.
The parameter sets proposed in [5] ensures that this attack is impossible.

Thank you for your response. Are you referring to the hybrid attack from [5] in the context of the parameters from section 8 in [5]?

Yes.

I also see that you do specifically address concerns related to f(1)≠0mod2 Thank you, again.

It is not just the $f(1) \neq 0 mod 2" part. In [5] the algorithm is a CCA-2 secure encryption algorithm, which rules out the inversion oracle [6] required by the "Unstructured Inversion" paper.

It also looks like the Unstructured Inversion pre-print is focused more on the approximate x-coordinates rather than modifying the public matrix a.

The "Unstructured Inversion" paper is not in enough details, so the following are my guesses, and may be incorrect. Overall, imho the  paper relies on several very strong assumptions.

there exist a trapdoor in (R-)LWE public key $a$, which is not known by the attacker.
This is a rare situation, as either the attacker inserted the trapdoor (as in attacks against [1]), in which case he already know the trapdoor and hence do not need to perform this attack;
or $a$ is generated truthfully by the client (as in the solution in [2]), thus there does not exist a trapdoor. It is a strange case where someone (but not the attacker) generates $a$ with trapdoor but the attacker does not know it. If the client follows the protocol correctly this shall never happen.

the existence of an inversion oracle.
The inversion oracle is a stronger oracle than a decryption oracle used in CCA definitions. In addition, in both newhope style and NTRU-KEM style key exchange, the public parameter/key is used only once. It is very unlikely such oracle exists for ephemeral keys. In other words, if there exist such an
oracle that works on ephemeral keys, there may be much stronger attacks than the one described in the paper.

[1] https://eprint.iacr.org/2014/599
[2] https://eprint.iacr.org/2015/1092
[3] https://eprint.iacr.org/2015/287
[4] https://tools.ietf.org/html/draft-whyte-qsh-tls12-02
[5] https://eprint.iacr.org/2015/708
[6] http://cseweb.ucsd.edu/~pmol/Publications/Recovering%20NTRU%20Secret%20Key%20From%20Inversion%20Oracles.pdf


Factorization of RSA modulus using a qubic residue Suppose that someone uses RSA with $n = pq$, exponent $3$, also $3$ divides $\varphi(n) = (p-1)(q-1)$ and $2$ different roots $y$ and $z$ of the equation:

$$x \equiv c \ (mod \ n)$$

are known (for some qubic residue $c$).

Then can $p$ and $q$ be effectively calculated using $y$ and $z$ and how ? Thanks in advance !

Let $n = pq$.  By assumption, $3$ divides $\varphi(n) = (p-1)(q-1)$.  Without loss of generality, I assume that $3$ divides $(p-1)$ or, equivalently, that $p \equiv 1 \pmod {3}$.

Fact Let $p$ be a prime such that $p \equiv 1 \pmod 3$.  Let also $c$ be a cubic residue modulo $p$. If $y$ is a cubic root of $c$ then so are $y\cdot \omega \pmod p$ and $y \cdot \omega^2 \pmod p$, where $\omega$ is a non-trivial root of unity modulo $p$ (i.e., $\omega$ satisfies the equation $\omega^2 + \omega + 1 = 0 \pmod {p}$).

In your case, given $c \in \mathbb{Z}_n^*$, you know that $y$ and $z$ are two (distinct) cubic roots of $c$ modulo $n$.  Namely, $y^3 \equiv z^3 \equiv c \pmod n$.  In turn, this implies $y^3 - z^3 \equiv 0 \pmod n$ and thus $(y-z)(y^2+yz+z^2) \equiv 0 \pmod n$.  Since $n = pq$, it follows that

$(y-z)(y^2+yz+z^2) \equiv 0 \pmod p$, and
$(y-z)(y^2+yz+z^2) \equiv 0 \pmod q$.

Subcase 1 Assume $q \equiv 2 \pmod 3$ —in this case, cubic roots modulo $q$ are unique.  This implies that $y \equiv z \pmod q$.  But you cannot have then $y \equiv z \pmod p$ because otherwise you would have $y = z \pmod {n}$ (and $y$ and $z$ are supposed to be distinct).  Therefore, since $y \equiv z \pmod q$ yields $(y-z) \equiv 0 \pmod q$ and $y \not\equiv z \pmod p$ yields $(y-z) \not\equiv 0 \pmod p$, you get $\gcd(y-z,n) = q$.

Subcase 2 Assume now $q \equiv 1 \pmod 3$.  In this case, there is no guarantee that $\gcd(y-z, n)$ will reveal a factor of $n$.  Indeed, it may be the case that, even if $y \neq z \pmod n$, $y^2 + yz + z^2 \equiv 0 \pmod p$ and $y^2 + yz + z^2 \equiv 0 \pmod q$.  But you can always give it a try...


RSA certificate needed in CVC format I had a client requirement asking me to provide an existing base64 encoded certificate in a CVC  format. Could someone point me in the right direction here to understand what this format is? How can I convert an x509 certificate to CVC format and the tools to achieve this, please? thanks.

A Card Verifiable Certificate (CVC) is a certificate that has been created with validation and verification on smart cards in mind. These cards are extremely small System on Chips, with RAM, persistent memory (flash or EEPROM) and ROM.

So basically it's the same as a normal certificate, but it doesn't contain as many bells and whistles, as the bells and whistles it does have are generally minimized as well.

There are some standards for CVC's but generally they are not complied to so you will have to look up the specific protocol to know how the certificate is encoded.

Things you should expect:

a non-standard certificate format
a flattened DER encoded structure (sometimes just a single sequence with child elements)
specialized DER tags
the use of octet strings over integers or bit strings (smaller encoding)
short date formats for the date of issuance and date of expiry
few if any personal details
a simplified / shorter scheme for subject / issuer identification
for ECDSA: flattened signature format (i.e. statically sized R & S)
for RSA: signatures with message recovery (ISO / IEC 9796)
signatures over all of the other elements (so the signature can be updated / verified in a single operation)
simplified encoding of the public key (e.g. without algorithm specification)

Sometimes the certificate contains an OID that specifies the specific scheme and versioning information. In that case you could try and find the protocol required.

As for your question:

Base 64 is not a certificate format, it's an encoding format.
You cannot just convert an existing X.509 certificate to CVC because the signature would not be valid - even if you knew which ASN.1 elements to copy / convert.
There is no generic standard that is commonly used, so there are no generic tools - you'd need specialized tools and - of course - the private key of the issuer.


How to encrypt data with the Threefish cipher I want to know how the Threefish cipher can be used to encrypt and decrypt. I tried to find out by searching the Internet but can't find a concrete answer. The only answers are theoretical in nature which is not usable to me.

As far as I know there isn't any Threefish-specific encryption standard specified. I actually asked Bruce Schneier back in the day (when I created my "SkeinFromSpec" implementation). Threefish is a tweakable block cipher with a large block size. I asked for instance if you should keep to the high amount of rounds (80 for Skein) and what mode I should use, but I never got a concrete answer. At that time the Skein team was of course mainly busy with the SHA-3 contest.

In principle you could use any mode of operation that is also available for normal block ciphers, as long as it allows for the larger block size. You are of course better off using an (authenticated) mode of operation for tweakable block ciphers. There are a few papers on that, but as you've indicated, they are usually theoretical in nature.

Things may have been different if Skein was the winner of the SHA-3 contest. There are a few proposed modes that use the Keccak sponge - the winner of the SHA-3 contest - which you could use, Keyak for instance.


ISO 9564-1 format 4: do I need an IV? ISO 9564-1 format 4 describes an extended PIN block format. Simply said, this standard can be used to encrypt 4-digit PIN codes in a secure way.

The standard mentions (simplified) to add random values to the PIN, before encrypting it with a cipher that can be chosen by the implementer (we will go for AES-CTR).

I wonder now, if we follow this standard, and append a cryptographically random value to the PIN before encryption, do we then still need an IV for the AES encryption?

ISO 9564-1 format 4 does not need a IV since it adds entropy to the plaintext PIN before encrypting.  There is no need to append a random value to the PIN.

The Format 4 PIN block algorithm is illustrated above.  The PIN and the PAN are both padded.  The padded values are called the plain text PIN field and the plain text PAN field.  The last $8$ bytes of the padded PIN field are random.  The plain text PAN has deterministic padding. The plain text PIN field is encrypted and then XORed with the plain text PAN field and the result is then encrypted again, yielding the encrypted PIN block.
Format 4 is typically used with a fixed AES key for each encryption operation on a particular device.  Since there are only $8$ bytes of mixed-in entropy for each PIN-PAN combination, Format 4 has the potential to be vulnerable to a chosen plaintext dictionary attack.  An attacker could capture an encrypted Format 4 PIN Block.  The attacker could then recover the PIN by repeatedly encrypting all possible PIN values until by chance the encrypted PIN block is the same as the encrypted PIN block the attacker is attempting to decode.
There are $64$ bits of random data in the plain text PIN Block. The PIN is between $4$ and $12$ decimal digits and thus adds at least $13$ bits of entropy.  Therefore above attack would require at least $2^{77}$ chosen plaintexts.
It would difficult to obtain $2^{77}$ chosen plaintexts from any single device.  Furthermore, the PCI PTS standard requires compliant devices to rate limit PIN encryption to $120$ PINs per hour.  As such, the above attack is not feasible.


aWallet Password Manager After reading a lot of articles on ramping up the security of my web accounts, I started using aWallet Password Manager for Android to backup my passwords. I like it for following reasons:

I'm able to have fairly good-entropy passwords: I'm able to throw in a mixup of lowercase & UPPERCASE alphabets, digits, special characters (including spaces) and have reasonably long passwords (10+ characters)
Saving my passwords securely allows me to have distinct passwords for each web account which would otherwise be impossible. This would avert a cascading effect (giving away credentials of all accounts) that would be created if one of my accounts, whose login credentials I share with several accounts, gets compromised.

Needless to say, that 2nd point is debatable because having all credentials stored at a single place introduces a single-point of failure and poses an equal risk of the chain-reaction mentioned earlier.

Given my limited knowledge of Cryptography and doubts around privacy (given recent incidents of online thefts), I want to testify the security of aWallet Password Manager before storing my Banking / Card details in it. Here's what they claim on their Google PlayStore page:

  SECURITY FEATURES

  • All data is encrypted, including Entry names, Category definitions
  and the data itself.

  • Encrypts data using AES and Blowfish algorithms with key sizes of 256, 192 and 128 bits.

  • When the data file is decrypted, up to all combinations of algorithm, key size and cipher mode of operation (CBC, CFB, OFB and ECB) are tried with the Master password to unlock the data file. This makes brute force attacks longer. The app itself does not store any hint to the actual cipher, key size or cipher mode of operation.

  • Uses a randomly generated 'salt' combined with the Master password. Salt helps to protect from off-line dictionary attacks.

  • The key to open the data file is created by combining your master password with the 512-bit 'salt'. The result is hashed 1000 times by SHA-256. Repetitive hashing makes a brute force attack more difficult.

While none of these points make a lot of sense to me, the little bit that I know about Cryptography tells me that repeating a Cipher multiple times doesn't Mathematically improve the security ; it may only give one a false impression of added security. And because of this inconsistency, I started doubting the validity of their other claims.

Could you elaborate their claims / point me to some source where I can get an overview of the concepts to eradicate my suspicion; so as to prove or disprove the level of security offered by aWallet Password Manager?

EDIT-1: As per suggestions by @SEJPM, I've edited the question to remove it's off-topic sub-parts. The remaining part of the original question can be found here.

Elaborate their claims / point me to some source where I can get an overview of the concepts to eradicate my suspicion

This answer will focus on this part of the question: elaborating on the listed claims.

  All data is encrypted, including Entry names, Category definitions and the data itself.

As long as that doesn't impede functionality such as retrieving information from the database then it should be fine.

  Encrypts data using AES and Blowfish algorithms with key sizes of 256, 192 and 128 bits.

I am hoping/presuming this means it provides the option of these key sizes, and not that it uses AES-256, AES-192, and AES-128 to encrypt each block of data. That would be a very bad sign if it did, not for cryptographic vulnerability reasons, but more so because it would imply the author doesn't understand what they're doing.

There is no benefit from using Blowfish. Even the author of Blowfish thinks that people should stop using Blowfish.

There might be complications due to Blowfish having a small block size, but without knowing exactly what is being done such as what order the ciphers are applied in, it's hard to know.

  When the data file is decrypted, up to all combinations of algorithm, key size and cipher mode of operation (CBC, CFB, OFB and ECB) are tried with the Master password to unlock the data file. This makes brute force attacks longer. The app itself does not store any hint to the actual cipher, key size or cipher mode of operation.

This is simply a waste of the users time and the devices battery, assuming that the cipher, key size, and mode of operation are secure. This is not a good sign, and is trying to provide security by obscurity.

If there are only 4 modes of operation - none of which provide authentication - and they are selected at random, then guessing the mode of operation provides a maximum of 2 bits of security.

If there are only two cipher choices - AES and Blowfish - and it is randomly selected for each cryptogram, then it provides an additional 1 bit of security.

If there are only 3 key sizes - 128, 192, and 256 bits - and it is randomly selected for each cryptogram, then it provides an additional 1.5 bits of security.

Assuming these are all invoked with random choices for each cryptogram, then it provides a maximum of 4.5 bits of extra security.

The correct way to slow down brute force would be to use a significant number of iterations with the key derivation function that is applied to the password.

Note that using ECB mode at all is a big red flag.

  Uses a randomly generated 'salt' combined with the Master password. Salt helps to protect from off-line dictionary attacks.

This is good. However, using a 512-bit salt is twice as large as it needs to be.

  The key to open the data file is created by combining your master password with the 512-bit 'salt'. The result is hashed 1000 times by SHA-256. Repetitive hashing makes a brute force attack more difficult.

1000 iterations of SHA-256 is not sufficient, and provides only a meager improvement in security. The design of SHA-256 does nothing to prevent an attacker from using GPUs/FPGAs/ASICs to compute obscene numbers of password guesses per second (on the order of billions).

Ideally, an actual key derivation function such as PBKDF2, scrypt, or Argon2 would be used with a much larger iteration count (100,000-1,000,000) and set to consume as much memory as is possible/tolerable in order to drive up the cost of custom hardware and reduce an attackers advantage as much as possible.

Maybe users don't want to burn up battery with 100,000 iterations - However, in that case the iteration count should be configurable with a reasonably secure default. 1,000 iterations of SHA-256 is not a reasonably secure default.

Lack of Authentication

The descriptions do not mention anything about authenticated encryption. The lack of authentication implies that an adversary can modify ciphertexts and the user will have no way of detecting the modification.

Not providing authenticated encryption is a huge red flag.

Conclusion

All these points considered imply that the author of the software in question does not fully understand what they are doing. You should strongly consider finding an app that is more heavily vetted and was written by more knowledgeable people. Some of the flaws are quite serious that could lead to compromise of users data in the real world.


Is there any encryption algorithm that, with small change in input will produce big change in the encrypted output? As stated in the title, I'm looking for an encryption algorithm with the characteristics that, when inputs are slightly different, the encrypted output will be VERY much different, to the point that no one will suspect that unencrypted inputs are quite similar when they compare the encrypted outputs.

The TDES encryption algorithm doesn't seem to reproduce the above characteristics. So is there such an algorithm?

What you want, if at all possible, is an IND-CPA (or, preferably, even IND-CCA2) secure encryption scheme.  Such encryption schemes are by definition probabilistic (and/or stateful), so that even encrypting the exact same plaintext twice will produce completely different results.

Conveniently, there are plenty of block cipher modes of operation that provide IND-CPA security, as well as authenticated modes that even provide IND-CCA2 security (which includes resistance to active forgery attacks where an attacker may modify encrypted messages and observe the results of attempting to decrypt them).  Triple DES can be used with most of these modes — but you really shouldn't be using it nowadays, since AES is both faster and more secure.

If you absolutely need your encryption scheme to be deterministic, so that the same plaintext always encrypts to the same plaintext, the next best thing you can have is DAE security.  It's basically the same as IND-CCA2, except that because it's deterministic, an attacker can obviously tell if two encrypted messages have the same plaintext or not.

The first and most popular DAE-secure encryption method is SIV mode, although there are also newer and potentially faster schemes like GCM-SIV.  All of these are designed (and standardized) for use with AES; while you could in principle used them with TDES, that would be less secure (particularly due to the smaller block size) and generally pointless.

Conveniently, SIV and other DAE-secure encryption modes have the useful feature that, if you include a unique nonce as associated data with every encrypted message, they become fully IND-CCA2 secure, and still remain DAE-secure even if you accidentally use the same nonce twice.  This "nonce misuse resistance" is a very handy safety net to have, and IMO is a good reason to use AES-SIV (or AES-GCM-SIV) whenever possible.

Finally, I'd like to note that your description of your attempts so far doesn't really fill me with confidence that you know what you're doing.  (That goes particularly for the fact that you mentioned using TDES, but not which mode you're using it in — that's kind of the crypto equivalent of saying that you're driving a 4-cylinder internal combustion engine from 1995, but not specifying whether it's in a car or a motorbike or a lawn mover.)

If all this talk of "nonces" and "modes of operation" and "IND-CPA/CCA2 security" goes straight over your head, I'd suggest either picking up a good introductory crypto book and/or just browsing this site until it no longer does.
 While there are nowadays some relatively "foolproof" encryption APIs like NaCl crypto_secretbox available, you do still need at least enough basic crypto knowledge to understand the terminology and to be able tell a secure and well designed system from complete snake oil.  Or you can just hire someone who does understand all this stuff to design your cryptosystem (and someone else to review it — which you really should do anyway).


Block-cipher based vs Hash based MAC When it comes to MAC algorithms one can have many choices. CBC-MAC, CMAC, PMAC etc are some MAC algorithms that rely on block ciphers (ex AES) to generate a MAC. On the other hand HMAC is very popular on the Internet and relies on compression functions (ex SHA-1, MD5).

What are the drawbacks of each from a security perspective and how do you make a choice if you need to include MAC in your protocol?

Here are some advantages and disadvantages for each of the three classes of MACs, which I know about:

Based on block cipher

There are constructions where the security of the MAC is proven in terms of the security definition of a block cipher. This means as long as the block cipher is secure, the MAC will be secure.

There are constructions where encryption and MAC can be computed with almost no extra CPU cost compared to only encrypting.

Based on cryptographic hash (HMAC)

Assuming the underlying hash is secure, a HMAC guarantees that even an adversary who knows the key cannot produce two different messages for which the same HMAC value would be valid. Neither could an adversary produce a HMAC value which would be valid with two different keys.

One disadvantage is that security of HMAC cannot be proven based on the usual properties regarding collisions of the underlying hash. There could exist a secure cryptographic hash which would lead to an insecure MAC if used in an HMAC. Put differently, HMAC could be broken without ever finding a collision in the underlying hash.

Based on almost 2-universal classes of hash functions

This kind of MAC is provably secure.

Like a one-time-pad, this kind of MAC consumes key material. You will need some key material, that is used only for a single message.

Unlike a one-time-pad, the number of bits consumed does not grow with the message size. You can authenticate an arbitrarily large message using a constant number of key bits from your pool. (The key material also has a reusable part, that grows logarithmically in message size.)

Public key signatures based on cryptographic hash

It is possible to construct a public key signature using a cryptographic hash as the only underlying primitive. These can be proven secure based on the usual assumptions about the security of the underlying cryptographic hash.

A major drawback is that they are expensive to compute, and the signatures require a huge number of bits compared to other public key algorithms.

This is not really a MAC, because it is using asymmetrical keys. A signature could be used in place of a MAC, if it wasn't so expensive. The CPU time needed and the number of bits in a signature is prohibitive in many of the situations, where a MAC would be used.


Hill Cipher if the length of the string is not divisible by the Key Dimensions For a project, I want to encode the word "MEMBRANOPHONES" with the key "MULTITONE". I try spliting "MEMBRANOPHONES" into groups of 3, but then I get "MEM", "BRA", "NOP", "HON", leaving me with a 2 letter "ES". I can't multiply a 3 by 3 matrix by a 2 by 1 matrix, so what do I do in this case?

This is a standard problem in modern cryptography (eg for CBC-mode).

The standard solution is to use Padding or some other agreed-upon mechanism to encode variable-length messages as a multiple of the blocksize.

The most common padding is PKCS#7 padding: If one byte is left, append 0x01, if two are left append 0x02 0x02 and so on. Note that this requires you to also pad on messages which are a multiple of the blocksize (in case your message ends on eg 0x01).

As you are more concerned with letters than bytes, you can probably adapt the above scheme to use A instead of 0x01 and B instead of 0x02 and so on for the full alphabet. So in your particular case you would pad the message with a single A.


Is this "layered" XOR cipher secure? I am aware of the vulnerabilities of simple xor ciphers and recently I came across a block cipher that claims to solve those vulnerabilities.

The cipher goes as follows with both the block and key sizes at 256-bits: the key is separated into chunks of length 1 bit.  Every bit in the plaintext is xored with every key chunk.

For example assume that the first bit of the plaintext is 1. Say that the key is 10100101010010101…
The operation that takes place is:

1 xor 1 = 0
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 0 = 1

This continues until the end of the key and the result becomes the first bit of the ciphertext.

Is this really as secure as advertised?
If not why?

If I understand right, your operation effectively is
$$\forall i:  c_i = p_i \oplus k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$
whith $c_i$ the ciphertext bits, $p_i$ the plaintext bits, and $k_j$ the key bits.

As $\oplus$ (this is XOR) is associative, this is equivalent to

$$k^* :=  k_0 \oplus k_1 \oplus k_2 \oplus \dots \oplus k_n,$$
$$\forall i:  c_i = p_i \oplus k^*.$$

Now $k^*$ is either 0 or 1 - in the first case this operation is the identity, in the second case it is simple negation. Neither of those can be considered an encryption, and you effectively have a key space of 2 (= 1 bit).

Whoever told you this either wanted to play a joke with you, or knows nothing of cryptography (or both). Or I misunderstood your presention of the algorithm.


PAK Diffie-Hellman vs. sharing high-entropy key In order to setup an authenticated shared secret key between two clients, I am faced with the choice between two possibilities:

Let users set a (low-entropy) shared password and then perform some password-authenticated key exchange that is resilient to low-entropy secrets (as described here, for example).
Generate a high-entropy shared key and use it directly as a shared key.

Are there any advantages to “1.”, especially when users must communicate the password/key through a separate channel in both cases?

Nota Bene: The resulting shared key is used only once per client (Alice $\rightarrow$ Bob and Bob $\rightarrow$ Alice) and subsequently destroyed.

Are there any advantages to “1.”, especially when users must communicate the password/key through a separate channel in both cases?

As the comments (1, 2) already indicated: the first option “1.” will be easier to communicate.
When you talk about a “high-entropy key”, I assume you are generating that high-entropy with a cryptographically secure random number generator. To make such a random piece of data easy to communicate among humans, you would need to convert it to something like Base64… which means “2.” will have a longer message which needs to be communicated between humans. The longer the message, the more room you’re providing for potential human error during that communication.
To keep human communication easy, you could stick to option “1.” and let users set a (low-entropy) shared password. You can always opt-in to a kdf if you want to make it computationally more difficult to crack attack the user-chosen passwords.
Please note that I’m assuming you generate and communicate that shared key without allowing impersonation. If you don’t authenticate communication, no entropy in this universe is going to help.
TL;DR
I would advise to prefer PAK Diffie-Hellman (as described in RFC5683) because it additionally offers authentication, while sharing a high-entropy key without authentication merely provides more entropy… but not a single bit of security which could prevent impersonation (man-in-the-middle) et al.


Encrypting cryptocurrency seeds for cold storage I’d like some feedback on an encrypting algorithm. I’m not rolling my own, but even putting together well-proved pieces may create many pitfalls. (I don’t know if I'm stretching questioning in this forum. I'm after concrete feedback on concrete, potential pitfalls.)
The purpose:

Cold storage of encrypted cryptocurrency seeds (i.e. secret keys).

EDIT: The seed (as used in this question) is the super secret plaintext. But often called seeds, as it is normally a binary array, and not ascii.
The purpose is the same as for BIP0038 (* see summary below).
Likelihood of someone reusing a passphrase is definitely present.
The algorithm should be as simple as possible, to avoid errors in implementations.
My proposal:

Generate cryptographically random seed (32 bytes) (Or input from user*)
* EDIT: The seed is 32 random bytes. User may input a cryptographically random seed, generated somewhere else, if she wants to. The seed is used to generate public addresses. A bit like private/public key pairs. It's the private key, the seed, that I would like to encrypt and store.)
Input UTF-8 passphrase from user, applying canonical normalization
Generate cryptographically random salt (12 bytes)
(Possibly ask for an input on “toughness”, to adjust the argon2id parameters.)

.

Generate 32 byte encryption key, using Argon2id, using 2) and 3).
I guess the argon2id options is a separate topic altogether.
I think iterations = 2(something + toughness)

.

Encrypt the seed 1) with AES-CTR, using salt from 3) as counter, and encryption key from 5).

Encrypted seed (6) + Salt (3) is concatenated and base32 encoded to uppercase, to make the most compact QR code, appended by ‘:T’ + <toughness>.

.
My reasoning and Questions
Any tripwires I’ve tangled myself into?
AES-GCM is preferred over AES-CTR.
GCM has message authentication. But I don’t see mallability as an attack vector. You might as well burn the piece of paper, instead of scribbling on the QR code.
A) Are GCM and CTR equally good in this use-case?
Both have a catastrophic failure if the same key and counter is re-used.   (No difference there, that I am aware.)
B) Birthday problem. Why 12 byte salt?
Open for input. :)
Reading Birthday attack - Wikipedia, and if my math is correct:
An 8 byte salt would yield a likely birthday collision every 5x10^9 reuse of the passphrase.
A 12 byte salt would yield a likely birthday collision every 3x10^14 reuse of the passphrase.
But it will fit in the same size QR code, after base32 encoded. (Version 3, ECC level L.)
C) A 16 byte salt is still better. But is it needed?
Any considerations regarding Argon2id?
D) Is there a problem that the salt is reused for two different operations? (Both Argon2id and AES)
E) AES CTR vs CBC? The seed is 32 bytes long, so no padding is needed for CBC.  Both need a random counter/iv.  Are they equally good for this use-case, or does one of them have a better fit for the problem?
Why base32? Because QR has an optimized encoding for uppercase and digits. And security here is more than hacking. An unreadable QR code is just as disastrous.
Keepass is all very good for this too.
My use-case is scannable paper. And that my wife can use it if I get hit by a bus or fall off a cliff. :)
I apologize if this post being a bit long.  But it's putting the steps together that causes the security to break.
Any comment are welcoming. :)
vbakke
.
* The BIP38. https://en.bitcoin.it/wiki/BIP_0038 Uses scrypt, and 2xsha-ing the passphrase first. The salt derives from the passphrase, so reusing the passphrase is an issue.
BIP38 feels overly complicated. Like someone tying lots of bad knots, instead of tying one knot properly to secure the load. Simplicity is also security.

Unless otherwise noted, I assume adversaries know the genuine QR-code, and can alter it and submit it for decryption. I posit the design requirements are:

Confidentiality of $\text{seed}$, to as high a level as the passphrase + key stretching of Argon2 allows.
Integrity of $\text{seed}$, to 64-bit security level [ample in the context, where we want to catch an incorrect passphrase, or an altered QR-code which decryption is attempted in a legitimate context, with some low limit on how many times].
Ability to encode an arbitrary $\text{seed}$ [e.g. because it was generated independently of the procedure; this also is necessary to allow a change of passphrase without changing $\text{seed}$].

I suggest to get rid of AES-GCM, because we can do without it, and most portable implementations [not using AES instructions] use data-dependent memory accesses which can create side channels. Also, questions A/D/E disolve. Towards this:

At step 5, generate 64 bytes [that is set 64 for tagLength in the invocation of Argon2]. Split the output into first 32 bytes $K_0$, and last 32 bytes $K_1$.
For confidentiality, compute $C\gets K_0\oplus\text{seed}$ and encode it in the QR-code. On decryption, do $\text{seed}\gets K_0\oplus C$.
For integrity, use Argon2i [1 for hashType] with $C$ as salt, $K_1$ as password, 8 as tagLength, minimum workfactor [that is 1 for parallelism, 8 for memorySizeKB, 1 for iterations], other parameters as in step 5 [empty key, empty associated Data, same version]. The 8-byte result $T$ is encoded in the QR-code. On decryption, it's compared to decide is we accept the QR-code with the given passphrase. That comparison needs not be side-channel protected, but if it fails, nothing except an error indication must be output.

Security arguments:

The output of Argon2 is computationally indistinguishable from random, except if the passphrase is guessed; hence $C$ leaks nothing about $\text{seed}$.
The integrity test using $T$ is functionally a MAC keyed by an output of the main Argon2 of step 5; that's why the extra Argon2 can be fast.
We use Argon2i for integrity since it promises maximum side-channel resistance, and key stretching [which the other forms optimize] is not an objective.
Removal of AES makes testing a passphrase only marginally easier, because the computational burden of AES decryption is negligible compared to the main Argon2 of step 5. In the check of a $\text{seed}$ candidate the way that's done on normal decryption, the extra Argon2 is arguably comparable in cost to AES-GCM. And the cost of AES decryption is typically low compared to other possible tests of a $\text{seed}$ candidate (like testing it against a public key or signature).

On the $\text{salt}$ size (B/C), the main goals of $\text{salt}$ are

When adversaries attack many QR-codes and are content with breaking any [rather than one or few in particular],  $\text{salt}$ prevents the reduction (by a mere factor of two) in the expected work for dictionary attacks that would occur for QR-codes which $\text{salt}$ collide.
Making it futile to pre-compute Argon2 outputs [e.g. building rainbow tables] before getting one's hand on QR-code(s) [for a faster attack, or leveraging resources otherwise not available].

The proposed 12 bytes for $\text{salt}$ are fine from both standpoints: if we assume $2^{40}$ QR-codes, there's about one chance in $2^{12\cdot8-2\cdot40+1}$ (one in 130,000) that the first bullet applies. Except for passphrases and Argon2 parameters so weak that they give no useful protection, the second is no issue. In fact, from the perspective of one particular user, 6-byte $\text{salt}$ would be enough as long as the passphrase is not massively reused.

On using $\text{salt}$ as IV for AES (D): that's not an issue as long as there is no collision of both $\text{salt}$ and passphrase [because Argon2 makes no use of AES, hence the identity quickly dissipates]. If there is collision of both $\text{salt}$ and passphrase, both AES-GCM and this answer's proposal have the same issue: leak of $\text{seed}$ encoded in one QR-code leaks $\text{seed}$ in another. That's one area where AES-CBC has an advantage [because a difference in the first 16 bytes of $\text{seed}$ is likely to save the day].

GCM has message authentication. But I don’t see malleability as an attack vector.

AES-GCM encrypts just as AES-CTR does (except for an offset of one in the IV), but adds authentication. In the original proposal, GCM authentication has at least one important function: it catches using the wrong passphrase on decryption. Depending on what $\text{seed}$ is used for, malleability in the decryption could well be an attack vector. ECDSA is not claimed to resist in an attack context where adversaries can flit bits of the secret key.

Note: if the ability to encode an arbitrary $\text{seed}$ is not needed, we can set $\text{seed}\gets K_0$ and save the 32 bytes of $C$ [since it's all-zero]. This does not change security w.r.t. an adversary knowing the QR-code. If we want extra protection against adversaries not knowing the QR-code (which is quite reasonable), we can rename the $\text{salt}$ field of the QR-code to $\text{pepper}$ [to denote that it's secret to a degree], and increase it's size to say 24 bytes [which combined with the entropy in the passphrase and the Argon2 key stretching is more than overkill].


Building a cryptography system by combining a block cipher and a stream cipher? I have to come up with a design for a cryptography system by combining a block cipher and a stream cipher. I can't seem to come up with anything on my own. Can someone point me in the right direction with helpful resources and information to tackle this problem?

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

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

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

Solution 1: Building a stream cipher using a block cipher

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

Notice that:

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

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

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

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


Linear Feedback shift register over integers The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is:

It is supposed to be a normal Linear Feedback shift register but it doesn't seem to follow the "normal" lfsr rule. Is anyone able to explain the logic it follows?

I'm not sure I understood your question correctly, but what Solinas is doing is shifting the input polynomial by multiplying it by $t$ and reducing modulo $f(t)$

To compute the reduction it subtracts $f(t)=t^3-t+1$.
So, for example, after shifting the first line (where shifting means multiplication by $t$) what you obtain is: $t^3$ from which you subtract the modulus, so $t^3-t^3+t-1=t-1$ which is what you obtain in the second row.

And so on for the other rows.

In the table, the top row identifies the constant term, degree-1 term, and degree-2 term of the polynomials, while the second row (-1,1,0) identifies the value used for the modular reduction. The third row is the initial value of the LFSR which is $t^2$ by Solinas' construction.


How to prove Security of Onion Layers of encryption? CryptDB has Onion layers of Encryption to provide wider functionality from weaker forms of encryption. How do we prove such things are indeed secure ? Intuitively It seems ok. Are there any parallels in theory that is related say, security of multiple encryption schemes etc? or Universal Composability etc?

Is this same as Cascade ciphers ? Product Ciphers ?

In CryptDB, it is not really cascaded. According to encryption schema the layers are decrypted. At the end, the lowest level is the your security.

The current layers are RND (Highest Security) , DET (For Joining queries), SWP (Search), HOM (Add), OPE (Sort) etc.  OPE being least secure as it allows more inferences about the underlying data fields than others. A data field that is encrypted all these Onion layers offer security only as strong as the weakest (OPE or similar) !

The fact that there is no need for the removal of the layer implies there is no need to layers.