How does hill cipher key exchange takes place? I am giving a presentation in my college where hill cipher is a part of the presentation. I just wanted to know, how is the hill cipher key matrix is exchanged securely in order to decrypt the message?

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

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


Are any of the practical implementations of ORAM being used in a real world system? The concept of Oblivious RAM (ORAM) was first introduced by Oded Goldreich and Rafail Ostrovsky in 1996. However, in the past 5-10 years there has been a surge in the amount of research that looks into various realizations, optimizations and implementations of ORAM. My questions are two-fold:

Although ORAM was introduced around two decades earlier, why is there a sudden spike in the interest of ORAM by the research community?
Various applications of ORAM have been put forth, which includes: secure computation, data-outsourcing and secure processors. Is ORAM currently being employed in any real world systems for an application that it was intended for? If yes, please provide me with some reference.

In addition to Paul's answer there is even an ORAM module inside a processor architecture, fully implemented: “A secure processor architecture for encrypted computation on untrusted programs”

Abstract:

  This paper considers encrypted computation where the user specifies encrypted inputs to an untrusted program, and the server computes on those encrypted inputs. To this end we propose a secure processor architecture, called Ascend, that guarantees privacy of data when arbitrary programs use the data running in a cloud-like environment (eg, an untrusted server running an untrusted software stack).


Use of q-ary lattices in developing cryptosystems Why q-ary lattices are used to most cryptosystems rather than lattices.
In most of the papers q-ary lattices are used. Is there any advantage?
and

Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, lattice generated by B
               $$ L(B)=\{a_1v_1 + ........ + a_nv_n\ |\ a_1........,a_n ∈ Z\}$$
Fix q and given a matrix $$A ∈ Z_{q}^{n×m}$$
 m-dimensional lattice $Λ(A^T)$ is defined as
$$Λ(A^T)=\{y ∈ Z^m | y ≡ A^Ts\ (\text{mod } q) \text{ for some } s ∈ Z^n_q\}$$
How can we say that the above set of points forms the lattice and does it contains exactly $q^n$ points?

The main advantage of using $q$-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems.  So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness guarantee "for free."  By contrast, if one were to work "directly" with lattices, one would have to explicitly describe a distribution over lattices and their secret "trapdoors," show (or assume) that lattices generated in this way are hard, etc. etc.

Another reason is that the SIS/LWE problems are very easy to work with, and admit a lot of versatility; it's less obvious how to obtain comparable properties when working with general lattices.  For example, one can perform arithmetic on parity-check/generator matrices $\mathbf{A}$, which can yield many interesting properties and applications (e.g., trapdoor manipulations, homomorphisms, etc.).  Most of these arithmetic operations do have interpretations in terms of general lattices, but they've been much easier to discover and exploit when working with $q$-ary lattices and their parity-check/generator matrices.

Regarding your question about $\Lambda(\mathbf{A}^t)$, this is a lattice and hence it has an infinite number of points.  However, modulo $q$, it has at most $q^n$ distinct points, at most one per value of $\mathbf{s}$.  It has exactly $q^n$ points if and only if no two distinct values of $\mathbf{s}$ yield the same value of $\mathbf{A}^t \mathbf{s} \pmod{q}$, which holds if and only if the right-nullspace (mod $q$) of $\mathbf{A}^t$ is simply $\{ \mathbf{0} \}$.


Implementation of ECC operations in BMR I want to implement computing ECC operations (i.e., multiplication) in a BMR scheme (secure multi-party computation)
What is the best way to do it?
I found Fairplay MPC - to allow BMR computation through ASFL language, but it does not provide a good library for ECC operations.
Instead, CHARM implements several cryptographic functionalities, but without MPC.
Is there anything that combines the two approaches? (Both MPC and ECC operations)?
Edit: This question is about ECC operations as one component in a general MPC scheme.
CHARM
FairPlay

If you are looking to implement private ECC operations using BMR, then you need to convert these operations first into a Boolean circuit. This will be extremely expensive and not the way to go. Rather, you need a direct protocol for this. Note that there are secure protocols for ECDSA, if this is what you are looking for.


Is it true that for RSA with no padding, the length of data must be equal to the length of key? The question pertains not in terms of security but computing operational functionality, as it how the computation is done.

Is it true that for RSA with no padding, the length of data must be equal to the length of key?

If so, why is that so? What is the reasoning why the data needs should have the same number of bits as the modulus? What is the mathematical implication?

Examples:
Limitations to input size corresponding to key size in bits:

keysize: 512 bits  (64 bytes),  number of input bytes: multiples of 64
keysize: 768 bits  (96 bytes),  number of input bytes: multiples of 96
keysize: 1024 bits (128 bytes), number of input bytes: multiples of 128
keysize: 2048 bits (256 bytes), number of input bytes: multiples of 256
keysize: 4096 bits (512 bytes), number of input bytes: multiples of 512

The short answer is NO. Generally, it is not true that for RSA with no padding, the length of data must be equal to the key length. When and if that applies, that's a restriction of a particular cryptographic library, and either that's not the only restriction about the data, or the library does not allow reliable decryption of what's encrypted.

RSA (encryption) with no padding is a well defined algorithm when enciphering integers. It uses a public key $(N,e)$. The key length is given as the bit size $n$ of $N$; that is $n$ is the integer such that $2^{n-1}\le N<2^n$. This form of RSA encryption with no padding takes as input some integer $m$ with $0\le m<N$ called the plaintext (or message), and outputs the integer $c$ with $0\le c<N$ called the ciphertext, such that $c\equiv m^e\pmod N$ (or in other words such that $m^e-c$ is a multiple of $N$). That transformation is reversible for decryption. Notice that if we remove the restriction that $m$ is less than $N$, we create the problem that $m$ and $m+N$ yield the same $c$, therefore decryption of the ciphertext can not reliably recover the plaintext; for example, $m=2^n-N-1$ and $m=2^n-1$ both encipher to the same $c$.

RSA with no padding is not universally defined when we move to data rather than integers, for many reasons including:

There's no agreement on the stuff data is made of. Is that bits? Octets of 8 bits? Characters for various definitions of that?
Endianness in the conversion to integer and back.
Dealing with the aforementioned $m<N$ requirement; a fine option would be defining a fixed data size insuring that. For example, message data of exactly $\lfloor (n-1)/8\rfloor$ octets (and some usual conversion to integer) would insure $0\le m<2^{n-1}\le N$; but then that fixed data size is less than the key length (in octets).

The library in the question does not do the later. Its requirement seems to be that the input data length in bytes (octets) must be a multiple of $n/8$, where $n$ is the key size in bits (an a multiple of 8 in all the examples). We can guess that the input is split into data blocks of exactly $n/8$ octets, each individually converted to a number $m$ (probably using straight big-endian convention, which is the most common), then RSA-enciphered as above, with each result converted back to exactly to $n/8$ bytes using the same convention, and the results concatenated in the same order as the original to form the ciphertext. We have no way to guess what happens when one of the $m$ does not meet the $m<N$ requirement.

It seems the library in the question unify symmetric and asymmetric cryptography into a one-size-fits-all API, even if that's at the price of drawbacks:

Making it easy to unwillingly implement an unsafe cryptosystem; in particular, if some data belonging to a small set (like a dice throw, or candidates to an election) is enciphered in this way, it is trivial to break the encryption (just encipher each possible plaintext and see which match the ciphertext).
Allowing large data and subdividing that into blocks before enciphering each with RSA, which makes decryption grossly inefficient; and is insecure when used with no padding: in particular repeated plaintext blocks are visible in the ciphertext.
Either ignoring the $m<N$ requirement (with the consequence that for some data, encryption followed by decryption does not give back the original data); or rejecting some data at encryption time (which might escape testing). Most likely, one of this occurs when enciphering a block of data consisting of $n/8$ octets all 0xFF.

Except in very specific cases (such as enciphering a random bit string of $n-1$ bits):

Do not use RSA with no padding (also called textbook RSA or naked RSA), but rather use some secure RSA scheme built on top of that; see e.g. RSAES-OAEP of PKCS#1. Among the reasons not to use RSA encryption with no padding

Like any deterministic public encryption, it is unsafe when the plaintext has low entropy.
Short plaintext is vulnerable. In particular, even uniformly random plaintext of $\lfloor n/e\rfloor$ bits can be found by $e^{\text{th}}$ root extraction, and there are extensions to that.
Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem has more excellent reasons; and there are even more.

Do not use RSA to directly encipher application data that could be larger than what makes the RSA scheme used safe (for example, RSAES-OAEP with 2048-bit key and SHA-256 hash allows to safely encipher data of 0 to 190 octets and still have enough randomness added by the scheme); rather, use hybrid encryption.


Is there a library-less implementation of DSA available to read? Is there a pedagogical library-less implementation of DSA available to read?  (Not ECDSA.)

Obviously BigInteger and hash functions may be from libraries, but I want to read the implementation of all of the calculations involved in signing a message and verifying a signature, using whatever BigInteger operations are appropriate for the language.

Ideally it will treat keys as numbers, and not interact with DER/PEM file formats in any way.

Java, Python, Javascript, Haskell, or even C would be great.

Any recommendations?

Not great answers but something:

If you just want the mathematical computations, indepedent of implementation, Wikipedia has a good explanation, and the standard is definitive.

Java JCE source is open. The repository is git (which I don't have set up); Oracle(Sun) JDK distribution has src.zip but exclude the JCE part; JRE distribution has no source at all. openjdk-src package for CentOS/RedHat does include JCE, and I'd assume/expect at least some other Unixes but maybe not Windows the same. The JCE facade/provider/engine framework somewhat complicates the code for all providers, including DSA.

Java BouncyCastle (http://www.bouncycastle.org) source is open. Their build recipe is too complicated for me, but can be avoided by downloading the jar(s) and the source and telling your debugger to link them; I use Eclipse and just set the source property for the library. BC includes both a provider implementation, with the same complication as the Oracle one, but also a "lightweight" API, where you just call an implementation directly; org.bouncycastle.crypto.signers.DSASigner is the one you want here. That's what I'd use if I wanted to debug something in Java.

OpenSSL C (http://www.openssl.org) source is open. Beyond a standard C toolchain (compiler, preprocessor if separate, assembler if separate, linker, lib/archive, etc, and debugger) build requires only perl (builtin to nearly all Unix, and easily available for Windows); a separate assembler can be needed for an optimized build, but for pedagogical you don't need optimized. Although linked enough you need to build the whole thing, for execution the code is quite well modularized and you can easily write a small program that just calls the DSA_* and BN_* (bignum) modules to do a few DSA operations. However, C code must explicitly deal with error handling and memory management that is (mostly) implicit in Java, and OpenSSL C code for older modules is not exactly the clearest possible. OpenSSL also makes it easy to add file handling when and only when you want.

Note that the numbers involved in DSA, even using the long-obsolete 512-bit minimum of original FIPS186, will be much too large to deal with or check or recognize manually, so you can step through code and see that it does something that works, but won't actually learn any more about what it does than the formulas in the spec told you to start with.


How to avoid a chicken and egg scenario with encrypting passwords? I am working on application that allows users to upload files containing company data and then share those files with a list of other users that have specific roles within the system.

I want to encrypt the uploaded files to protect the data at rest while allowing the files to be shared by people who do not know the encryption password. The uploaded files are owned by the company that they belong too not by the user who uploads them.

When a user creates an account on the system a private-public key pair is generated for the user, the private key is stored in the database and is encrypted with the users clear text password, which is accessible during the login process. User passwords are salted, , stretched hashes so other than during login the app does not know the clear text of the users password.
When a user log's into the system successfully the encrypted user's private key is pulled from the database, decrypted and the private decrypted key is stored in the http session. I am assuming that while the decrypted private key is in RAM it going to be very hard but not impossible for a hacker to get a private key out of the RAM of a running process.
When a user uploads a file the following happens:

A secure random UUID is generated and used as the password to encrypt the uploaded file using AES 256
The generated UUID is then encrypted with the user's public key and stored in the database.
The system determines a list of every user that can access that file

For every user that can access the uploaded file the generated UUID is encrypted with that user's public key and the encrypted UUID is stored in the database.

When a file is being downloaded here is what the system does.

It locates the encrypted password for the file being downloaded
Decrypt the encrypted password using the user's private key
decrypt the file using the file password
return the clear text of the file to the user

To me this seems to be more secure than just storing the files on the server unecrypted a hacker who steals a copy of the data would not be able to read the files, since they would have to figure out the clear text passwords of the users before they could get at the user's private key.

The problem is dealing with password rests, since the users private key is encrypted with the users password if the user forgets their password and does a password reset they would loose their private key and thus access to the files they uploaded. Since I need to have a password rest feature in the application I am into a chicken and egg scenarios because how do I safely store the private keys of the users without end result being less secure than doing nothing?

Is there any way to store private keys that are encrypted with a users clear text password and still have a way when resetting a password to preserve access to the users data?

I am not a security expert and would prefer to use a known solution / library for this problem but I can't seem to find any so I have to make my own solution.

As fgrieu notes, the problem as specified is unsolvable: if the server alone should not be able to decrypt the files, then there must be something (in this case, the password) possessed by the user but not the server which is needed to decrypt them.  If the user loses this extra information, there's no way the server can provide them access to the files — if it could, it could also provide itself with access.

However, let's step back and think about what a "password reset" really accomplishes.  Basically, it's a mechanism that allows users to prove their identity and access their data using some proof of identity other than their usual password.  For example, in the case of a password reset e-mail, the proof of identity is effectively access to a predesignated e-mail account, to which the password reset code is sent.

(There are various fundamental security concerns with that, as with most "password reset" schemes, but I'll ignore those for now and assume that having a password reset mechanism has been found necessary and desirable, and that the only issue is how to implement it.  I do strongly recommend that the user should be able to opt out of any such mechanism in advance, if they wish to do so in order to minimize the attack surface for their account.)

So, instead of having the server send the user a single-use password reset code after the user has forgotten their password (which is impossible in this case), you could allow the user to request one in advance, to be saved in case they need it later.  Indeed, you could even send one automatically (unless the user explicitly opts out) as part of the signup process, and resend a new one whenever the previous one has been used.

In effect, you'd be allowing your users save a back-up key to their account.  I should note that this is not a new idea: for a recent example, the Firefox Sync service does something quite similar.

What should this back-up key contain, then?  Well, obviously it needs to allow the server to access the user's internal key, just like a normal password would.  It probably should not be the user's normal password, though, or anything related to it, just to avoid concerns about password reuse.  Also, if you want the back-up key to be single-use, it should not simply be a copy of the internal key either.

One simple solution would be to just generate a random password (of sufficient length), encrypt the internal key with the password, save the encrypted key at the server and send the password to the user as their back-up key.  Then the only difference between this back-up key and the user's normal password would be the actions the server takes when the user logs in with the back-up key (typically, request a new password, generate and send a new back-up key, and replace the old ones so that they can't be used again).


What's the difference between rsa_pss_pss_* and rsa_pss_rsae_* schemes? I'm trying to understand the difference between rsa_pss_pss_ and rsa_pss_rsae_.

The picture shows the extension of TLS1.3's ClientHello.

I view the OpenSSL code and find the rsa_pss_rsae_* scheme is corresponding to the scheme in Section 8.1 in RFC 8017 but what about rsa_pss_pss_* scheme?

And it's weird that I find some annotation like this:

  TODO this does not differentiate between the rsa_pss_pss_* and rsa_pss_rsae_* schemes since we do no have a chain here that lets us look at the key OID in the signing certificate.

What's the matter with this chain and key OID?

In my understanding the signature schemes is only applicable to the type of private key (RSA or EC).

Summary: they aren't different signature schemes. Both specify the use of RSA-PSS. The difference is in how to parse the certificate to find the public key.

RSA-PSS (also spelled RSASSA-PSS and other variants) is a family of short-message signature schemes defined in PKCS#1 (RFC 8017). A short-message signature scheme can only sign a message with a small length limit; normally the payload is a hash of a message that can be arbitrarily long (in pratical terms). RSA-PSS is a family of schemes because it is parametrized by a mask generation function (and a salt length but I won't discuss that here; you can view it as a parameter of each signature rather than a parameter of the signature scheme). The only mask generation function anyone uses is called MGF1, but it is parametrized in turn by a hash function. Thus RSA-PSS-MGF1-SHA-256 is one example of a short-message signature scheme. RSA-PSS-MGF1-SHA-256-SHA-256 and RSA-PSS-MGF1-SHA-256-SHA-512 are two examples of message signature schemes that use the hash-and-sign construction, with RSA-PSS-MGF1-SHA-256 to sign the hash.

rsa_pss_pss_sha256 and rsa_pss_rsae_sha256 both indicate the RSA-PSS-SHA-256 signature scheme, in the same way that rsa_pkcs1_sha256 indicates the RSA-PKCS#1v1.5-SHA-256 signature scheme which uses the RSA-PKCS#1v1.5 short-message signature scheme. The reason there is a pair of values for each PSS-based scheme is that signature algorithm extension in TLS 1.3 encodes a little bit more than a signature scheme.

That extra bit of information is how to find and validate the public key. For the most part, given a TLS version and a ciphersuite, there is only one way to do this: in a ciphersuite that uses certificates (i.e. the “normal” ciphersuites, as opposed to ciphersuites without authentication or using pre-shared keys or raw public keys), you parse the certificate chain, check that the chain of signatures is valid, and check that the root of the chain is acceptable. There is no other method in use in the TLS protocol.

But wait, how do you parse certificates? The TLS protocol only specifies one certificate format, which is X.509. So there's still no need for any extra information. I won't go into detail about X.509, suffice to say that there is a standard way to find the public key and the signature, and both annotated by some information that says what type of key
or signature it is. The key or signature type is conveyed by an OID.

Obviously, since there are two standard signature schemes that use RSA keys (RSA-PKCS#1v1.5 and RSA-PSS), they each have their own OID. Less obviously, there are also multiple key types for RSA keys. There's an OID called rsaEncryption which allows the key to be used for any of the standard encryption or (despite the name) signature schemes. And there's an OID called id-RSASSA-PSS which indicates that the key may only be used for PSS signatures. This is explained in RFC 4055. In addition to restricting the use of the key to the RSA-PSS signature scheme family, using id-RSASSA-PSS to identify the RSA key rather than rsaEncryption allows the certificate to indicate which scheme parameters to use (MGF1, its hash, and other rarely-used parameters). The reason to have a distinct key OID is that if you use the rsaEncryption then there is no way to specify that the key must be used for PSS only, and if someone finds something signed with PKCS#1v1.5 then it must be a forgery that takes advantage of a weakness in PKCS#1v1.5. (There is no known weakness of PKCS#1v1.5 when correctly implemented, but one may be discovered one day, and PKCS#1v1.5 verification is difficult to implement correctly.)

So what does this have to do with TLS? Some TLS implementations use an X.509 parser that only recognizes rsaEncryption. So they don't include the rsa_pss_pss_sha256 value when they send the signature algorithm extension, they only include rsa_pss_rsae_sha256 (if they support it), where the rsae part stands for “encoded with rsaEncryption in the certificate”. Others may consider rsaEncryption to be legacy, and they don't include rsa_pss_rsae_sha256, only rsa_pss_pss_sha256 (if they support it), where the second pss stands for “encoded with id-RSASSA-PSS in the certificate”.


Role of xor in ARX construction In ARX construction like Salsa 20, why xor operation is required? That is why AR is not sufficient? Note that xor is a linear operation.

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

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

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


Can a low density subset sum problem be intractable? Hardness of a subset sum problem depends on it's density.

Is it possible for a subset sum problem to be intractable even if it's density is less than 0.9408?

Yes.    By reduction from 1-in-3-SAT, subset sum remains

NP-hard when the subset's size is part of the input, so we can

[add an arbitrarily large number to each element

and  (that_number)*(subset_size)  to the target]

to get that for all positive integers c, [subset sum with density less than 1/(1+(n^c))] is NP-hard.

Here's a much better question:  "Is it possible for a subset sum problem to be"

strongly hard-on-average "even if it's density is less than 0.9408?"

(I do not know the answer to the better question.)


Performing EdDSA/Ed448 employing Montgomery ladder EdDSA can be efficiently performed employing the Montgomery ladder. In order to implement this method, the base point should be converted to Mont. space, then the Mont. ladder should be executed, and the $y$-coordinate is required to recover. Eventually, the achieved point should be converted to twisted Edwards space.
I design a scheme to work in twisted Edward space, and all results are verified by the given test vector in RFC 8032.
Now I am trying to work over Montgomery space. The first three mentioned steps, i.e., convert the base point to Mont., Mont. ladder execution, and y-coordinate recovery can be performed simply. However, the back transformation has a problem. Based on the equation described in RFC 7748, the map between Mont. space and Ed space are as follows:
\begin{multline}
(x, y) = \frac{(4*v*(u^2 - 1)}{(u^4 - 2*u^2 + 4*v^2 + 1)},- \frac{(u^5 - 2*u^3 - 4*u*v^2 + u)}{(u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u)}
\end{multline}
I have used (5 , 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362) as the base point over Curve448. Furthermore, in $y$-coordinate recovery, I suppose $A=156326$, and $B=1$. After $y$-coordinate recovery, the $(u,v)$ coordinates in Mont. space is represented in projective coordinates, i.e., $(X,Y,Z)$. Now this point is required to converet to Edward space, i.e. $(x,y)$.
This is my attempt (in sage) to achieve the point in Ed448-Goldilocks:
#P_projective=y_recovery(R0,R1,P_base) where R0=k*P_base
x2=R0[0]
z2=R0[1]
x3=R1[0]
z3=R1[1]
x1=P_base[0]
y1=P_base[1]

t1 = mod(x1*z2,p)
t2 = mod(x2+t1,p)
t3 = mod(x2-t1,p)
t3 = mod(t3^2, p)
t3 = mod(t3 * x3,p)
t1 = mod(312652 * z2,p) #2A = 2*156326
t2 = mod(t2 + t1,p)
t4 = mod(x1 * x2,p)
t4 = mod(t4 + z2,p)
t2 = mod(t2 * t4,p)
t1 = mod(t1 * z2,p)
t2 = mod(t2-t1,p)
t2 = mod(t2 * z3,p)
t1 = mod(y1 + y1,p)
t1 = mod(t1 * z2,p)
t1 = mod(t1 * z3,p)
X = mod(t2-t3,p)
Y = mod(t1 * x2,p)
Z = mod(t1 * z2,p)

# convert from Mont. space to Edwards space where x=a1/a2 y=b1/b2
a1 = mod(4*Y*Z*(X^2-Z^2),p)
a2 = mod(X^4-2*X^2*Z^2+4*Y^2*Z^2+Z^4,p)
b1 = mod(-(X^5-2*X^3*Z^2-4*X*Y^2*Z^2+X*Z^4),p)
b2 = mod(X^5-2*X^2*Y^2*Z-2*X^3*Z^2-2*Y^2*Z^3+X*Z^4,p)

a2_inv = Integer(inverse_mod(Integer(a2),p))
x = mod(a1*a2_inv,p)

b2_inv = Integer(inverse_mod(Integer(b2),p))
y = mod(b1*b2_inv,p)

The results are not correct. what mistake I did? Should I do any other step to get the same point in the Ed448 curve?

According to Alternative Elliptic Curve Representations,  each other point $(x1,y1)$ of Edwards448 corresponds to the point $(u,v)$ of Curve448, where:
$u = y1^2/x1^2$
$v = y1*(2-x1^2-y1^2)/x1^3.$
Under this isogenous mapping, the base point $(G1x, G1y)$ of Edwards448  corresponds to the base point $(Gu,Gv)$ of Curve448. The dual isogeny maps both the point at infinity and the point $(0,0)$ of order two of Curve448 to the point $(0,1)$ of Edwards448, while each other point $(u,v)$ of Curve448 corresponds to the point $(x1,y1)$ of Edwards448, where:
$x1 = 4*(u^2-1)*v/((u^2-1)^2+4*v^2)$
$y1 = u*((u^2-1)^2-4*v^2)/(2*(u^2+1)*v^2-u*(u^2-1)^2).$
under this dual isogenous mapping, the base point $(Gu, Gv)$ of Curve448 corresponds to a multiple of the base point $(G1x, G1y)$ of Edwards448, where this multiple is $l=4$ (the degree of the isogeny)


Error Detection/Correction technique for Encypted Data I will be very pleased if anyone can clarify me that, can we use the same error detection/correction techniques like (Convolutional code) for the error detection/correction of encrypted data.
Or do we need separate techniques for plain data & encrypted data?

Thanks,

Not only is it easier to do error correction/detection after encryption, it is risky to do the error correction before encryption.

This is because the attacker would know parity check relations (in the typical case of a linear code being used) between the bits of the plaintext, which could get them started on an attack.


Can Zk-SNARKs verify the results of turing-complete computations? My understanding is that Zk-SNARKs (and zero-knowledge proofs in general) can be used to prove that a polynomial-time computation has a certain output, while keeping one or more of the inputs to that computation hidden.

For example, say you have a string h which is the output of a fixed hash function. If you know an input x which hashes to h, you could use a Zk-SNARK to prove you know x in zero knowledge (i.e. without revealing x). Equivalently, given a verification function like this:

verify(x,h):
    return hash(x) == h

you're essentially proving that you know inputs to verify which make it return true, without revealing all of those inputs.

So, here's my question. Suppose you have a secret poly-time, single-argument function f. Given a public input x and a public output y, could you use a Zk-SNARK to prove in zero knowledge that f(x)=y? I.e., given the function

verify(f,x,y):
    return f(x) == y

could you still construct a proof showing that verify returns true while keeping f secret? The difference between this situation and the above one is that now you're proving something about a verify function that is itself running an arbitrary function, rather than one which simply does some fixed calculations to check things--and this seems like a pretty significant difference to me.

It seems like this should be possible in theory, because if f is poly-time then f(x)=y is still an NP statement (although I may be wrong about that)--but I'm wondering if it's possible in practice with today's Zk-SNARKs.

The way I phrased my question, I guess knowledge of such a function is trivial, because if the prover knew y in advance, they could just define f to return y. So to make things more interesting, you could imagine a situation where the prover commits to f in advance, and the proof is expanded to verify that the f used to compute y matches the commitment.

Yes. Express $f$ as a (say, Boolean) circuit. If $f$ is poly-time it will have a number of gates that is polynomial in the input size. A universal circuit $U$ is a Boolean circuit that evaluates any circuit up to bounded size (see e.g. this eprint from 2017 by Günther, Kiss and Schneider). The input to $U$ will be bits representing the structure of the circuit of $f$. Since $U$ is just another Boolean circuit, it can also be represented as a QAP as in the Pinocchio paper, or whatever the zk-SNARK uses.


Randomness in generation of Virtual Machines from pre-built Image I am studying Multi-Tenancy vs. Virtualization, and I got thinking about randomness, true randomness, virtualization etc, and I couldn't find anything on it.

From what I gather, /dev/urandom is just as good as /dev/random and you should use it instead, BUT... it doesn't bloc if you "don't have enough entropy"... That has been extensively discussing before and there is a consensus that /dev/urandom is more than enough for everyday usage.

But if I am creating virtual machines on-demand from a single image, with the whole deploy process automated (Thus replicating all the steps and possibly durations for each step), won't this mean very little entropy...?

I read about seeding VMs to get more entropy, but is that approach feasible, has it been done, is there some/any consensus on this?

This is a conceptual question, I have no specific implementation I'm working with, I  just want an outline about this possible issue where lack of randomness can possibly be seen in everyday usage (Or if I am mistaken, which is very possible), and if there is consensus how one should approach this possible scenario.

I'm trying to imagine something uses VMs based on a single image, and it gets so big that it becomes "rewarding" to build something akin to a "rainbow table", in the sense of using this "not-so-random" starting pool that is the same for all VMs to find out any and all possible encryption keys/hashes/etc used for securing said installation, thus being able to break into a system, provided the attacker had access to the algorithm and images used to generate the system, and that he has access to the result of said encryption.

If an attack like that is even possible, what would be risk level of that? Would it be better to re-hash everything or something after gathering enough entropy on the new VM, possibly by using something like /dev/random, or even then it is a bad choice...? What about seeding this machine with entropy...?

How should one approach this problem, if it is indeed a problem?

Low entropy for PRNGs is bad.
If you set up a VM by automatized software, you won't have entropy for your PRNG which is not good.

What would be the risk level? Weak cryptographic keys (pretty bad if this is f.ex. a SSH log-in key or someting like this).

Seeding the VM with entropy rich data from the host is the standard solution and will solve the problem.

In my edition of "Cryptography Engineering: Design principals and Practical Applications by Schneier, Fergueson and Kohno" the following solutions are described (for seeding the Fortuna-CSPRNG):

Make the VM-creating system (originally the backup system) PRNG aware -> let it update the PRNG's seed file.
Hash the current time. (originally, again backup system: hash the current time along with the seed file). This works unless the clock's reset and will prevent the PRNG from outputting the same bits. (no high entropy :-( )
Same as 2. but use a counter for each VM you create and hash that instead of the time. (again originally for backups)
Provide entropy via a randomly generated seed file.
Just wait for random events to take place. (if your PRNG implementation is good you can't fully reproduce things like RDRAND output or hard-drive noise) This might take some time and should be last line of defense.

Conclusion: Entropy feeding from the outside is the best option.

I hope this gives you some answers.


An example of an appropriate use case for AES-CBC encryption without authentication? I have been learning a lot by studying the questions and answers here on crypto.stackexchange.com and an grateful for this community.

Recently in this question AES in CBC Mode Is totally unsecure if no defense is provided for padding oracle attack, right? I learned that CBC is secure against chosen plaintext attacks even though it isn't secure (by itself) against chosen ciphertexts attacks or padding oracles attacks.  That makes sense to me.

From what I have learned so far, I would think that there are no cases where using a CBC encryption mode would be wise unless it were paired with some kind of authentication algorithm like HMAC.  But from the answers for the linked question above I get the impression that perhaps that's not true, and there are cases where such use might be reasonable.

What is a specific example of where using CBC mode encryption (ex. AES-CBC) without pairing it with validation would be an appropriate and reasonable choice?

Full disk encryption is only an example of encryption of data at rest. For that kind of usage CBC could suffice if only confidentiality is required. This is often the case if the user just wants to hide something, say an illegally downloaded movie. In that case you don't care if anybody can change the ciphertext, you just want to make sure that nobody finds out what is encrypted (possibly leaking the size of the file, which can be pretty unique for such large files, by the way).

The same goes for ransomware. If ransomware encrypts a file then the rightful owner can muck with the encrypted file as much as he wants; the data just gets further mangled. In this case I assume that there is no padding oracle attack, I suppose that the victim simply gets an application with the private key to decrypt files instead of the victim sending files over for decryption. That's one way to implement it anyway.


How to generate successive stream-cipher keys? I've identified a weakness in a distributed simulation system I'm looking at, and I'm looking for some advice on how to fix it.

Clients initially negotiate an authentication token with a login server using Diffie-Hellman. They then connect to the each simulation node they require (seperate hosts) in turn, using the token as a key for data encryption.

The problem is that for a single client the same key (i.e. the token data) is being used for each node.

I'm thinking of hashing the token n+1 times each time it is used, to produce a new key each time. Unfortunately I don't have the option of re-negotiating an entirely new key for each node a client wants to access.

Does this sound OK, at least for a temporary fix?

Thanks for any advice.

Cheers!

I can see a number of problems with your suggestion to let the session key $sk_{n,c}$ for node $n$ and client $c$ be $sk_{n,c} = h^{n+1}(masterkey_c)$, where $masterkey_c$ is what you refer to as "token":

You should use different keys for encryption and integrity, and different keys for the client -> node direction and the node -> client direction, making four keys total for each node and client combination.
The keys are not independent. If an adversary is able to compromise a node $n$ and get the session keys of that node, then the sessions of each node $n+k$ with $k > 0$ will also be trivially compromised.
There is no easy way to negotiate a new $sk_{n,c}$ if the connection between client $c$ and node $n$ is dropped. The client will have to negotiate a new $masterkey_c$.

I presume you have already figured out a way to securely distribute $masterkey_c$ from the login server to the nodes. The question is exactly which security features you need. I presume the communication between the client and the node is two-way, and that your application is such that you both need protection from replay attacks and the ability to easily renegotiate the session key of any client and node pair without having to renegotiate the master key for the client.
To begin with, you need a key derivation function $KDF(keymaterial,label,nonce)$. If the only cryptographic primitives you have are the stream cipher and the hash, you will firstly have to implement HMAC since it will be used for the protocol later. Secondly, you could then construct the KDF as follows:
$KDF(keymaterial,label,nonce) = HMAC(keymaterial,label|nonce)$
where $|$ denotes concatenation.
Thirdly, you need an unpredictable pseudo random bit generator. Since the client is performing a Diffie-Hellman handshake with the login server, it must have one already. If the nodes don't have access to the same functions the login server has, they could get a random $seed$ sent to them by the login server and use the following:
$DRBG(seed,ctr) = KDF(seed,"drbg",I2OS(ctr)), ctr = ctr + 1$
client/node master key
Server side, the login server performs the following calculation and sends the result to the corresponding node. The client might perform the calculation immediately before connecting to a node. The keymaterial $masterkey_c$ is the output from the Diffie-Hellman handshake:
$masterkey_{c,n} = KDF(masterkey_c,"mast",I2OS(n))$
client/node handshake
Input: $masterkey_{c,n}$
Output: message counter c->n $Ctr_{c,n}$ message counter n->c $Ctr_{n,c}$, session keys $ek_{c,n}$, $ek_{n,c}$, $ak_{c,n}$, $ak_{n,c}$.
Note: For simplicity, I assume you are using a stateful stream cipher, and that the encryption keys $ek_{c,n}$ and $ek_{n,c}$ can be regarded as stream cipher states that get updated by each call to the encryption function $E(keystate,text)$.

Both the client and the node set both message counters to $0$.
The client generates a random nonce $nonce_c$ and sends it to the node.
The node generates a random nonce $nonce_n$ and sends it to the client.
Both calculate $ek_{c,n} = KDF(masterkey_{c,n},"ekcn",h(nonce_c)|h(nonce_n))$, $ek_{n,c} = KDF(masterkey_{c,n},"eknc",h(nonce_c)|h(nonce_n))$, $ak_{c,n} = KDF(masterkey_{c,n},"akcn",h(nonce_c)|h(nonce_n))$, $ak_{n,c} = KDF(masterkey_{c,n},"aknc",h(nonce_c)|h(nonce_n))$.
The client calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|E(ek_{c,n},"verify")), Ctr_{c,n} = Ctr_{c,n} + 1$ and sends it to the node. The node disconnects if it fails.
The node calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|E(ek_{n,c},"verify")), Ctr_{n,c} = Ctr_{n,c} + 1$ and sends it to the node. The client disconnects if it fails.

There should probably be some safety mechanism in the handshake protocol that prevents the client and the node to repeat it indefinitely in case of failure. For instance, they could attempt to complete it three times, before they give up and the client either marks that specific node as unreachable, or returns to the login server to negotiate a new $masterkey_c$. The client should only do the latter if it fails to complete the handshake with several nodes.
Bulk data transfer
Input: $pt$
Output: $ct|mac$
Client to node:

$ct = E(ek_{c,n},pt)$
$mac = HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$
$Ctr_{c,n} = Ctr_{c,n} + 1$

The client sends $ct|mac$ to the node, the node calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{c,n}$ and decrypts $ct$ otherwise.
Node to client:

$ct = E(ek_{n,c},pt)$
$mac = HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$
$Ctr_{n,c} = Ctr_{n,c} + 1$

The node sends $ct|mac$ to the client, the client calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{n,c}$ and decrypts $ct$ otherwise.
Hope this helps


Pepper and key derivation/stretching I understand the pepper concept of adding but not storing a secret and iterating through the set of possible secret values for verifying.

But is pepper also useful when it comes already to the use of key stretching algorithms?

Key stretching is used to make a (possibly) weak secret more robust against brute force attacks by increasing the validation time. The pepper method has the same purpose. Does it make sense to combine this techniques? Following the important security principle keep it simple, I would expect that e.g. stretching a password with PDKDF2 and a higher iteration value is better than combining pepper and PDKDF2. Is this assumption correct or do I miss an important aspect? Thx.

A pepper is similar to a salt, but it is kept secret. So while the salt is stored in the DB the pepper is kept elsewhere, for instance in the code that verifies the password hashes.

A pepper can be used anywhere where a salt is present - mainly PBKDFs: password based key derivation functions. It makes somewhat less sense for KBKDF's: key based key derivation functions as the input secret of KBKDF's is already a key and you would expect it to be kept secure as it is.

The pepper is not really a method, it is just an addition to the salt. The salt is still required as the pepper is generally static. That would mean that identical passphrases would generate the same password hash or symmetric key.

The pepper doesn't increase the work factor / iteration count (much) but it does make it impossible for an attacker to perform the calculations while the pepper is not known. Basically the pepper acts as a secret key that is required to perform the calculations.

Stretching the password using an iteration count is a different way of protecting the password. These are two different ways of making a PBKDF more secure; they do not directly influence each other.


Zero-knowledge proofs vs. "Identification schemes"? (as in Katz--Lindell) Most modern papers on zero-knowledge proofs (for example, BBB+16) recycle essentially the same list of boilerplate definitions, concerning soundness (formulated using extraction or some form of "emulation") and zero-knowledge (involving simulation).

Yet Katz and Lindell's incredible book does not use these definitions—instead speaks only of an Identification scheme (see [KL15, p. 452]), which is either secure (against a passive attack), or isn't (i.e., see Def. 12.8). For example, the Schnorr protocol is formulated only as an identification scheme (Fig. 12.2). Moreover, both its perfect zero knowledge and 2-soundness are implicitly contained in its proof of security (Thm. 12.11).

My question is: should I view this simpler Identification scheme-based definition as "the future"? Can we get by with definitions of this sort, i.e., can this definition capture everything we "care about" in zero-knowledge proofs? What are the reasons for keeping the more traditional definitions around, if any?

Moreover, has an Identification scheme-based definition been formulated for more general settings, where the "statement" of the relevant NP language has a complicated structure (is no longer uniformly random, maybe selected by the adversary, etc.)? Where can I find these more general formulations?

I think I'm qualified to answer this question :-). The approach of going via identification schemes suffices for constructing secure signature schemes. Since this is the aim of this part of the book, it is much simpler than doing full blown zero knowledge. However, if you are interested in looking at sigma protocols and compilation to non-interactive zero knowledge via Fiat-Shamir, then you are going to need the more complex definitions. So, in short, what we do in the book is not more general; on the contrary, it's more specific, but suffices for what we need.


How can Cipher Block Chaining (CBC) in SSL be attacked? I am trying to understand how CBC-mode in SSL/TLS can be attacked.

I have been looking around online but all examples and explanations are very hard to understand and follow. Can you give a simple explanation for how such attacks happen?

The recently demonstrated attack against SSL (BEAST) was an IV misuse attack and not really the same thing as what happened to XML Encryption. Nonetheless, here is what happened with SSL.

Basically they found two things:

A way to get the browser to encrypt data under the session key used by an existing SSL connection and
A mistake in the way SSL was written that allowed that ability to be leveraged to read messages.

Let's says you are using AES with CBC mode. Encryption for the first block of a message is basically $AES(K, IV \oplus m)$. The IV is typically sent along with the ciphertext.  This is a simplification ignoring how longer messages are handled, see Wikipedia's CBC article for more details, but it works for this purpose.

The point of this is that multiple encryptions of the same thing don't result in the same cipher text because the IV is random and data XOR random = random, so you never actually encrypt the same message. Thus an attacker who can cause the browser to encrypt data can't simply guess at what the message was and verify that guess by causing the browser to encrypt the guess and checking if it matches the encrypted message they want to read.

Well the problem is, if I know the IV in advance, this no longer holds: If I want to guess that some previous message was "attack at dawn" (with IV $IV_1$) and I know the IV for the next message will be  $IV_2$, then I merely need to cause the browser to encrypt  a message $m$ such that  $IV_1 \oplus \text{"attack at dawn"} = IV_2 \oplus m$, and check if the ciphertext blocks match.

SSL used the last 128 bits of the previous encrypted message as the IV. Because there was time between when this message was sent and the next, the attacker could make a guess.

This is a basic overview, there still some details of how you do this efficiently to get the session cookie sent with each HTTP request, but that's the gist of it.

This attack is not possible with TLS 1.1 and 1.2 (as they generate a new initialization vector for each message), and the OpenSSL library worked around this problem already in TLS 1.0 by sending an empty message (i.e. only padding and MAC) directly before each real message, so the ciphertext of this empty message is used as initialization vector for the real one (and this is not predictable without knowing the key). (Edit: it turns out this feature is disabled in OpenSSL because it breaks large numbers of servers who assume a zero byte read  is an end of file. Instead, the deployed fix is "1/n-1 record splitting" where one byte is sent in a block and the rest of the message is in the next block)


The Wide Pipe construction I'm learning more about the Merkle–Damgård construction, including its "alternatives".

I think I know how the Wide Pipe construction works, but am confused about the different images being used online.

Wikipedia uses this one, which has two lines going through the compression function. However, this one, scroll down to "Alternatives to Merkle-Damgård" and this one, scroll down to "The Wide-Pipe Hash: A Modified MD Hash" use an image which has just 1 line going through.

Why do the images look that different? Is one or the other simply wrong, or is there something I'm missing?

If you're comfortable with the reasons for  alternative pipe construction I won't reiterate them.

Yes you're missing something, but it's not cryptographic.  It's just that informative artwork and graphic design is not the usual cryptographer's skill set.  So they bodge it as best they can.  So single lines can represent many things.  Sometimes they can mean a standard MD width of interim hash passing through, and sometimes they represent  twice the width.  The feature that gives it away is the finalisation function /output compression function.  If one of these exists, it suggests (graphically) that the interim hash width exceeds the input /output block widths and has to be reduced.

I understand your confusion.  Figure 3 of your The Wide-Pipe Hash: A Modified MD Hash seems to show yet another alternative type of wide pipe that you might call staggered.  This is my nomenclature for it as it's not specifically named, but I wouldn't call it standard wide pipe.  It seems to show iterated compression functions of input width IV + message and IV width output.  It's almost the fast wide pipe compression function mirrored.

The designers randomly try all sorts of weird stuff in order to improve the security of the total hash.  It's called incremental development and that's how things evolve.  So some of your examples are slightly different in form.  They just sometimes draw /explain it very badly but then they're not graphical artists.  Your wiki example doesn't name the wide pipe hash, so we don't know what the compression function is.  It is entirely possible that it keeps IV compression and message block compression entirely separate until finalisation.  But it's a clip art style image and not very detailed.  Between subtle variations on which bit is wider than the output block width and bad drawing, it's hard to figure it out.


Combined message separation? I have two ciphertexts, I suppose that its RC4 with reused key. I have XORed both ciphertexts and obtained message containing combined cleartexts.

I suppose that the underlaying messages are written in some structured format, but unfortuanatelly I do not know anything about frequencies (I might guess that there will be eg plenty of { }, if its json).

Most sources that I have read state that the separation is simple, but do not discuss the method to separate the texts. My idea was to use backtracking algorithm and try to construct both messages, so their sum (xor) matches the known combined text.

Is this the correct solution to this issue, or is there some smarter way?

Maarten appears to make it look like it's an impossible (or, at least, an exceedingly difficult task) to recover the two plaintexts.

Indeed, if you literally know nothing about the plaintexts, it can be difficult.  However, you typically have a reason you are interested in the messages, and hence often have a clue as to what language they might be.  If the language is 'random bits', or something else which is high entropy, it can be a difficult or impossible task.  However real plaintexts often don't fall into that category.  You mentioned that they might be json files; lets go with that.

One common trick that is useful in many languages is crib dragging; you pick an n-gram that is common in the language (for json, the 4-gram consisting of the characters ", :, space and " is one possibility), and xor in that in various places in the xor'ed plaintexts.  If one plaintext consists of that 4-gram in that spot, the result of the xor will be the contents of the other plaintext in that location.  Hence, if the result of the xor is a plausible plaintext, you might have successfully decoded both messages there (and can possibly extend the decode, if the other plaintext has obvious previous/next characters).

By using several such cribs, and by expanding revealed plaintexts when possible, my experience (with ASCII-encoded English) has found it to be a doable process -- I don't have any specific experience with json, however I would expect it to be doable as well.

I don't personally know of any tooling that would help you (I built my own tooling on the fly when I did it); however I wouldn't be surprised if something exists.  However, I would expect any such tooling would require some hand-holding (as people are more likely to judge correctly whether things are plausible or not).


Are there any practical implementation of a homomorphic hashing or signature scheme? A homomorphic hash function is a function $H : A \to B$ between two sets with some algebraic structure $(A, *)$ and $(B, \star)$ such that

$H$ is collision resistant, i.e. it is hard to find $x \neq y$ such that $H(x) = H(y)$ and
$H$ is a homomorphism, i.e. $H(x * y) = H(x) \star H(y)$.

Are there any practical realizations of such a homomorphic hash function, or even a homomorphic signature scheme (i.e., where we can "add" valid signatures to get a signature of the "sum" of two messages)?

Even better, are there even any libraries implementing this?

There's plenty of research in this area.  I'll give you just a small sampling:

Speeding Up Homomorpic Hashing Using GPUs. Kaiyong Zhao.  ICC 2009.
Transitive Signature Schemes. Silvio Micali, Ronald Rivest. CT-RSA 2002.
Homomorphic Signature Schemes. Robert Johnson, David Molnar, Dawn Song, David Wagner.  CT-RSA 2002.
Sanitizable Signatures. Giuseppe Ateniese, Daniel H. Chou, Breno de Medeiros, Gene Tsudik. ESORICS 2005.
Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.  Dan Boneh, David Freeman. PKC 2011.
Homomorphic Signatures for Polynomial Functions.  Dan Boneh, David Freeman. Eurocrypt 2011.
Homomorphic MACs: MAC-Based Integrity for Network Coding. Shweta Agrawal, Dan Boneh. ACNS 2009.
On Homomorphic Signatures for Network Coding.  A. Yun. IEEE Trans. Computers.

Like I said, this is only a small subset of the available research in this area.  I found most of these through about 5 minutes with Google Scholar.  I recommend you start by doing a literature review to familiarize yourself with the research literature on this subject: search to find as many relevant papers as possible; read each such paper; for each paper you find, read the related work section and bibliography to try to identify other relevant papers, and also use Google Scholar or other sites to find other papers that cite that paper that might be relevant; for each additional relevant paper you find, repeat the process.

After you have done this process, you should be in a better position to ask a more narrowly targeted question with a particular set of requirements -- or, if you're lucky, you might have found a solution to your particular problem already described in the literature!


ZKP of the validity of a decryption key without revealing the message in public Alice publicly shares encrypted message $E_k(m)$.
Alice publicly shares the key encrypted with Bob's public key $E_\mathit{bob}(k)$.
Alice wants to create a Zero-Knowledge Proof that this is indeed the key that unlocks $E_k(m)$ encrypted with Bob's public key, such that anyone can be convinced that Bob can now know the message $m$ by decrypting $E_k(m)$ without revealing any information about $m$ or Bob's private key.

Is this possible using cryptographic tools (ZKPs, SNARKS, hashes, etc...)?

You could solve the problem using a kind of cryptographic commitment, but it requires an additional message from Bob.

(I'm assuming $k$ is a symmetric key from the context of your post)

Alice picks another message, $m_2$, and posts $E_k(m_2)$ and $Hash(m_2)$, using a cryptographic hash function like SHA-256 or what you.

Once Bob gets $k$, he uses it to find $m_2$, and then reveals it. Anyone can check the validity of his $m_2$ by hashing it and checking against Alice's commitment.

Nothing is learned about $m$ unless the symmetric cipher itself leaks information.


LUKS: decrypting with master-key rather than with passphrase It's my understanding that LUKS encrypts data by using a randomly-generated master-key, which is then itself stored encrypted by my passphrase. When I want to access the data, I use my passphrase to decrypt the master-key, which is then used to decrypt the data.

Question:
Is it possible to have LUKS just encrypt the data by using the randomly-generated master-key (can I specify the size?), but then instead of encrypting this with my passphrase and storing it, just tell me the master-key (which I will memorize or write on a piece of paper). When I'll want to access the data, I will use the masterkey to decrypt it.

As a side note, let me explain why I think that this would be more secure than the usual procedure: when cryptographically sanitizing a USB or non self-encrypting SSD drive (or changing the LUKS password), it's my understanding that the master-key encrypted by the old password will always be physically present on the drive, because digital sanitization is hard to achieve for USB and SSD. The randomly-generated master-key would then be recoverable by either guessing the old password, or by brute-forcing it.

Normally, you don't provide the master key directly. The master key is protected by a key encryption key. All storage encryption systems work this way.

There is no way to change the master key without re-encrypting all the data. Using a master key that's stored in a form wrapped by a key encryption key allows changing the key encryption key without re-encrypting the data. It also allows having multiple key encryption keys.

You propose not using a key encryption key and using the master key directly. This is always weaker than using a key encryption key, unless the mechanism for processing the key encryption is flawed. In your proposal, you propose to remember the master key (128 bits or more). If the master key is ever compromised, you've lost. Instead, suppose that you remember a passphrase with as much entropy as the master key (a random passphrase chosen in a space of 128 bits or more). Then you are protected against all the attacks that you would be protected against if you'd remembered the master key, and more.

The attack you're concerned about is someone finding a copy of the master key encrypted with an old, weak passphrase. If you want to protect against this attack, don't use a weak passphrase! If you only use a strong passphrase then there won't be anything lying around that was made by a weak passphrase. Storing the master key encrypted with a passphrase that's as strong as the master key itself is not a risk. The passphrase can even be weaker because it goes through a strengthening function (PBKDF2 or Argon2).


Bit decomposing a polynomial in BGV cryptosystem I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a vector of polynomial in $R_q^n$, in particular, how the $u_j$'s are in $R_2^n$.

Does it assume that the polynomial is in coefficient representation? Can someone please give an example for $n=1$, and $n=2$?

To understand that, we have to understand how it works for a single polynomial (which means, for $n = 1$).

First of all, think about the binary decomposition of an integer value: given $m \in \mathbb Z_q$, it is always possible to write $m = \sum_{i=0}^{\log q} b_i 2^i$, with each $b_i$ in $\{0, 1\}$.

Now, just see that if you decompose each coefficient $a_i$ of a polynomial into the binary representation $\sum_{j=0}^{\log q} b_{j,i} 2^j$ , you get $\log q$ polynomials:

$\begin{align}
p(x) &= a_dx^d + a_{d-1}x^d_{d-1} + ... + a_1x + a_0\\
     &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^j \right)x^d + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j \right)x^{d-1} + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^j  \right)x^1 + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
    &= \left( \sum_{j=0}^{\log q} b_{j,d} 2^jx^d \right) + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j x^{d-1} \right) + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^jx^1  \right) + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
     &=  \sum_{j=0}^{\log q} \left(b_{j,d} 2^j x^d + b_{j,d-1} 2^j x^{d-1} + ... + b_{j,1} 2^j x^1 + b_{j,0} 2^j \right) \\
     &=  \sum_{j=0}^{\log q} \left(b_{j,d} x^d + b_{j,d-1} x^{d-1} + ... + b_{j,1} x^1 + b_{j,0} \right)  2^j \\
     &=  \sum_{j=0}^{\log q} u_j(x)2^j
\end{align}$

Therefore, what this BitDecomp function does when it receives a single polynomial is to return a vector with those $\log q$ polynomials $u_j$.

Thus, when given a vector with $n$ polynomials, it returns a vector with $n \cdot \log q$ polynomials.

Maybe this answer will be useful to you, since it is very related to your question ($Dec_{w,q}$ is a generalization of BitDecomp that uses a parameter $w$ to the base instead of fixing the value $2$).


How difficult is it to find the "pre-image" of a block cipher? Say that I have

$$ C_1 = AES_{k_1}(M_1) $$

How difficult would it be to find a key, K2 and plaintext M2

$$ C_2 = AES_{k_2}(M_2) $$

such that

$$ C_1 == C_2 $$

How would using a block cipher algorithm other than AES effect this problem?

Take $C_2$ and pick any $k_2$. Then decrypt using $k_2$ so that $M_2 = AES_{k_2}^{-1}(C_2)$. Now obviously we have $AES_{k_2}(M_2) = C_2 = C_1$.

This extends to any blockcipher, because blockciphers are specifically designed to be reversible.

In the comments you asked about the scenario where $M_2$ is also fixed. This is as hard as breaking AES. Consider this problem:

Find $k_2$ given $k_1, M_1, M_2$ such that:

$$AES_{k_1}(M_1) = AES_{k_2}(M_2)$$

Giving $k_1$ (and thereby $M_1$) does not add information for the solver to this problem, because there is no relation between $k_1$ and $k_2$ other than that there exists a ciphertext that was created using both keys - which is non-information because all keys can create such ciphertext given the correct plaintext. Thus the problem with irrelevant information removed becomes:

Find $k_2$ given $M_2$ such that:

$$C_2 = AES_{k_2}(M_2)$$

This is obviously the problem of breaking AES itself.


Questions about the Curve25519-donna implementation I'm trying to understand the implementation of the following function:
Please note questions in comments.

int curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
limb bp[5], x[5], z[5], zmone[5]; // why 5 elements in each?
uint8_t e[32];
int i;
for (i = 0;i < 32;++i) e[i] = secret[i];
e[0] &= 248;
e[31] &= 127;
e[31] |= 64;
fexpand(bp, basepoint);
cmult(x, z, e, bp);
crecip(zmone, z);
fmul(z, x, zmone);
fcontract(mypublic, z);
return 0;

}

Why do all the functions work on a polynomial form of a number? and thus require fexpand function? as I understand fcontract does the opposite.
e[0] &= 248;  e[31] &= 127; e[31] |= 64;  - I've found this suggested in the whitepaper, is there any particular reason behind doing this?
Why is cmult performed twice? what does crecip function achieve?

From what I read on curves in the Weierstrass form, in order to get a public key H, one needs to compute H = dG    (where G is the base point of the subgroup).
Then the situation is entirely different in case of Ed25519 (I know Montgomery Curve25519  is birationally equivalent to a twisted Edwards curve  Ed25519), where generation of the public key involves hashing and results in a non-linear key-space.

In contrast with Ed25519, Can private/public keys in Curve25519 be said to form a linear space? I was wondering whether it would be possible to generate public keys independently to the corresponding private keys using a common index in case of Curve25519.

Update: besides the excellent answer provided by Lery; those of you not familiar with projective coordinates might find this useful.

You have 5 limbs because it is based on DJB's papers and as the Ed25519 paper mentions, it's using a $2^{51}$ radix representation for performance reasons.

It does so in order to avoid carries when performing field multiplication. Because otherwise the carry bits need to be handled by subsequent additions, which slows down even modern CPUs.

So according to the paper, to reduce the number of expensive adc/subc instructions, they represent an element $x$ of $\mathbb{F}_{2^{255}−19}$ as $(x_0,x_1,x_2,x_3,x_4)$ with $x =\sum_{i=0}^{4} x_i 2^{51i}$.

So in the end the multiplication should be accepting inputs with each limb having up to 54 bits.

Working with polynomial form allows to efficiently perform computation modulo the field's order. It allows to simplify the code required to implement the different arithmetic operations and thus is more comfortable to work with. Polynomial form is the natural way to represent integers modulo something.

Now regarding the bit manipulations done on the secret key, they are done in order to convert (random) 32 bytes into integer scalar.

The bit manipulation are there to set the three
   least significant bits of the first byte and the most significant bit
   of the last to zero, set the second most significant bit of the last
   byte to 1.  This means that the
   resulting integer is of the form $2^{254}$ plus eight times a value
   between $0$ and $2^{251} - 1$ (inclusive).

Now, as for why they are performed, the lower three bits are cleared to prevent a small subgroups attack.
And now regarding the MSB, it is set to 1 in order to avoid timing leaks.

Regarding the reason for the presence of two multiplication cmul first and fmul next, that's because cmul is actually computing, for an integer $n$ and a point $V$ the value $Curve(nV)=x/z$, so we have that $z\cdot Curve(nV) = x$.

Since we don't want the x-coordinate of the resulting point in this short form $x/z$, we need to convert it into the actual x-coordinate value, hence the crecip and fmul calls.

Finally, yes you should be able to derive private key and public keys independently of each other à la BIP32.


What is the difference between security parameter and $b$-bit security? In a previous question, I read

... for $b$-bit security meaning $O(2^b)$ work for an attacker to break the system...

While in Katz's Introduction to modern Cryptography, I read:

The key-generation algorithm $\text{Gen}$ takes as input $1^n$ (i.e., the security parameter written in unary) and outputs a key $k$".

What is the difference between security parameter and $b$-bit security?
Edit: Can I have an example for the McEliece cryptosystem?

What is the difference between security parameter $1^n$ and $b$-bit security?

There's not one, but two:

A security parameter $1^n$ does not precisely specify how the attacker work grows with $n$. Depending on author and context, that can be: unspecified; faster than any polynomial in $n$ (common in asymmetric cryptography); exponential in $n$ (common in theoretical symmetric cryptography); or roughly¹ as $2^n$ (common in applied symmetric cryptography).
By contrast, "$b$-bit security" specifies that the work for attack grows roughly¹ as $2^b$, as it can in symmetric cryptography for attacks aiming at recovery of a $b$-bit key for an ideal cipher. The distinction is paramount in RSA, where $n$ most often is the bit size of the modulus, and $n=2048$ is believed to yield $b\approx112$.

When we consider algorithms running in time at most polynomial to the size of their input, as is customary in theoretical work: passing $1^n$ (meaning a bitstring consisting of $n$ bits at one) as input implies that the run time is polynomial in $n$, when passing $n$ would allow the run time to be a polynomial in $\log(n)$. Usually the former is desired in cryptography.
Whereas "$b$-bit security" says nothing about the run time.

¹ For some definition of roughly. Many, including me, often state that the expected attacker work is $O(2^b)$,. That's improper because that upper-bounds said work. We should at least  write $\Omega(2^b)$ or $\Theta(2^b)$; see this. I corrected that (minor and common) issue in my answer to the "previous question" mentioned.


How can I calculate the SHA-256 "midstate"? Recently I've been trying to implement some Bitcoin-related code, and I've stumbled upon a weird concept, a SHA-256 "midstate". Some explanation is given here.

The general concept is that Bitcoin relies on performing SHA hashing of a 128 byte data chunk many times, but only the second half of that chunk changes. This is why the concept of "midstate" is used. As I understand it, in order to perform SHA on 128 bytes of data, one needs to divide the hashing into operations on first and second 64 bytes of the data. As results of first hashing are constant, one would save them as this "midstate", and before hashing the changed second half of bytes, one would restore the "midstate" instead of calculating it again.

Can anyone explain how would I calculate this "midstate" having a library that calculates a whole SHA-256 hash, or alternatively which libraries support calculating of something like that?

SHA-256 uses an internal compression function $f$ which takes two inputs, of size 512 and 256 bits respectively, and outputs 256 bits. Hashing works like this:

Input message $M$ is first padded by appending between 129 and 640 bits (inclusive), resulting into a padded message $M'$ whose length (in bits) is a multiple of 512.
$M'$ is split into $n$ 512-bit blocks $M_1$, $M_2$,... $M_n$ (each block has length 64 bytes).
Set $X_0$ (a 256-bit value) to a conventional initial value (which is specified in the SHA-256 standard, section 5.3.3).
Process each block in due sequence, by computing $X_i = f(M_i, X_{i-1})$ for all $i$ from $1$ to $n$.
The hash value is $X_n$.

The $X_i$ values can be seen as the successive contents of a state variable $X$ (indeed, when you have computed $X_i$, you can discard $X_{i-1}$ since that value will not be used thereafter).

Your "midstate" is $X_1$: that's the contents of the "state" after having processed the first block. Since all your 128-byte messages begin with the exact same 64-byte header, all the hash computations formally begin by processing the same block $M_1$, with the same $X_0$ (the conventional initial value), resulting in the same $X_1 = f(M_1, X_0)$. You would like to "restart" each computation from that value $X_1$ directly, to avoid recomputing it again and again.

Doing that over an existing library implementing SHA-256 may or may not be easy, depending on what facilities that library offers. For a basic SHA-256 library, there are two possible issues:

The library may refuse to output $X_1$, because it would insist on computing hash values over a padded message only; you want to have the output of $f$ over a given $M_1$ block without padding.
The library may refuse to start a new computation starting with the $X_1$ you provide instead of the conventional initial value $X_0$.

Some libraries offer a bit more. For instance, consider sphlib. With that library, there are two ways to achieve what you seek:

The implementation works over a context structure (of type sph_sha256_context) which represents the current state. You can thus begin a computation by processing the header, and then clone the context to make many hash computations which start from that exact point. It would look like this:

sph_sha256_context sc;

sph_sha256_init(&sc);
sph_sha256(&sc, header, 64);
for (/* all 128-byte messages */) {
        sph_sha256_context sc2;
        unsigned char second_half[64];
        unsigned char out[32];

        /* set second_half[] to the second half of the 128-byte message */
        sc2 = sc;
        sph_sha256(&sc2, second_half, 64);
        sph_sha256_close(&sc2, out);
        /* SHA-256 output is in out[] */
}

sphlib offers an sph_sha256_comp() function which implements exactly the compression function $f$. You can use it to compute SHA-256 "manually", block by block, starting from any state value $X$ you wish. You would have to take care of encoding issues (SHA-256 is big-endian throughout, use sph_dec32be() and sph_enc32be() to do that properly and portably) and padding. If all your messages have length exactly 128 bytes, then padding is always a full 64-byte block, consisting in a byte of value 0x80, followed by 61 bytes of value 0x00, and then two bytes of value 0x04 0x00. Expressed in 16 32-bit words, first word has numerical value 0x80000000, followed by 14 words of value zero, then a final word of value 0x00000400.

For heavy hash crunching (I understand that's the point), your best bet is still probably to extract the inner loop from an opensource implementation, and integrate it directly in your code, so as to avoid any overhead from the library API. You also probably want to avoid heavy encoding/decoding, and work over 32-bit words directly (while SHA-256 takes as input a bit sequence, it soon converts it to a sequence of 32-bit words and works over that). I invite you to do your own SHA-256 implementation, working from the standard: it is not hard, that standard is reasonably clear, and it will grant you enough knowledge on how SHA-256 works to optimize your code (even if you end up reusing parts of some other implementation).


Is this a secure PRG? Suppose that we have a secure PRG $$G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$$

I want to construct a secure PRG $G'$ that when we select its seed $s \in \lbrace 0,1 \rbrace^n$ that $parity(s)=0$, it becomes insecure.

I construct this: $$G'(s||\operatorname{parity}(s)) = G(s)||\operatorname{parity}(s)$$

(where $\operatorname{parity}(s)$ is defined as XOR of all bits of $s$)

Intuitively, I think this is correct. Am I wrong? I couldn't prove it.

Parity alone is a hard-core predicate of a oneway function, with this example given in the wiki:

With $f$ a oneway function, define $g(x,r) = (f(x),r)$ with $|x|=|r|$. Clearly $g$ is oneway, too, and it's trivial to build an adversary for $f$ from an adversary for $g$ and vice versa. However, $g$ has a hard-core predicate:

$$b(x,r) := <x,r> = \bigoplus_j x_j r_j$$

If we fix $r$ as the all-$1$ input, we get exactly the parity function.

In a similar context in this question the answer of Thomas Pornin has an example where the parity of the input to a oneway trapdoor function is is used as a hardcore predicate.

Now, the difference here is that you have a PRG, with a different definition than oneway functions, but my intuition would be that this is actually a secure PRG (regardless of the input parity) - since one of the standard way to construct a PRG is based on using hardcore predicates. And in the input domain you just fix one bit of the input by calculating the last bit as parity of the others, that should not break the PRG definition.

Edit, here's a sketch for the security proof:

Let's assume you have a distinguisher for $G'$, and we want to build a distinguisher for $G$. We get a challenge $x$ of length $l(n)$, which is either $G(s)$ or a randomly chosen number (from the uniform distribution). Now, we run the distinguisher for $G'$ on the $x|1$ and on $x|0$. Running a poly time algorithm twice is still a poly time algorithm. Loosely speaking, a distinguisher guesses, whether a challenge is in the image of the PRG or not and then returns this guess - but of course any value in the image could also have been the randomly chosen number.

So if at least one of our distinguishers returns "this was generated by the PRG", then we also answer this - if $x|0$ is in the range of the function $G'$, then $x|1$ could be in the range as well or it might not be. For an actual proof you would want to estimate the actual advantages.


Is the following construction of a secure PRG is also a secure PRG? Given a secure PRG $G :\text{{0,1}}^n \rightarrow \text{{0,1}}^{2n}$, I've constructed the following PRG:
$$
G'(x) =
\begin{cases}
0^{2n} & \text{if x is palindrome;}\\
G(x) & \text{otherwise;}\\
\end{cases}
$$
My intuition is that $G'$ is secure because it's "predictable" only for negligible portion of the inputs, so I tried to write a formal reduction.
I tried showing that given an efficient distinguisher $D'$ for $G'$, I can construct an efficient distinguisher $D$ for $G$. The immediate issue I faced is that $D$ receives as input either a random string $r$ of length $2n$, or $G(s)$ for a random $s$ of length $n$, and In the later case I'm having trouble rearranging $G(s)$ to be "suitable" for $D'$. (which I'm using as a black box)
Is my intuition about $G'$ security correct? If so, what's the way of proving its' security?

Indeed, your intuition is perfectly correct and the distinguisher $D$ you're trying to build is basically $D'$ itself.
To see that this is the case, simply divide the experiment for $G'$ into two cases: either the chosen input is palindrome or it is not.
The first case occurs with negligible probability, so we can focus in the second case, but now it's easy since this case corresponds to the original experiment for $G$.

If you want to be formal, just keep in mind that
\begin{multline*}
\mathbb{P}\left[D'(G'(x)) = 1\right] = \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is palindrome}\right]\cdot\overbrace{\mathbb{P}\left[x\text{ is palindrome}\right]}^{\delta}
\\ + \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is not palindrome}\right]\cdot\underbrace{\mathbb{P}\left[x\text{ is not palindrome}\right]}_{1-\delta}
\end{multline*}
and
$$\mathbb{P}\left[D'(r) = 1\right] =
\delta\cdot\mathbb{P}\left[D'(r) = 1\right] + (1-\delta)\cdot\mathbb{P}\left[D'(r) = 1\right].$$
Now, when you take the difference
$$\begin{align*}
\left|\mathbb{P}\left[D'(G'(x)) = 1\right] - \mathbb{P}\left[D'(r) = 1\right]\right|
\end{align*}$$
try to associate terms appropriately and apply some straightforward inequalities to show this is negligible.


Ring Signature - paper/code difference in trying to solve inverse trapdoor function? There is a paper on ring signatures and a python implementation of it here.
The Step 4 in the paper describes $y_s = v =C_k,_v(y_1, y_2, ... y_r)$ for all $1 \leq i \leq r$ where $i \neq s$. The next step is to find a unique $x_s$ for the signer's computed $y_s$. This is done by solving $x_s = g_s^{-1}(y_s)$
However, in the python example, to find the unique $x_s$:
s,u = [None]*self.n,random.randint(0,self.q)

s[z] = self.g(v^u,self.k[z].d,self.k[z].n)

It looks like it's generating a random integer $u$ as though $x_s$= $u$, then XOR'ing it with $y_s$ found in step 4, and then it applies the inverse trapdoor function $g^{-1}()$.
Why does the paper's implementation seem different from the one in the code?
That is, why $x_s = g^{-1}(y_s)$  or  $x_s = g^{-1}(y_s \oplus x_s)$ ?

I'm taking some stuff from my relevant question at Rivest's ring signatures with hashes instead of symmetric encryption

Remarkably, Wikipedia's Python code does not use a symmetric encryption function ($E_k$, as in "How to leak a secret"), but a hash function ($\mathcal{H}$). Indeed, the encryption function does not need to be invertible, if we close the ring of the signature at the very last (take $v^\prime$ random, $m$ is the hashed plaintext):

$$
\mathcal{H'}(x) = \mathcal{H}(x||m)\\
v=\mathcal{H'}(y_{r} \oplus \mathcal{H'}(y_{r-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(v'))))\quad r-s\enspace\text{times}\\
h=\mathcal{H'}(y_{s} \oplus \mathcal{H'}(y_{s-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(y_1 \oplus v))))
$$

now notice that
$$
v'=y_s \oplus h \Leftrightarrow y_s=v'\oplus h\\
x_s=g_s^{-1}(y_s)
$$

which "closes" the ring.

  My question is, why is the paper's implementation seem different than the one in the code?

To answer this question, I think we can only guess (or ask the authors). My guess would be that the authors didn't think of this trick, or that they didn't find it interesting enough to mention the possibility.

In my opinion, solving $C_{k,v}(y_1,y_2,\dots,y_3)=v$ by inverting $E_k$ (i.e., $E_k^{-1}=D_k$) seems more natural that "closing" the ring at the very last.

In terms of security, I think it has no influence on the proof in HTLAS, since they already modelled $E_k$ as a random oracle (and $\mathcal{H}'$ would be one too). I posted a new question about the security of this substitution.

  That is, why $x_s = g^{-1}(y_s)$  or  $x_s = g^{-1}(y_s \oplus x_s)$ ?

Don't get fooled here; what they denote in the code as u is what HTLAS calls $v$, so the sole thing they actually do in that step is $x_s=g_s^{-1}(y_s) = g_s^{-1}(v'\oplus h)$ (in my notation above).

The code on that page is very illegible to say the least, and may get removed soon. For future reference, here is the version in Wikipedia's history.


Running Crypto on hardware -- e.g., AES in hardware I am trying to understand the difference between a crypto algorithm run in hardware from that run in software. From a previous post (see here: Difference between Hardware implemented algorithm and software implemented one?), I have a partial answer to the question. The answer is that running a crypto algorithm in software typically means that it is run on CPU or GPU while running a crypto algorithm in hardware means that it is run on FPGA or ASIC.

Here is my confusion: In both cases the algorithm is still passed as a set of instructions to the CPU, GPU, FPGA or ASIC. For me this means that the algorithm is compiled into a set of instructions that are passed to the underlying hardware (where hardware means CPU, GPU, ASIC or FPGA). So this means all four cases operate in exactly the same way-- which makes me wonder why some are called hard-ware-based and others are called soft-ware-based.

Would someone please clarify?

**This question is not a duplicate of the earlier question because I am looking for the operational differences between the two. To put it differently, lets say I have some data to encrypt. Can some one give me the step-by-step process from start to end of encryption for (1) the hardware case, and (2) the software case? I am not looking for the advantages and disadvantages of either; I am only looking for the differences in how they work.

The difference between "software-based" and "hardware-based" lies in economics.

From a formal, mathematical point of view, there is no qualitative difference: the algorithm takes some inputs (including a source of random bits, for randomized algorithms), and produces some output which is fully determined from the inputs. How exactly the output is produced from the input has no consequence at that level.

In practical terms, though, a new factor must be introduced, and it is of paramount importance: money. Whenever some application (here I am talking generically, not only of cryptography) is to be incarnated as a tangible system, this is done at some cost, both in building (chips, wiring, casing...) and in operating (power consumption, weight, size...). The builder will try to minimize the costs for a given performance target. Among the structural choices that can be made, a very fundamental one is to go either "software" or "hardware":

The software path is about using some general purpose chips, usually known as "CPU", that can implement a variety of behaviours through programmability: the CPU is a fixed circuit, but it can interpret instructions obtained from some memory storage. The CPU includes circuitry to perform a number of elementary, general purpose operations such as "adding two 32-bit integers".
The hardware path means building dedicated circuits for the task at hand, directly from transistors or elementary logical gates. The dedicated circuit will become an ASIC or an FPGA (the FPGA is like an ASIC that can be wiped and drawn again, which is nifty but increases power consumption and chip cost, while lowering the maximum operating frequency).

What is good in the software path is that general purpose CPU are a commodity produced in huge series, which makes individual prices quite low; making millions of the CPU also justifies, economically speaking, the use of finer engraving technologies, which again promote performance (higher operating frequency, lower power consumption). Moreover, the inherent versatility of a CPU allows reduction of the number of hardware pieces needed in a system, since a single CPU can perform a high number of functions.

What is bad in software is that the CPU is basically an interpreter for the operations to perform, and that is expensive. Compared to an equivalent circuit, for the same algorithm to implement, a CPU will mobilize orders of magnitude more transistors and/or clock cycles. Using a dedicated circuit may save a lot in that respect, or allow a substantial performance boost, or both, but at the cost of a much lowered versatility. Dedicated hardware also forfeits the economical benefits of huge production series; FPGA try to regain some of these benefits, but lose a bit on performance compared to ASIC.

So, for any given application, whether software or hardware is to be used depends on what the system is supposed to do. Normally, CPU are cheaper, except for very specialized applications where versatility is not really needed, and raw performance must be achieved (e.g. detectors in high-energy particle accelerators, that must process gigazillions of data each second; bitcoin miners, that need to compute SHA-256 all day long, and only SHA-256; pacemakers, that must reliably regulate the heart beat of a patient with as small energy consumption as possible).

This is the landscape. What does it mean for cryptographic algorithms? Cryptographers, when they design algorithms, do so generically, that is, without a specific application in mind. Well, really, they do have applications in mind, but they try to make their algorithms good for many applications. They recognize that the computing industry at large operates over the two main models, so they try to define algorithms that will be "performant" (fast, light, economical...) in either or both.

For a software-based algorithm, this means using the operations that are natively offered by CPU. An example of a software-based algorithm is the hash function SHA-256, which uses a lot of 32-bit integer additions.

An hardware-based algorithm will rather concentrate on operations that yield better dedicated circuits. The new SHA-3 function (aka "Keccak") is of that kind: it is built around bitwise logical combinations. For a CPU, a 32-bit ADD and a 32-bit XOR have the same cost: both are elementary operations that will be executed in the same time, with the same CPU resources. But when you go hardware, the two operations are quite different: the ADD requires many more transistors (because of the carry propagation) with a deeper circuit (again because of the carry propagation), so the XOR is cheaper (less transistors, so less silicon area), lighter in energy consumption, and faster (because of the shallower circuit). The consequence is that Keccak tends to be a hog in software but a screamer in hardware.

Of course, the full situation is complicated. There are many types of CPU, some of them (the GPU) being optimized for tasks that general-purpose CPU are traditionally bad at (in particular heavy parallelism). Some modern CPU now include circuits dedicated to some specific cryptographic algorithms (e.g. for AES encryption). Also, FPGA have some, let's say, inclinations toward CPU, in that they are reprogrammable, and some include CPU-like features (RAM blocks, or even embedded DSP/microcontrollers). This blurs the limits.

In fact, the notion of an algorithm being "for software" or "for hardware" must be understood as a broad design categorisation that describes more the initial intent of the cryptographer who produced the algorithm, than a cleanly defined, mathematical property. There are extreme cases, e.g. the former AES candidate RC6, which is purely software (it uses an integer multiplication, a very expensive operation in hardware, that just happens to be part of the panoply of most CPU because it is a very useful operation in many cases), and the old GSM phone encryption algorithm A5/1, which is extraordinarily efficient in hardware (can be done in less than 500 gates) and remarkably slow and cumbersome in software.

Most modern cryptographic designs try to be versatile, and while they are usually meant to be more software-friendly or more hardware-friendly, it is considered a good thing if they do not yield abysmal performance in either case. This is one of the reasons, maybe perhaps the main one, that made Rijndael the winner of the AES competition: while not extraordinarily performant on, say, a big PC, it was still decent on all envisioned software platforms and in dedicated hardware; ultimately, this allowed the inclusion of such dedicated hardware in modern lines of CPU.

An exception is password hashing functions, that purposely aim at being most efficient on the defender's platform (supposed to be a general-purpose PC, i.e. the epitome of software), and as slow and expensive as possible on dedicated hardware. The recent Password Hashing Competition revealed a number of candidates that try to achieve this goal either with extensive usage of RAM (a traditionally sore point in FPGA), or with heavy usage of multiplication (as in Makwa).


Reverse Encryption Algorithm from Decryption code I have the code for a decryption algorithm but I'm struggling to figure out how to reverse it into the original encryption code.

function write(x) {
    return x >= "0" && "9" >= x ? (x.charCodeAt(0) - 48) : (x >= "a") && "f" >= x ? (x.charCodeAt(0) - 87) : 0;
}

function ondata(input) {
    var DATA = "";
    var i = 0;
    for (; i < input.length; i += 2) {
        var diff = write(input[i]);
        var firstNum = write(input[i + 1]);
        val = 16 * diff + firstNum ^ [31, 126, 188, 168, 210, 3, 208, 219, 229, 149, 187, 222, 17, 31, 59, 100, 131, 62, 163, 81, 115, 154, 2, 220, 166, 30, 112, 192, 48, 172, 174, 119, 249, 5, 251, 41, 46, 148, 43, 210, 35, 42, 231, 145, 16, 6, 10, 28, 228, 49, 103, 248, 151, 109, 19, 20, 151, 243, 12, 193, 152, 126, 83, 235, 27, 109, 66, 96, 179, 88, 11, 189, 30, 187, 23, 172, 93, 109, 239, 247, 123, 105, 55, 98, 117, 175, 114, 212, 146, 136, 38, 115, 124, 39][i / 2];
        DATA += String.fromCharCode(val);
    }
    return DATA;
}

ondata("6c0adddaa66abebc"); // 'starting' (javascript)

As shown, the string 6c0adddaa66abebc produces the output starting. My initial thought was to take the character code of each input character, but I wasn't sure what do to then. I'm sure it's just simple algebra but an explanation or a point in the right direction would be great, I'd like to learn from this.

UPDATE:

Ilmari Karonen's post gave me the help I needed to understand this. The problem I had was that I didn't actually understand what the long val = 16 * ... line was doing. His refactored code and explanation helped me to understand the process. Here's how I came up with the solution if anybody's interested in the thought process:

I knew I had to reverse the function, like in algebra. So logically, I started with finding the character code of each letter in the starting string:

var x = value.charCodeAt(i);

Now, I had to "undo" the xor applied, which obviously (not to me) was just the xor function with the same key:

x ^= key[i];

Then, I had to undo the conversion of the hex string to a decimal number, which was just converting the decimal to a hex number:

var hex = x.toString(16);

I also had to add padded zero's to the hex number, because the decoder worked in pairs of two.

if (hex.length < 2) hex = '0' + hex;

Final solution:

function parse(value)
{
    var result = "";

    for (var i = 0; i < value.length; i++)
    {
        var x = value.charCodeAt(i);
        x ^= key[i];

        var hex = x.toString(16);
        if(hex.length < 2)
          hex = '0' + hex;
        result += hex;
    }
    return result;
}

First of all, the write() function does nothing but decode a single hexadecimal digit into a number from 0 to 15.  You could replace it with:

function write(x) {
    return parseInt(x, 16);
}

Thus, the code:

var diff = write(input[i]);
var firstNum = write(input[i + 1]);

takes two consecutive hex digits from the input string and decodes them.  The expression 16 * diff + firstNum then just multiplies the first digit by 16 and adds it to the second one, giving you an 8-bit number from 0 to 255.  (In fact, since parseInt() can handle multi-digit numbers, you could replace all that code with just parseInt(input.substr(i, 2)).)

Next, the 8-bit number we just decoded is XORed with the value of this long expression:

[31, 126, 188, 168, 210, 3, 208, 219, 229, 149, 187, 222, 17, 31, 59, 100, 131, 62, 163, 81, 115, 154, 2, 220, 166, 30, 112, 192, 48, 172, 174, 119, 249, 5, 251, 41, 46, 148, 43, 210, 35, 42, 231, 145, 16, 6, 10, 28, 228, 49, 103, 248, 151, 109, 19, 20, 151, 243, 12, 193, 152, 126, 83, 235, 27, 109, 66, 96, 179, 88, 11, 189, 30, 187, 23, 172, 93, 109, 239, 247, 123, 105, 55, 98, 117, 175, 114, 212, 146, 136, 38, 115, 124, 39][i / 2]

Scrolling to the end, you can see that it's just a long array literal indexed by i / 2.  Since i counts hex digits from the start of the input and is incremented by 2 per iteration, i / 2 is simply counting the number of bytes output so far.  Thus, each byte of the decoded string is XORed with a different number from this fixed array.

(If the index i / 2 points past the end of the key array, the resulting key byte will be undefined, which gets converted to zero when it's XORed with the decoded byte.  Thus, in effect, for long inputs this code behaves as if the key array was padded with zeros.)

Finally, the resulting 8-bit number is just passed to String.fromCharCode(), which converts it into an ASCII (or ISO Latin 1) character, which then gets appended to the output string.

Thus, this code just decodes the input from hexadecimal into a byte string, and then XORs the bytes with a fixed key.  Now can you reverse it?

Ps. Here's how I'd rewrite the decoder:

var key = [31, 126, 188, 168, 210, 3, 208, 219, 229, 149, 187, 222, 17, 31, 59, 100, 131, 62, 163, 81, 115, 154, 2, 220, 166, 30, 112, 192, 48, 172, 174, 119, 249, 5, 251, 41, 46, 148, 43, 210, 35, 42, 231, 145, 16, 6, 10, 28, 228, 49, 103, 248, 151, 109, 19, 20, 151, 243, 12, 193, 152, 126, 83, 235, 27, 109, 66, 96, 179, 88, 11, 189, 30, 187, 23, 172, 93, 109, 239, 247, 123, 105, 55, 98, 117, 175, 114, 212, 146, 136, 38, 115, 124, 39];

function decode(hex) {
    var len = hex.length / 2, bytes = [];

    // decode input hex string into array of bytes:
    for (var i = 0; i < len; i++) {
        bytes[i] = parseInt(hex.substr(2*i, 2), 16);
    }

    // XOR each decoded byte with the corresponding key byte:
    for (var i = 0; i < len; i++) {
        bytes[i] ^= key[i];
    }

    // convert the byte array into a string and return it:
    return String.fromCharCode.apply(null, bytes);
}

You can check that this gives the same results as your original code, but it's hopefully more readable, and also possibly a bit faster (not that speed really matters for such short strings).


Zero-knowledge proof with only a ciphertext Suppose there is a plaintext p, which is encrypted with a symmetric cipher using a key k, resulting in a ciphertext c. Bob knows both c and k, but Alice knows only c. Is there any protocol by which Alice can be certain (maybe with some probability) that Bob indeed does know p, without revealing to her p itself?

Also, it be great to not have to have any third-party involved.

Yes, this is possible: every statement in NP can be proven in zero-knowledge, meaning, without revealing anything more than the very fact that the statement is true. In fact, this result can be extended to proofs of knowledge, where the prover does not only show that a statement is true, but also that he does know a witness (still without revealing it).

Of course, general techniques are very inefficient. For standard symmetric ciphers, the best approaches will use general zero-knowledge proofs for statements represented by boolean circuit - see my answer to the question that AleksanderRas links to in the comment section. You should also note that if you replace the symmetric cipher by a cipher with a strong algebraic structure, such as ElGamal, then much (much) more efficient solutions exist - for example, in ElGamal, proving knowledge of a plaintext requires only exchanging a few string (about twice more communication than simply sending the ciphertext - so really not much).