Optimized modular multiplicative inverse for Bitcoin (secp256k1) I have written an application to brute-force attack Bitcoin addresses for OpenCL. It implements a simple exhaustive search starting from public key G (private key 1) and point increment (addition of G) to get next key.

It works, but its performance is one order of magnitude slower than its CPU implementation using GMP (same point increment algorithm but with GMP routines instead of custom ones). On GMP implementation, hashing is the bottleneck. On OpenCL implementation, point increment is the bottleneck.

My point increment implementation uses modular multiplicative inverse via binary extended GCD (algorithm 14.61 of Handbook of Applied Cryptography). It is one order of magnitude slower than GMP implementation using mpz_invert().

What I need is an optimized point increment (point addition with G) optimized for curve secp256k1. This is an educational project, so my knowledge about the subject is limited. I don't know if there is a way to accomplish it without using modular multiplicative inverse or if there is a way to speed up this calculation for my particular application.

I saw and implementation (by Segher Boessenkool) using modular exponentiation with precomputed values, but there was no information on how to get those values for other curves. I failed to replicate GMP implementation. Its source code is huge and a mess of mixed optimized C and assembly code impossible to understand for me.

Requirements:

A fast point addition by G implementation.
Safety is irrelevant due to its use.
If possible, optimized for curve secp256k1.
If possible, precompute as much as possible.

Question:

How can I improve speed of elliptic curve point addition in my specific case?

Notes on comments:

The search is sequential inside each OpenCL kernel, but parallel considering the whole program. My worksize is optimized experimentally, getting close to theoretical GPU FLOPS performing SHA-256 only, so the bottleneck is not in OpenCL usage, but algorithmic implementation of elliptic curve cryptography.
The performance one order of magnitude smaller I am talking about is measured on CPU, not GPU. I get about 30 kKeys/s with my own modular multiplicative inverse and 200 kKeys/s (a laptop) with GMP. On GPU I get about 2 MKeys/s. Computing unoptimized SHA-256+RIPEMD-160 hash only, without point addition, I get about 1 GHashes/s (AMD Radeon RX 580).
Main program computes an array of public keys using scalar multiplication. It can compute them pseudo-randomly or equally spaced. This array is feed to the OpenCL kernel, and each instance computes RIPEMD160(SHA256(P)) == TARGET, RIPEMD160(SHA256(P+G)) == TARGET, RIPEMD160(SHA256(P+2G)) == TARGET, ... For now, there is only a single target address.
OpenCL is not the issue here. Profiling on CPU reveals that 90% of the time is expend computing modular multiplicative inverse. Same algorithm with GMP mpz_invert() uses only 25% of the time to do same step, using the remaining time on hash computation.

Half-extended binary GCD

The extended binary GCD of the HAC's algorithm 14.61 mentioned in the question, when given positive integers $x$ and $y$ , computes integers $a$ , $b$ , $v$ with $ax+by=v=\gcd(x,y)$ . When $v=1$, it follows that $a$ is the multiplicative inverse of $x$ .

In our context, $0<x<y$, $y$ odd, $\gcd(x,y)=1$ (the last two conditions are met since $y$ is $p=2^{256}-2^{32}-977$ of secp256k1$v=1$ , which is prime); thus $a$ is always the inverse. Importantly, we do not need $b$ , which allows simplifications. This leads to the half-extended binary GCD, which I hope can help to some degree:

If $x$ is odd then $u\gets x$ ; else $u\gets x+y$ ;
$v\gets y$ ; $a\gets0$ ; $d\gets 1$ ;   [or $d\gets y-1$ in unsigned variant, see note]
While $v\ne1$
[invariant here and at start of the next while loop: $u$ and $v$ are odd and distinct]

While $v<u$

$u\gets u-v$ ; $d\gets d-a$ ;   [or $d\gets d+a$ in unsigned variant, see note]
While $u$ is even (that's at least once)

If $d$ is odd then $d\gets d+y$ ;
$u\gets u/2$ ; $d\gets d/2$ ;

$v\gets v-u$ ; $a\gets a-d$ ;   [or $a\gets a+d$ in unsigned variant, see note]
While $v$ is even (that's at least once)

If $a$ is odd then $a\gets a+y$ ;
$v\gets v/2$ ; $a\gets a/2$ ;

$a\gets a\bmod y$ ; that's the desired inverse.

Note: As shown, $a$ and $d$ are signed. In an unsigned variant we can keep them non-negative, by making the three changes noted.

As shown, $a$ and $d$ can grow to several times $y$ (in absolute value for the signed variant). We can devote some extra bits to this. I conjecture without proof that $\max(|a|,|d|)<4y\log_2(y)$ (or $\max(a,d)<8y\log_2(y)$ for the unsigned variant). Alternatively, we can change $a\gets a+y$ into $a\gets a-y$ when $a\ge0$ for the signed variant (for the unsigned one, that can be when $a\ge y'$ for some convenient $y'\ge y$, e.g. $y=2^{256}$ ); and same for $d\gets d-y$ . This is enough to ensure everything stays below $4y'$, or $2^{258}$ in the context.

Possible optimization: the number of times $i$ that the "While $u$ is even" loop is run is predictable from the low-order bits of $u$, and we can group the overall effect on $u$ and $d$ into a single loop. What needs to be added to $d$ depends on $i$, the $i$ low-order bits of $d$, and $y$ . It can be precomputed since $y$ is fixed. Even if we do this for $i$ up to 2 or 3 only (then iterate if necessary), that saves significantly (on a classical CPU at least). Same for $v$ and $a$.

The (half)-extend Euclidean algorithm (see this answer) also computes the multiplicative inverse, and has a simple variant avoiding multiplication (the quotient is made a power of two). It can be competitive. The two can be blended.

GPUs are best at SIMD workloads

GPUs shine at workloads where the same instruction flow applies to different independent jobs launched in parallel. Taking different code paths in simultaneously launched jobs at best dramatically reduces performance. Thus GPU-friendly algorithms are those with long sequences without tests, and tests which predictably mostly take the same path in different jobs. Algorithms often need to be tweaked towards that.

[hopefully more to come there]

It's a brute force attack

The attack require about $2^{b-1}$ point addition to find a private key with $b$ unknown bits, or about $256-b$ known bits (e.g. at zero). I see no reason why there should be such keys, other than deliberately. Thus I'm doubtful on the overall usefulness of the thing. We can still think about it for educational purposes.

Starting from addresses forces using Cartesian coordinates

Because a version of the attack is said to be hash-bound, we know that the attack tries to find a private key from the hash (known as address) of the corresponding public key, rather than from the public key. This has been confirmed in comments of that other answer, which proposes a mathematical technique assuming the public key is known. I'm not exploring that avenue.

Thus, the bulk of the sequential version of the algorithm is to compute public keys $kG$ for incremental private key $k$ using point addition of $G$ to move from one public key to the other; hash the resulting public key (essentially) in its Cartesian uncompressed $X\|Y$ form; and check the hash.

The attack should be multi-target

There is a tremendous potential benefit in targeting multiple addresses simultaneously; only the comparison of the final hash is made slightly more compute intensive (it becomes a search among the addresses targeted), and all the rest is shared. That's too good to ignore.

Outer loop for GPU (it's fine)

When optimizing an algorithm for GPU or other highly parallel architecture, it is essential to split the task into independent jobs. That part of the question made me think it was not done:

  search starting from public key G (private key 1) and point increment (addition of G) to get next key

With this algorithm, the overall search speed would not scale up with more GPU power: point increment is going to be a bottleneck no matter how optimized it is.

But the question now also has:

  Main program computes an array of public keys using scalar multiplication.

and that suggests "starting from public key G (private key 1)" does not apply to the OpenCL jobs/kernels. Instead, the private key search interval is subdivided, the corresponding public key computed, and the search performed; that's fine.


Is there any way to save Email encrypted in Database and used as normal later? I have a senario like
" I want to save a email (like  foo@bar.com) encrypted in Database (For example as 'asdjasjdna')  after that I want to check when User enter this email and compare in database.
Till now findings :

I can't lookup in database using that email directly
I can't convert incoming email to existing encryption as it changes every time depending upon timestamp.

So am I going right ? Is there anyway or workaround ? kindly guide any suggestion would be highly appreciated

It looks like it is asked for deterministic symmetric encryption (and authenticated, because we can and should) in a decisively applied context. There are options for this, including some that can be built easily on top of primitives available now in most cryptographic libraries.
One would be: after normalizing the email (which is a difficult task of its own), build an IV from it using some MAC (HMAC-SHA-512 truncated to 128-bit will do¹), then AES-CBC² encrypt the email using that IV. In theory you need separate keys for the MAC and encryption, but with the stated algorithms disaster won't strike if you don't. Store the concatenation of IV and ciphertext with Base64 encoding in the database.
Decryption is just as normal for AES-CBC, and after decryption you can check the MAC.
Since the encryption is deterministic, you can search by encrypting again and searching the ciphertext (case sensitive).
That solves the problems of search, and protects in case of database leak only slightly³ poorly than normal encryption. But is does not solve two wider IT security issue:

securely storing the key(s)
preventing their abuse

Note: I have asked here if AES-GCM-SIV with fixed public IV would do.

¹ Using HMAC-SHA-256 could be less than academically correct for more than 128-bit key, but would most likely be OK in practice.
² With some standard padding like PKCS#7. AES-OFB would simplify padding, but is uncommon. AES-CTR would simplify padding too, and is common, but it's uncommon that a 128-bit IV can be used and that would be a problem here.
³ In the context, the loss of security due to use of deterministic encryption is that it allows comparison of emails in database dump(s), including between different users in the database, and between revisions including if a user changed email then went back to the original.


NIST random test suite choosing bitstream length and count I am trying to use the statistical test suite software from NIST SP800-2.
First it asks for bitstream length.
Usage: ./assess <stream length>
   <stream length> is the length of the individual bit stream(s) to be processed

After file is given to program, it asks for;
How many bitstreams?

How can I determine that values? Let's say I have 1000000 32-bit ASCII sequence of 0s and 1s in a file like;
01111111000111000110010001111010
.
.
.
00110100001001100010111100000011

Which values will be appropriate for this?

Look for the document "NIST Randomness Testing SP800-22b.pdf" (or more recent updates if available) in the NIST website.

My guess is that your sequences are way too short (32 bits long) and no kind of statistical convergence can be expected to occur, which is necessary for the test to work. I presume this may be the reason why you get the error message.

The section "sequence length", p.102 in the NIST document states:

  The determination as to how long sequences should be taken for the
  purposes of statistical testing is difficult to address. If one
  examines the FIPS 140-1 statistical tests, it is evident that
  sequences should be about 20,000 bits long.

Coupled with this, you have 1 million such outputs. Depending on the conditions of how these outputs were obtained, you may want to concatenate them into longer outputs, in some principled manner.


AES CTR with a non random and predictable nonce? after reading a lot of stuff about AES CTR and its IV i'm still not sure if it is ok to use a predictable IV or not.

I searched the web and found some programs / devices that use encryption in this way.

For example Lora. Lora is a low speed Network for exchanging data
(temperatures or humidity sensors ) over a complete cities with thousands of devices.

Example:
I've found source code of the Lora Mac on the Web which is doing exactly that.

A Sequence counter that uses every value only once over the entire Node lifetime.

And a little 1 Byte counter for every new 16 Byte Block.

The IV is Initialized by

static uint8_t aBlock[] = { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
                            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

after this

    aBlock[5] = dir;           ( direction of message)
    aBlock[6] = ( address ) & 0xFF; (Hardware address of device)
    aBlock[7] = ( address >> 8 ) & 0xFF; (Hardware address of device)
    aBlock[8] = ( address >> 16 ) & 0xFF; (Hardware address of device)
    aBlock[9] = ( address >> 24 ) & 0xFF; (Hardware address of device)
    aBlock[10] = ( sequenceCounter ) & 0xFF; (counter that never repeats)
    aBlock[11] = ( sequenceCounter >> 8 ) & 0xFF; (counter that never repeats)
    aBlock[12] = ( sequenceCounter >> 16 ) & 0xFF; (counter that never repeats)
    aBlock[13] = ( sequenceCounter >> 24 ) & 0xFF; (counter that never repeats)
    aBlock[15] = ( ( ctr ) & 0xFF );  ( a counter value that is incremented for every 16 Byte Block)

Is this secure enough?

Source Code:
https://github.com/Lora-net/LoRaMac-node/blob/master/src/mac/LoRaMacCrypto.c
Line 108: void LoRaMacPayloadEncrypt()

http://www.semtech.com/wireless-rf/internet-of-things/

For CTR mode, a random IV is not needed. The only requirement be that the counter be unique in each block over all encryptions. (This is in contrast to CBC mode where unpredictability of the IV is essential.)


What order should these HTTPS ciphers go in to maximize security? I want to set up a very secure-from-MITM-attacks server. I have these algorithms enabled in my nginx and I'm getting an A+ on ssllabs.com but it's complaining that my cipher strength isn't 100% and that my key exchange isn't either. Even if reordering these won't improve it, I still would like to sort them by security level.

TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256  ECDH secp256r1  FS 128
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384  ECDH secp256r1  FS 256
TLS_DHE_RSA_WITH_AES_128_GCM_SHA256    DH 4096 bits    FS 128
TLS_DHE_RSA_WITH_AES_256_GCM_SHA384    DH 4096 bits    FS 256
TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256  ECDH secp256r1  FS 128
TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA     ECDH secp256r1  FS 128
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384  ECDH secp256r1  FS 256
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA     ECDH secp256r1  FS 256
TLS_DHE_RSA_WITH_AES_128_CBC_SHA256    DH 4096 bits    FS 128
TLS_DHE_RSA_WITH_AES_128_CBC_SHA       DH 4096 bits    FS 128
TLS_DHE_RSA_WITH_AES_256_CBC_SHA256    DH 4096 bits    FS 256
TLS_DHE_RSA_WITH_AES_256_CBC_SHA       DH 4096 bits    FS 256

If there is another change I need to make to fix my nginx setup I'm interested in learning that as well.

In short, don't bother getting 100 in "Cipher Strength" or "Key Exchange".

It is possible to get 100 in "cipher strength" by only allowing 256-bit ciphers, however, this will break compatibility with considerable amount of clients, slow down your server and have no security benefits. You can also get 100 in "key exchange" by only using >=4096-bit RSA or >=384-bit ECDSA certificate, as well as only allowing >=4096-bit DH or >=384-bit ECDH key exchange. I personally don't recommend it either for the same reason above.

There are some real things to do to improve security. If you are using OpenSSL 1.0.2 or lower, upgrade to 1.1.0 or higher, turn on ChaCha20 cipher and X25519 key exchange. Use 2048 or 3072-bit RSA and 256-bit ECDSA certificate in parallel if possible, and replace your DH parameter to match the length of your certificate key instead of 4096-bit.

The official document for NGINX SSL configuration:
https://nginx.org/en/docs/http/ngx_http_ssl_module.html

By the way, SSL Labs will use a new letter-grade marking scheme and fully deprecate the numeric ones (https://blog.qualys.com/ssllabs/2017/06/30/ssl-labs-grading-redesign-preview-1). Therefore, in the future, getting a 100 will no longer make a difference.

Good luck!


I don't care about replay attacks. What should I do with the nonce in nacl? My system forwards encrypted and/or signed messages on a gossip network. Replay is part of the design. What should I do with the nonce? I'm tempted to just set it to the same number always. Is this a bad idea?

Nonces must be unique but are not secret. Typically you send it alongside the ciphertext as a prefix. Note that with the asymmetric box, you must not use a nonce that you used in one direction in the opposite direction, since both directions use the same shared symmetric key.

Reusing a nonce is a fatal mistake. It completely breaks the MAC and it leaks the xor of the two plaintexts. This leak is quite severe, if for example both texts are natural language this allows recovery of most words of the messages.

Using a counter or a random value of at least 128 bits are common approaches to generate nonces.


Rogue CA Certificate MD5 Collision Control Papers from Marc Stevens et al show that X509 certificates that rely on MD5 signatures can break the assumed security model, that is, it allows for a forged certificate to have the same signature as a trusted cert, see https://marc-stevens.nl/research for these papers.  Both methods require the "to be signed" portion of the certificate to be known in order for the collision search to begin. Both require some "control" over the CA, whether it is by setting a fake CA or correctly predicting the validity and serial fields.

My question is why is this necessary? I understand that I need to know the to be signed parts, but why can't I just get this information from an already generated cert? I must be missing something simple about how these certs are constructed.

The reason for this is because it is impossible to generate an MD5 for just any $y$, where $y$ is the output of any $x$ that isn't pre-computed. MD5 is broken but it is not completely broken. Using the common terms, MD5 is broken with regards to collision attacks, but not broken with regards to pre-image attacks.

So your assumption that "Both methods require the "to be signed" portion of the certificate to be known" is not strong enough; a block (or two) in the to-be-signed portion should be pre-computed.

The to be signed portion is usually send to the CA in a certificate request. The CA uses the information in the certificate request and creates and signs the certificate that contains the information from the certificate request. This is usually automated, so if you can get past some filters you will be send the resulting certificate. At this point you can create a certificate that contains different information by altering the pre-computed block to create the correct MD5. Because the MD5 hash doesn't change the signature remains valid.

So the attack that's most potent is to pre-generate a certificate request for *.kzs8wf.com and a certain crafted public key forming the pre-computed block. You then receive the resulting certificate and then modify it to a *.google.com certificate with an re-calculated public key forming the altered pre-computed block.


Algebraic Variants of NTRU There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, which is over group rings; there is NTRU over quaternions, and octonions, and even sedenions; and there are various other non-commutative and non-associative schemes. I am aware that non-commutativity helps avoid an attack of Coppersmith and Shamir, but my question is the following: are any of these variants considered essentially superior to standard NTRUEncrypt? Is the more exotic algebraic structure of these variants considered preferable by experts, or are these schemes academically interesting but impractical/not trusted for real world use?

If one expands the discussion to include LWE-type schemes, isn't Module-LWE naturally a "non-commutative" hardness assumption which has practical applications? For example, the Kyber NIST PQC candidate is an MLWE scheme, and is a round 3 finalist.
In general though, I mostly see lattices over "exotic" (at least more so than things like RLWE/MLWE) algebraic structures discussed by coding theorists (two specific examples are Fredrique Oggier and Cong Ling). As there seems to be a larger theoretical basis of research on "that side" of things, it might be easier to search for practical applications.


What is the fastest integer factorization to break RSA? I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.

And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.

Which of these is actually right?

The IEEE paper is silly.

The factorization method they give is quite slow, except for rare cases.  For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...


Explanation of Proof-of-Encryption Regarding the question  Provable Encryption,
I'm trying to understand how a 'proof of encryption' might actually work.

What I can deduce from the answers is this: we need a cryptographic scheme that is somewhat homomorphic, in the sense that some algebraic structure on the set of plaintext is respected by the encryption transformation (like RSA and Rabin (plain $x^2$ version) respect multiplication in the underlying finite rings).

Can someone explain this in more detail? How can it be used to decide whether or not a given string is actually the ciphertext of something w.r.t. to a given public key?

I mean, in a sense all elements of the underlying finite field (or lattice or whatever algebraic structure the scheme is based on) are ciphertexts of something, right?

Not all encryption schemes have the property that all strings are ciphertexts of something. For instance, if you created a version of RSA where you added an extra 0 at the end of every ciphertext, this would still be a valid encryption scheme, but any ciphertext with a 1 at the end would not be an encryption of anything.

In a public-key cryptosystem, to prove that a ciphertext is an encryption of something, you can prove that you have some plaintext $x$ such that $Enc_k(x)=y$ where $k$ is the public key and $y$ is the ciphertext.

There are generic techniques which allow you to create proofs of arbitrary computable statements, namely that you know some value $x$ such that $f(x) = y$. There are also generic techniques that allow you to do this in a non-interactive way. By definition, these techniques reveal nothing about $x$ except that it satisfies the given statement.

Note: For certain functions, we know of more efficient ways to do zero knowledge proofs. Some answers in the question you posted refer to some more efficient ways of doing this in the case of public key cryptosystems. But for any computable function there is always some way of making a zero-knowledge proof using generic techniques.

EDIT

I don't really understand how the generic protocols work under the hood, but I do understand the following:

First, you can represent the function as a circuit. As long as you have bounds on how long a function will take to do this (e.g. the max number of iterations of a for loop), you can always represent a function this way. (May not be very efficient though.)
Then you convert the circuit into a list of constraints that need to be satisfied. This article by Vitalik Buterin has, among other things, a good explanation of how this step is done.
Finally, there are tools such as libsnark that, given a set of constraints and a correct input provide a way to generate a Short Non-Interactive Argument of Knowledge (SNARK) that the constraints were satisfied. This is the part where I don't understand how it works.

By Non-interactive, it means that once the person encrypting has generated a SNARK, $\pi$ that they know the plaintext to a ciphertext $y$ and has sent this proof to the verifier, no more interaction is needed. Since no interaction is needed, anyone who gets access to $\pi$ and $y$ can verify that $y$ is an encryption of something.


What is a permutation in Keccak? I am trying to understand Ethereum's hash algorithm Keccak. Keccak uses permutations in the hashing process. Could anyone explain me what this permutation looks like or how it works ? I only know permutation from mathematics, is it the same here?
A permutation of "abc" is: abc, acb, cab, bac, bca, cba
Is the same logic applied in Keccak?

I only know permutation from mathematics, is it the same here? A permutation of "abc" is: abc, acb, cab, bac, bca, cba Is the same logic applied in Keccak?

It's a slightly different sense of the word permutation that's in play here.  The initial sentence of the Wikipedia entry touches on this:

  In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.

In your example, the set is $\{a, b, c\}$, and it's already ordered as $abc$, so those other strings are permutations of the set and the string.

In cryptography when we talk about permutations, normally we're talking about sets of binary strings of some fixed length (notation: $\{0,1\}^n$) and a permutation is a bijective function with that set as both domain and codomain.  This is the same sense in which the term is used in abstract algebra:

  In algebra and particularly in group theory, a permutation of a set $S$ is defined as a bijection from $S$ to itself. That is, it is a function from $S$ to $S$ for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of $S$ in which each element $s$ is replaced by the corresponding $f(s)$.

Or, since the elements of a set $\{0,1\}^n$ can be read as numerals, you can read that as a providing an implicit, canonical ordering of the set, where the first element is the numeral for zero, the second element is the numeral for one, and so on.  And in that setting a permutation can be written as a nonrepeating sequence of all the numerals in the set, such that the $i$th element in the set's canonical ordering is substituted with the $i$th element of the sequence that denotes the permutation.

So the specification for Keccak defines certain permutations that are just some standardized functions over binary strings of a fixed length (which the specification defines for several lengths, but the most common is for 1600-bit strings).  These functions are designed to behave as much as possible like a permutation chosen at random from the set of all possible permutations of the same set, but to be efficiently computable.  But one way to reason about how Keccak works is to pretend like the permutation really is a randomly chosen one.  Again, if we think of the bit strings in the set that the Keccak permutation operates on as binary numerals, what the function does is, given any one of these as input, compute the position it would occupy in the randomly shuffled set.


What is adversary's advantage in cryptography and why we use it? The definition of adversary's advantage seems a bit odd for me and I am wondering why do we use it to measure the power of an adversary rather than just use the probability of a PPT adversary succeeding in answering an computationally hard question?

We begin with the probability $p$ of an adversary answering correctly.

For many problems in cryptography, such as factoring or computing discrete logarithms, finding a secret key or decrypting a plaintext, this is useful measure of how good the adversary is. If we have an adversary that can compute discrete logarithms with significant probability, that is obviously a problem.

But sometimes, we want a stronger statement than simply "the adversary is unable to decrypt". Instead, we want to be able to say something stronger, e.g. that the adversary cannot determine even a single bit of information about the decryption.

Now, I can guess the value of a bit with probability $p = 1/2$, which is significantly larger than $0$. Which means that the probability $p$ of answering correctly is not a useful measure of my power.

We could say that I should be able to guess correctly more often than half the time, in which case $p-1/2$ might be a sensible measure. But if I somehow always end up guessing wrong, so that the probability $p$ of me answering correctly is $0$, then essentially I know what the bit of information is. Reliably answering wrong is essentially as good as always answering correctly.

So we take absolute value, and arrive at the usual definition of advantage being $|p-1/2|$.


Different encryption standards and how they relate to auth and algorithms The main confusion I have is around the different PKCS and relation with SSL (TLS). I have done a lot of research and have found bits and pieces but not necessarily how these relate, so let me explain but first with a little background.
To start, I am fairly comfortable with how SSL (and subsequently TLS) works, and subsequently mutual TLS. Typically X.509 certs with CA signed for mutual authentication, and sometimes using self signed certs. Also with how the symmetric key is used for the content encryption and the asymmetric key is used for encrypting the symmetric key.
I am also fairly comfortable with PGP, encrypting, signing, different algorithms, features like built in zip compression, etc. Particular interest in RSA encryption and signature algorithms, but more on that later. So, so far we have SSL which security can be enhanced if you encrypt a payload before using the transport level encryption, especially if you're sending data somewhere where you don't want any data to be unencrypted at rest.
Now on to PKCS where it starts to get a little hazy. I know that PKCS are just standards.
PKCS#12 - These are your .pfx or .p12 files, which can be used to store your X.509 certs with the corresponding private key (very simplistic definition). My guess, and please correct me if I'm wrong, is that these are typically created be a server which wants to setup HTTPS. Can use different algorithms, like RSA which is also mentioned in PGP.
PKCS#7 - Subsequently CMS, typically used for generating and verifying digital signatures. Here is where I'm finding some conflicting information. I understand digital signatures, calculate the hash encrypt with the private key so you can verify, with the public key, that the message was not tampered with and that it came from the correct sender. Before I get to the main question relating to auth, I see that PKCS#7 can use AES, which is a symmetric key algorithm. Does this make sense, and if so is this common or how would that work?
Now main questions sorry if that was long winded.

I was told to download a PFX file in order to authenticate with an
API, similar to this question. Question on this, and related to
my next question on PKCS7, is how does that authentication work? I'm
getting the private key and cert in the form of a .pfx file from
the server, does that mean that the server is just self signing this
and this is essentially mutual TLS using a self signed cert? If not,
we then just be using TLS (so encrypted with the servers public key)
with the message content being our payload signed with our private
key?
Similar for PKCS7. I completely understand how we verify the
signature with the public key. How how do we handle the
authentication if we are sending data across to some API (typically
speaking)? Because technically once we have something that we have a digital signature,
really anyone anywhere can send this, so how would we know it is being sent by a particular
client or do we not care?

Sorry for the long post and hopefully you can clear some of this up for me.

PKCS#7 - Subsequently CMS, typically used for generating and verifying digital signatures.

I wouldn't go for 'typically' there. There are three main uses of PKCS7/CMS today:

signature on various kinds of data ranging from Java or Windows code to PDF documents
signature on and/or encryption of mail messages or attachments in S/MIME
as a container for certs and/or CRLs, as described in the Q you linked for PKCS12 (and others too)

I don't have numbers and I'll accept the first might be more common, but the others exist.

I understand digital signatures, calculate the hash [and] encrypt with the private key so you can verify, with the public key, that the message was not tampered with and that it came from the correct sender.

No. This is a commonly repeated mistake, but signatures are not 'encrypting with the private key' or 'encrypting backwards'. For RSA only, not other algorithms, there is a mathematical similarity which 30-ish years ago led people to use this description, but the actual signature and encryption schemes are vitally different, and more importantly differ semantically, so informed people no longer say this. See my growing list of Qs or As on this at https://security.stackexchange.com/questions/159282/can-openssl-decrypt-the-encrypted-signature-in-an-amazon-alexa-request-#159289 . As relevant here, compare any CMS even the earliest in 1999 which says SignerInfo.signature "is the result of digital signature generation, using the message digest and the signer's private key" and defines signature generation and verification to use private key and public key respectively but otherwise leaves them to other standards, versus actual PKCS7v1.5 which was redistributed by IETF in 1998 but actually published by then-RSALabs in 1993, which says SignerInfo.encryptedDigest "is the result of encrypting the message digest and associated information with the signer's private key" and in 9.4 essentially copies part of the then-current version of PKCS1.
It is true that digital signature allows the verifier to be certain that the data is untampered and is 'from' (or at least was seen/approved by) the party holding the private key, which should be unique (more below), and can (at least try to) verify that the signer is the 'correct' sender according to whatever criteria are relevant to that correctness.

I see that PKCS#7 can use AES, which is a symmetric key algorithm. Does this make sense, and if so is this common or how would that work?

Only for 'enveloped' (that is, encrypted) messages, not for signed messages or detached signatures; as I said above I don't have numbers on usage.

I was told to download a PFX file in order to authenticate with an API, similar to (link) ... how does that authentication work? I'm getting the private key and cert in the form of a .pfx file from the server, does that mean that the server is just self signing this and this is essentially mutual TLS using a self signed cert? If not, we then just be using TLS (so encrypted with the servers public key) with the message content being our payload signed with our private key?

This is very likely TLS with client authentication also called mutual authenication or just mutual TLS, yes. The certificate must be one that is trusted by the server(s) you connect to; this can be self-signed by the server, it can be signed by the server acting as a CA, or it can be obtained from some other CA which signs it. It doesn't matter to you as long as the result is trusted, although if you are curious you could look at the certs with any of the many tools that can look at a PKCS12/PFX, or a cert or several certs extracted from one.
TLS never encrypts data with the server's public key. TLS encrypts, and authenticates, data in both directions using symmetric algorithms with per session (and connection) 'working' keys which are created by 'key exchange' process during the initial handshake. See e.g. https://security.stackexchange.com/questions/20803/how-does-ssl-work/ for an extensive but slightly out of date explanation -- it hasn't been updated (yet?) for TLS 1.3 which was released in 2018 and is now becoming more and more common. The oldest and now mostly obsolete key exchange, called 'static' or 'plain' RSA, does encrypt the premaster secret using the server public key, but newer key exchanges (especially in 1.3) use Diffie-Hellman signed by the server private key and verified by the client with the server public key (from its certificate, after validation). Conversely, client auth in TLS always signs handshake data with the client private key and it is verified by the server using the client public key (ditto).

Similar for PKCS7. I completely understand how we verify the signature with the public key. How how do we handle the authentication if we are sending data across to some API (typically speaking)? Because technically once we have something that we have a digital signature, really anyone anywhere can send this, so how would we know it is being sent by a particular client or do we not care?

Creating a digital signature that will verify successfully requires using the private key, and the whole concept of public-key cryptography is that only the 'owner' has the private key; everybody else should have only the public key. Thus if a particular key belongs to client X, only client X can create signatures with that key. However in your example, where the server is apparently passing out PKCS12's containing private keys willy-nilly, which is not considered good practice, this guarantee is greatly weakened: it is definitely possible for that server and anyone else who gets a copy of 'your' PKCS12 to forge data (in this case connections) from 'you'. Although if your connections are to this same server, its ability to forge a connection doesn't matter too much, because it could just as easily lie about what it received on a legitimate connection.


What is the purpose of using different hash functions for the leaves and internals of a hash tree? I just learned that the THEX hash tree specification which is widely used in P2P requires that two different hash functions be used: one for the leaf nodes (hashes of input data) and one for the internal hashes (hashes of hashes).

  In order to protect against collisions between leaf hashes and
  internal hashes, different hash constructs are used to hash the leaf
  nodes and the internal nodes. The same hash algorithm is used as the
  basis of each construct, but a single '1' byte in network byte order,
  or 0x01 is prepended to the input of the internal node hashes, and a
  single '0' byte, or 0x00 is prepended to the input of the leaf node
  hashes.

By contrast, the proposed (though not yet widely adopted) Simple Merkle Hashes extension for BitTorrent just uses unmodified SHA-1 for all hashes. It's conceivable that this was a trade-off of security for simplicity, but that wasn't mentioned in the proposal.

What is the benefit of using two different hashes in this scheme?

If the same standard hash function was used for both leaves and branch nodes, it would be easy to generate collisions and even second preimages.

For example, let $M$ be a message which is longer than the segment size of the hash tree, but (for simplicity) no more than two segments long. Then the hash value of $M$ is calculated as $$H(M) = H_I(H_L(M_0) \,\|\, H_L(M_1)),$$ where $H_I$ is the internal hash function, $H_L$ is the leaf hash function, and $M_0$ and $M_1$ are the first and second segments of $M$.  We'll also assume that the segment size of the hash tree is at least twice as long as the length of the output of $H_L$.

Now let $M' = H_L(M_0) \,\|\, H_L(M_1)$.  Since $M'$ is, by assumption, at most one segment long, its hash will be calculated as $$H(M') = H_L(M') = H_L(H_L(M_0) \,\|\, H_L(M_1)).$$  If $H_L = H_I$, then $H(M') = H(M)$, and we've just found a second preimage for $H(M)$.


Bulletproof - Is it possible to do range proof only from public key? is it possible to proof x in range (2^1,2^64) from xG=Q with bulletproof or something else only from Q? I’m new in this subject, so thanks before.

No, it is not possible to generate a proof only with the knowledge of $Q$; you need the knowledge of $x$.

If it were possible to generate a proof (or fail to generate a proof if $x$ were out of the range), then it would be possible to efficiently recover the value of $x$ by attempting to generate a range proof for $Q - yG = (x - y)G$ for various values of $y$.


Brute forcing the secret key in Elgamal encryption Crypto noob here, I am attempting to do this programming challenge. I do not have the secret key that is used to decrypt the message. However, the key is small enough for a brute force approach. I am attempting to write a function that will solve for the secret key with other variables used in the process.

  She tells Bob values of $p$ and $pe \equiv p^e \pmod{n}$ (p raised to power of e mod n)
  as her public key. Meanwhile the value e remains her secret key (there
  is no easy way to calculate it from $p$ and $p^e$).

I have $pe$, $p$, and $n$. Here is some code written in java.

static int findE(int n, int p, int pe) {
    for(int e = 0; e < n; e++) {
        if(modular_pow(p, e, n) == pe)
            return e;
    }
    return -1;
}

static int modular_pow(int base, int exponent, int modulus) {
    int c = 1;

    for(int i = 0; i < exponent; i++) {
        c = (c * base) % modulus;
    }
    return c;
}

I calculate $p^e \pmod{n}$ for all possible values, but my "findE" function always returns -1. I have tested my modular_pow function and am certain that is not the problem. Maybe I am misunderstanding the instructions. Thanks for any help!

Given $p$ and $p_e \equiv p^e \pmod{n}$. You need to calculate $p_e$. Propose $e$ is small enough to brute-force. The simplest way would be to calcute $p^e \pmod{n}$ for values $e \in \{1,2, ..., n-1\}$ until you find $p_e$.

So all you need would be something like this:

static int findE(int n, int p, int pe) {
    int base = p;
    for(int e = 2; e < n; e++) { // also it suffices to start at e=2
        p = p * base % n;
        if (p == pe) return e;
    }
    return -1;
}

Even though you are doing to much calculation (for every value of $e$ you recalculate all values of $p^{e-1}$), right now i do not see why your code would'nt work.
Update: forget all i said about modular exponentation, that was bullsh*t.


What is the definition of Feistel Cipher? I know how Feistel Network works, but I want to know the exact definition of "Feistel Cipher" to solve several questions below:

  question 1: Is it correct to say DES (Data Encryption Standard) is Feistel Cipher?

Opinion: I think the statement "DES uses Feistel Network" is correct. Also, since the encryption and decryption process is same, except key scheduling,
somebody can say that DES is Feistel Cipher. But I think somebody else can say that DES is not a Feistel Cipher since DES has initial and final permutations.

  question 2: Does "DES_Encrypt'(M,K1,K2) =  DES_Encrypt(M,K1) xor K2" is also Feistel Cipher?

Opinion: I think the statement "The above modified DES uses Feistel structure" is correct. But, since the above modified scheme's encryption and decryption structure are not same, somebody can say that the above modified scheme is not Feistel Cipher.

There can be several options to solve this definitional problem:

We call an encryption scheme a Feistel Cipher, if it uses Feistel Network;
We call an encryption scheme a Feistel Cipher, if it only use Feistel Network;
We call an encryption scheme a Feistel Cipher, if it uses Feistel Network and the encryption and decryption procedure is same, except the key scheduling process.

Which one is correct? Or, are there any other opinions?

I know that this problem is not that important, but I want to make it clear.

According to Definition 7.81 given by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography,

  A Feistel cipher is an iterated cipher mapping a $2t$-bit plaintext $(L_0,R_0)$, for $t$-bit blocks $L_0$ and $R_0$, to a ciphertext $(R_r,L_r)$, through an $r$-round process where $r\ge1$.
  For $1\le i\le r$, round $i$ maps $(L_{i−1},R_{i−1})\xrightarrow{K_i} (L_i,R_i)$ as follows: $L_i=R_{i−1}$, $R_i=L_{i−1}\oplus f(R_{i−1},K_i)$, where each subkey $K_i$ is derived from the cipher key $K$.
  Typically in a Feistel cipher, $r\ge3$ and often is even. The Feistel structure specifically orders the ciphertext output as $(R_r,L_r)$ rather than $(L_r,R_r)$; the blocks are exchanged from their usual order after the last round. Decryption is thereby achieved using the same $r$-round process but with subkeys used in reverse order (...)

On the next page they state, with the contradiction pointed in the question's Q1:

  DES is a Feistel cipher (...)
  An initial bit permutation (IP) precedes the first round; following the last round, the left and right halves are exchanged and, finally, the resulting string is bit-permuted by the inverse of IP.

In Q1: DES is a Feistel cipher, except for IP and IP-1; that deviation keeps the notable property of a pure Feistel cipher that only the order of subkeys differs for encryption and decryption.

In Q2: the construction is a Feistel cipher, except for the above deviation, and an additional final XOR with $K_2$ on encryption, and correspondingly an additional initial XOR with $K_2$ on decryption; this looses the aforementioned notable property of a pure Feistel cipher, and adds a key-dependent transformation.

I would say the answer to Q1 is yes for Jim Kirk, and no for Mr. Spock; while they could agree on no for Q2. The Captain is on option 3 in the question (perhaps also requiring that any key-dependent transformation is thru the Feistel structure); while the logician sticks to 2 (and wants any deviation to be explicit). Nobody on the deck stands for 1.


Is it secure to use Diffie-Hellman key agreement to generate a nonce? I have a system, using AES, in one of the modes that uses a nonce and authentication.

We have a pre-shared key, and to agree about initial nonce we could use Diffie-Hellman, using the resulting secret as an IV.

I want to know if there can be any attack on this system: is it possible to perform a man-in-the-middle attack or a replay attack?

This algorithm is vulnerable to a Man in the middle. From Wikipedia:

In the original description, the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack. Mallory may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must continue to be in the middle, transferring messages every time Alice and Bob communicate. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in the channel.
A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie–Hellman, such as STS protocol, may be used instead to avoid these types of attacks.


HMAC does it matter if I chose the cipher text or the plain text as the message? I am using HMAC to create a message authentication code. My question is, does it matter if I use cipher text + encryption key or plain text + encryption key? I had a look at a implementation and as far as I can see they just concatenate the values (message and encryption key) and hash them.

Yes, it does matter. A MAC should always be over the ciphertext, not the plaintext.

HMAC(key, ciphertext) = Hash((DerivedKey xor OuterPad) || Hash((DerivedKey xor InnerPad) || Ciphertext))

Where || denotes concatenation.
OuterPad is a one-hash-block long hexidecimal constant 0x5C5C...5C.
InnerPad is a one-hash-block long hexidecimal constant 0x3636...36.

Of course you should use an existing implementation of HMAC instead of trying to make your own, but if your library is just concatenating values and then hashing them it's not HMAC, and you should use a different library (assuming the library actually calls it HMAC).

There are other MACs than just HMAC, such as SHA-3's KMAC or Poly1305. They also should only be applied to the ciphertext. Your library may be using one of these. I happen to like the libsodium library. It uses Poly1305 for its MAC. It also includes a design that makes it hard to misuse: it's impossible to use a symmetric cipher without properly applying a MAC, so you don't have to worry about the answer to this question. You just call the appropriate crypto_secretbox function!

The following question and answers give reasoning for Encrypt-Then-MAC being optimal: Should we MAC-then-encrypt or encrypt-then-MAC?


Why is public key cryptography (RSA) used in sites like Google or Facebook? The RSA algorithm is used for encryption (plain text to cipher text) and decryption (cipher text to plain text) of data. What is the need for using public keys in these sites; why is data is encrypted as everything is viewed by everyone?

Why do we need to use public key cryptography in Google; how does it provide security?

[I assume you're talking about Google's web search service, and not Gmail.]

Google doesn't encrypt the web page data in storage, because it's not secret data.  Encryption is optionally used by users to securely communicate with Google, and that's different.

Using certificate based keys and encryption assures the users that they are communicating with the Real Google and not a Fake Google that could give them false results.  It also protects the users' privacy from eavesdroppers; so if someone was searching for 'cancer' their employer or family wouldn't know.


how to prove sequence y uphold golomb's third axiom given $\{ x_k \}$ is a m-seq of order $n$, we define $\{ y_k \}$ to be a $m$ digits number:
$$
y_i=x_ix_{i+1}...x_{i+m-1}
$$
for every integer $n \ge m \ge 1$

how can I show that $\{ y_k \}$ upholds golomb's third axiom which says that the auto-correlation:
$$
c_{yy}(\tau)=\left\{\begin{matrix}
2^n-1 & ,\tau=0\\
Const & ,\tau \ne 0
\end{matrix}\right.
$$
I'm having troubles understanding how to show that it is the same const for every $\tau$

The full $m-$sequence (periodically repeated to avoid modular addition in the subscript} with $$C_{xx}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{x_k+x_{k+\tau}}$$ satisfies $C_{xx}(\tau)=-1+\delta(\tau)(2^n),$ where $\delta$ is the dirac delta function. Now, one might define an $m-$symbol partial correlation function, whose average is proportional to what you want, if the average is taken over all starting points in one period. But this function itself is nearly binomially distributed and not constant over nonzero $\tau,$ for $m\leq n$. To be clear, I am referring to a function of the form
$$
C_{xx}(i,m,\tau):=\sum_{k=0}^{i+m-1} (-1)^{x_k+x_{k+\tau}}
$$
and its average
$$
\overline{C_{xx}(m,\tau)}=\frac{\sum_{i=0}^{2^n-2}C_{xx}(i,m,\tau)}{2^n-1},
$$
which arises in communication applications.

Finally if you just take the $y_k$ to be an integer in $\{0,\ldots,2^m-1\}$ by letting the vector $(x_k,x_{k+1},\ldots,x_{k+m-1})$ be the binary representation of the integer $y_k$, then due to equidistribution of $m-$tuples under the Golomb postulate the correlation function
$$
C_{yy}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{y_k+y_{k+\tau}}
$$
will also be two valued since tuple equidistribution implies equidistribution of $y_k$ modulo 2, and the exponent might as well be reduced modulo 2. So you get the same distribution as that of the correlation $C_{xx}(\tau)$. Was this the point of your original question?


How were the DES S-box values determined? It seems like the S-boxes in DES have essentially random values.

How were these chosen?

There is a good article from Coppersmith which explains it. Basically, the designers of DES had envisioned differential cryptanalysis (a good 15 years before differential cryptanalysis was rediscovered by Biham and Shamir, and published); they could measure how well DES could resist differential cryptanalysis for a given set of S-boxes.

So they generated a huge bunch of random S-boxes, measured them all and kept the best.

It turns out that although the DES designers did not know of linear cryptanalysis (discovered in 1993 by Matsui), having S-boxes which resist differential cryptanalysis kinds of defeats linear cryptanalysis as well.


Permutations of pseudorandom data Assuming a bit string is deemed cryptographically secure, e.g. PRNG using AES in counter mode, can we equally assume any permutation of said bit string is also cryptographically secure?

In a more practical sense, using a PRNG with AES in counter mode again (for instance), assume it turns out that AES can be more efficiently computed by permutating the input data and rearranging the implementation of the algorithm accordingly. Does the resulting pseudorandom bit string need to be permutated back to the correct order or can I use it directly as a cryptographically secure bitstring? (this is from a purely theoretical pov.)

PS: I used AES as an example, it could be any secure block cipher.

PS2: sorry about the sloppy use of technical terms, but I hope you will understand what I mean.

Yes, an additional bit permutation of pseudo-random data from a secure Pseudo-Random Number Generator is secure, subject to the condition that this bit permutation is independent of the key material of the PRNG and of any data derived from that (including the pseudo-random data).

An argument is that if this permutation is public, the adversary can do/undo it at negligible cost and is back to the original problem of breaking the PRNG (with no usable information, given the sated condition); if this permutation is secret, its addition can only be an additional complexity for the attacker (given the stated condition). That could be formalized.

If the stated condition is not met, a counterexample can often be found. For example, if the permutation is chosen from the output of the original PRNG so as to put all the 0 bits first, then the output is weak. Same if the permutation is part of the key of a cipher, with the cipher ending in that permutation, and the cipher transformed into a PRNG by using counter mode.


Enigma: Theorie Rotors I wanted to programm the enigma (using C#). But it seems like i dont understand how the rotors work. Becouse if we take the first three rotors:

ekmflgdqvzntowyhxuspaibrcj
ajdksiruxblhwtmcqgznpyfvoe
bdfhjlcprtxvznyeiwgakmusqo
UKW A: ae  bj  cm  dz  fl  gy  hx  iv  kw  nr  oq  pu  st
(The meaning of the possitions are from a-z oc).

So if we take the route of A now: a-e; e-s; s-g; g-y; y-q; q-q; q-x; x= encrypted output.

Now lets go back again: x-r; r-g; g-c; c-m; m-z; z-e; e-l; l = decrypted output

So where is my logical problem?

When the signal goes back through the rotors after the reflector, the permutation for each rotor is inverted. That's what you're missing.

In a way, this is kind of obvious: if going through the rotor one way would map, say, A to E, then going through it the other way has to map E to A, and so on.

(The permutation applied by the reflector itself is always, by design, its own inverse; it just swaps distinct pairs of letters.)


Which algorithm do you recommend for practical use to generate unique passwords for each website? So, in my imagination there is this simple algorithm with only one master password, let's say a prime number 'p', which I have to remember. Using only the address of the website and p, the algorithm must generate a unique password. It must be at least almost impossible to guess the value of p even if you know the algorithm. Also impossible to guess the password of website B if you know the password of website A and the algorithm. The reason why I need this algorithm: I'd have different passwords and would have to remember only one number. There's also the matter of having multiple accounts on the same website but I think it will be easy to modify the algorithm. I think it will be useful for many users.

The problem is almost exactly the same as in password based key derivation, so you could use a similar solution.

Derive a master secret from your password and a unique salt using e.g. PBKDF2 or scrypt: $S_m = PBKDF(p, s)$.
Derive a site-specific secret from the master using e.g. HKDF and the site URL: $S_u = HKDF(S_m, u)$.
Turn the site secret into a usable password, e.g. by encoding in base 64.

If you go this route you are putting all your eggs in one basket. If you forget the master password, you lose all the derived ones. If someone guesses it, they can derive all the others.

You would probably be better off just using a password manager that prevents guessing attacks. Otherwise the master must be very strong. A password manager generates random site passwords that leak no information about the master.


Correctness vs Completeness What is the conceptual difference between the definition of correctness and completeness in verifiable cryptographic protocols? They justify that if a statement is correct then the verification should always successfully verifies. Is their any difference in the definitions? Or the one can substitute correctly the other?

It seems like authors prefer the term correctness for verifiable computations and the term completeness for zero-knowledge proofs

In context of interactive proof systems (including zero-knowledge proofs) completeness means the same as the term correctness as used for many other (interactive) cryptographic schemes or protocols. I guess that's mainly due to historical reasons (there are even some people that use correctness instead of completeness in context of zero-knowledge proofs).

Basically, both things say that if everything happens honestly, then it works out as it is supposed to be. Note that completeness as well as correctness may not be perfect. For instance, zero-knowledge proofs may have a completeness error, i.e., even if the statement to be proven is true and both - the prover and the verifier - behave honest, the verification may only work with some probability (close to one). Similarly, for public key encryption schemes the correctness may also only hold with a probability close to one, i.e., that decrypting a ciphertext for a message may lead to some different message (even under some honestly generated keys).


Security model scalar multiplication in NaCl I'm having trouble understanding what the “security model” for “scalar multiplication” in NaCl is.

  Security model

  crypto_scalarmult is designed to be strong as a component of various well-known "hashed Diffie–Hellman" applications. In particular, it is designed to make the "computational Diffie–Hellman" problem (CDH) difficult with respect to the standard base.

  crypto_scalarmult is also designed to make CDH difficult with respect to other nontrivial bases. In particular, if a represented group element has small order, then it is annihilated by all represented scalars. This feature allows protocols to avoid validating membership in the subgroup generated by the standard base.

  NaCl does not make any promises regarding the "decisional Diffie–Hellman" problem (DDH), the "static Diffie–Hellman" problem (SDH), etc. Users are responsible for hashing group elements.

Since “crypto_scalarmult is the function crypto_scalarmult_curve25519”, does this mean that Curve25519 does not provide any guarantees for the DDH problem to be hard?

If so, how can one—as suggested—hash group elements to achieve this? E.g., how does one implement elliptic curve El-Gamal in a semantically secure way using this implementation, if possible at all?

Since "crypto_scalarmult is the function
  crypto_scalarmult_curve25519", does this mean that Curve25519 does
  not provide any guarantees for the DDH problem to be hard?

No, it just means, that the NaCl specification or API, which is different from the NaCl implementation / library, makes no guarantees about the DDH problem being hard in the group being used. The implementation however may of course go beyond what is guaranteed by the API and use a group where DDH is hard, such as Curve25519.

  If so, how can one hash group elements to achieve this?

The output of the crypto_scalarmult function essentially is a chunk of bytes. You can then use your favorite hash function (e.g. SHA-3-256 or SHA-256) or preferably your favorite key-based key derivation function (KBKDF) (e.g. HKDF) to derive symmetric key material for bulk encryption.

  How does one implement elliptic curve El-Gamal using this
  implementation, if possible at all?

ElGamal requires the message to be represented as a group element which is not trivially possible to do in an (easily) invertible way and thus I strongly discourage anyone from using EC-Elgamal and instead use ECIES.

However you asked and I shall answer (using the notation from the HAC (PDF)):
Let $\alpha$ be your generator of the (sub)group. Let $\beta$ be your recipient's public key and $a$ be his private key. $\beta$ can be generated from $\alpha$ as $\alpha^a=\beta$, which maps 1-to-1 to a call to crypto_scalarmult.

For encryption you then pick a random $k$ which is smaller than the group's order and compute $\beta^k$ and $\gamma=\alpha^k$ which both can be done by single calls to crypto_scalarmult and then you compute $\delta=m\cdot(\beta^k)$, e.g. you apply the group operation to $m$ and the buffered $\beta^k$. Your ciphertext of the plaintext $m$ is now $(\gamma,\delta)$.

Decryption is even easier, you compute $\gamma^{q-a}$ where $q$ is the (sub)group's order and then perform a group operation using $\gamma^{q-a}$ and $\delta$, the result will be $m$.


Security of AES ECB for 128 bit random data I am using AES ECB mode to encrypt and decrypt 128 random data. I have read on drawbacks on using ECB but it seems that it is feasible to use it for random data. However my concern is that my implementation provides an oracle. What i am concerned is key extraction. Would it be possible in reasonable time or possible at all? Again the data is random, basically server generates 128 random bits and sends it to client, the clien then encrypts it and sends it back to server. However client and server communicate via a third party (tethered way) so third party can see both plaintext and ciphertext.

My two questions are:
is it safe to use AES ECB when both plaintext and ciphertext are visible to a third party? (random data, replay is not a concern)

Also there is a case where it becomes an oracle (if i am using it correctly) anyone can send 128 bits data and get cipher of it back.. (possible but not that practical, though i am wondering of its implications)?

AES is designed so that it is infeasible to derive the key with only the plaintext and ciphertext. It's part of the definition of a strong cipher.

At the risk of sounding like a broken record, the real problem with ECB is that the same input blocks produce the same output blocks. This is devastating if your data is more than 128 bits. Other modes prevent this by adding in some randomness as well as having previous blocks affecting future blocks.

Another security feature added by some modes is authentication. They provide a way to prove your data came from the place you expect it did, and to prove it wasn't tampered with. Without authentication, attackers could corrupt a single block of your data without you being able to directly tell (barring non cryptographic methods, such as checking if the decrypted data makes sense, but thats a lot less strong).

If all you need is secrecy, and integrity and authentication is of absolutely no concern to your threat model, and you guarantee the same block isn't ever encrypted twice, then encrypting 16 bytes (128 bits) of random data with AES ECB is okay.


How SPHINCS+ Hash Signature ADRS structure define can anyone help me to elaborate the structure of ADRS with example ( tree ADRS, layer ADRS, keypair ADRS etc)used to generate root SPHINCS+ signature. Also can some one help me to describe tree hash process used in SPHINCS+ with example.

Well, the ADRS structure is an 32 byte structure, organized as 8 4-byte words.  It looks like:
  +--------------------+
  |   Layer address    |
  +--------------------+
  |    Tree address    |
  |      (3 words)     |
  |                    |
  +--------------------+
  |        Type        |
  +--------------------+
  |  Keypair address   |
  +--------------------+
  | Chain/Tree Height  |
  +--------------------+
  | Hash addr/Tree Idx |
  +--------------------+

The idea behind the ADRS structure is that every single hash computation within Sphincs+ gets a separate ADRS structure.  Because the ADRS structure is an input to the hash, someone brute-forcing the hash computation would need to select the ADRS structure, which means that their brute-force search cannot take advantage of any multitarget attacks.
As for what the various fields within the ADR structure designate:
Layer address - Which Merkle tree level we are working on (0 is the lowest); also 0 if we're working within the FORS tree
Tree address - Which Merkle tree (counting from the left) in this level we are working on.  This is used for FORS, WOTS and Merkle tree hashes.
Type - An indication of why we are doing this hash in the first place; this ensures that, say a hash we do for the FORS does not collide with a hash we're doing for the WOTS
Keypair address - Which WOTS leaf are we working on (counting from the left of the Merkle tree).  Not used during a Merkle tree hash.
Chain/Tree Height - During WOTS, which Winternitz chain we are working on.  During FORS, what height we are in the FORS tree (1 being the bottom).  Unused during a Merkle tree hash.
Hash addr/Tree Idx - During WOTS, where in the Winternitz chain are we (with 0 being the first node in the chain).  During FORS, the horizontal position of the node we're computing (counting all the FORS trees under the current WOTS leaf); the later includes both "where in the FORS tree we are hortizontally", as well as "which FORS tree this is".  Unused during a Merkle tree hash.


What is "serial concatenation"? I have a third-party point-of-sale API (Speedflow Pay-N-Get) that I am trying to communicate with over HTTP, but I have a problem with it.

In a nutshell, a request is encrypted using RSA, and the response is encrypted using RSA followed by Rijndael/AES-128.  The RSA keys are provided by the vendor, the AES IV is a vendor-provided guid, and the AES key is the vendor-provided guid and a random requester-generated guid combined using "serial concatenation".  The random guid is included as a parameter of the request.

I am using OpenSSL to handle the encryption/decryption.

I have everything working except the AES portion.  I have no clue what "serial concatenation" is, online searches do not find any useful info about it, and the vendor has not replied yet.  Does anyone know what this is?

Update: Here is what the API doc says about the AES portion of the encryption:

  The server response — EDATA data in the body of the HTTP response.

  Formula: EDATA = Base64(Rj(RSA1(DATA)))

  Rj — symmetric algorithm Rijandel-128

  IV — Guid # 1 value, converted to a byte array

  Key — value Guid # 1 and Guid # 2 (serial concatenation)

  mode spacing — Zeroes

Also:

  -----Decryption.-----

  RSA (AES ( BASE64( response ) ) ),

  where RSA - RSA- private-key encryption

  AES - Symmetric key encryption

  response – server response

  -----AES-----

  use bouncyCastle: cipher= PaddedBufferedBlockCipher ( CBCBlockCipher ( RijndaelEngine(128)),
  ZeroBytePadding() );

  cipher.init (false, ParametersWithIV ( KeyParameter ( mykey ), iv )
  );

  where mykey- coding in hex string guid3

  iv- concatenation coding in hex string guid3 and coding in hex string guid2

  Encoding is performed on this algorithm by taking two character of a string is converted to hex and added to an array of bytes.

Guid#1 is the vendor-provided Guid, Guid#2 is the randomly generated Guid.  Both are included in a request.  I suspect the second paragraph actually meant the IV is Guid3 and the key is the concatenation of Guid3 and Guid2.  Guid3 is just Guid1 with its first 3 fields converted to big endian.

Since an AES-128 key is only 16 bytes in size, and a Guid is also 16 bytes in size, I suspect that "serial concatenation" would be somehow hashing them together, rather then simply appending them to each other, which would produce a 32-byte key instead.

"Serial concatenation" is not a standard term in cryptography.  Without any further information, I would guess that it probably refers to just concatenation.  If that's not what it refers to, then your spec is deficient and ambiguous; you'll need to consult with the author of the spec to ask for to clarify what they meant by that phrase.


Hashing Resource ID Into Publicly Known Value Securely I am in an environment where I have unique IDs for a list of resources. I am trying to design a system that takes that ID as an input parameter and produces a consistent output for a given resource. I am trying to obfuscate which ID led to a given output, but both the input IDs and the output will be public information. There can be as few as 2 resources (and thus only 2
 possible input IDs).

I am also trying to avoid having to store any additional information for each resource.

Would combining the input ID with a large (256 bit) secret salt value then running it through a hash function be sufficient? Would it be safe to use the same salt for all inputs?

Optimally, It would also be convenient if I could figure out which resource created which output given only the salt, but that wouldn't work with my proposed solution. Is there some other way to approach this problem that would have that property?

You are right thinking that using a large secret salt, such as a 256 bits value generated randomly (with a good CPRNG) should be fine.

Notice that we usually say that a salt can be known from the attack, which is not the case in your design, so you are not using a salt, but a key. Keyed-hash function are a thing (see BLAKE2, for example), but you can generally construct a keyed-hash function out of any hash function by simply hashing the concatenation of your key and your message with the said hash function.

In this latter case, which correspond to your design, the preimage resistance of the hash function would prevent the attacker from finding the "salted/keyed Resource ID" without knowing the key.

Using more than one key, like for example, one for each resource, would simply strengthen the system against potential leaks that might occur. Since then, if a key leaks, the rest of the non-leaked keys would still prevent an attacker from finding the image of a given Resource ID (or finding the preimage of a given hash by bruteforcing the possible Resource IDs, if those are known/in a small range).

Notice that the system you mention:

  a system that takes that ID as an input parameter and produces a consistent output for a given resource

is somehow similar to a pseudo-random generator, where the key would be the resource ID. Using a keyed-hash function as you propose (as long as the key has enough entropy) is a way to construct such PRG, but there are some hiccups if you let the adversary possibly control your entropy pool... I'm looking for example at the "Hash_DRBG"...

Now another way around your problem, since you've got a key already, might be to simply encrypt the resource ID with a symmetric (AES, e.g.) and that key you called "salt"... (As long as that key is generated with a good entropy, using a CPRGN, you're safe.)

Plus you'd get the two-wayness you wanted, as you could simply decrypt the resulting value using the key to obtain the initial resource ID out of it.


Station-to-Station protocol questions Basic Station-to-Station protocol which authenticates Bob and Alice if they safely shared their long-term asymmetric public keys.

Alice sends Bob her public key $A_K$
Bob receives $A_K$ and computes the shared secret key $K$
Bob signs with his long-term key $S_B(\mathit{B_K, A_K})$ and encrypts $E(S_B(B_K,A_K), K)$ using AES 128 GCM
Bob sends Alice $B_K, E(S_B(B_K,A_K), K)$
Alice computes $K$, decrypts $E(S_B(B_K,A_K), K)$ and verifies the sig. using Bob's long-term public key
Alice signs $S_A(\mathit{A_K, B_K})$, encrypts $E(S_A(A_K,B_K), K)$ and sends the resulted ciphertext
Bob decrypts $E(S_A(A_K,B_K), K)$ and verifies sig. $S_A(\mathit{A_K, B_K})$ using her long-term public key

I have three questions.

Before Bob computes $S_B(\mathit{B_K, A_K})$ does he hash $B_K$ and
$A_K$ using $SHA256$ for example so Alice can hash them herself and compare the hashes?
Does Bob use plain $K$ for encryption or does he use a key
derivation function like $HKDF$?
If Bob uses $HKDF$ can he include the salt at the end of the data he
sends to Alice?

1. Before Bob computes $S_B(\mathit{B_K, A_K})$ does he hash $B_K$ and
      $A_K$ using $SHA256$ for example so Alice can hash them herself and compare the hashes?

Generally the signature generation function already includes a hash operation (which might be SHA-256) so requiring a separate hashing step isn't required; it should be configured for the signature generation function.

You could use a separate hash if you don't want to involve the private key early in the protocol - but that's the only reason I can think of.

  2. Does Bob use plain $K$ for encryption or does he use a key
      derivation function like $HKDF$?

Depends.

Generally key agreement (which seems to be missing entirely from your protocol) will generate a shared secret. But this secret may not be well distributed and / or may be too large. So in that case a separate KDF is required.

Note that sometimes a KDF is already configured within the key agreement protocol, so in that case a separate KDF is not required - just like with the hash function for the signature generation algorithm. Of course you could still use a separate KDF to derive more keys or keys with a different size if that's needed in your protocol.

  3. If Bob uses $HKDF$ can he include the salt at the end of the data he
      sends to Alice?

Sure, or the salt can be left out altogether. But HKDF does mention that adding a salt is preferred to achieve high amount of security.


Encrypt-then-MAC with base 64 I've a doubt about the Encrypt-then-MAC approach when using HMAC-SHA-256 with AES-128 in CBC mode, as seen in https://en.wikipedia.org/wiki/Authenticated_encryption.
I need to encode the resulting ciphertext in base 64 in order to send along with the HMAC. Should I generate the HMAC before or after encoding the ciphertext in base 64? Does it even matters?
For example:
1 - Encrypt-then-encode-then-MAC, or
2 - Encrypt-then-MAC-then-encode.
Thanks in advance.

EDIT: I'm using JSON to separate the message and the HMAC, like:
{
  "payload":"base64-encoded-ciphertext-goes-here",
  "hmac":"base64-encoded-HMAC-goes-here"
}

Generally you would use encrypt-then-MAC before encoding. There is no need to process the expanded ciphertext before encoding, and you may be able to send the
message both in binary and ASCII-armored with base 64.

Note that you would have to base 64 encode the authentication tag (the HMAC output) anyway if you would choose encrypt-then-encode-then-MAC, it would be encrypt-then-encode-then-MAC-then-encode.

Choosing the encrypt-then-MAC-then-encode does require you to:

Establish where the tag is situated:

Generally this is performed by just appending the tag and then count 32 bytes backwards (assuming the entire 256 bit output is used for the MAC, the default) or to include a length encoding for the ciphertext. However, a full ASN.1 structure could also be defined to create a so called container format.

Make sure that your base 64 decoder is not vulnerable against attack:

Because the base 64 decoding will now happen before the message is authenticated (but this is also the case if the tag is base 64 encoded separately, so yeah, make sure your base 64 codec is secure).

If you decide on using a container format (CMS or your own container format) then please note that attacking the format may expose security issues before the authentication can be verified. Windows famously had such vulnerabilities before user authentication took place. But many crypto related libraries such as OpenSSL and NSS have suffered similar issues.

EDIT: On Jason

You've specified JSON as message format. That's fine, but please note that JSON doesn't have an explicit way to encode binary values. Therefore you would have yourself to define the exact encoding of the binary message in payload, e.g. base 64 as defined here. Otherwise you may run into interop issues (base64url, padding or no padding, line breaks or no line breaks at specific locations, etc.

Furthermore, HMAC takes binary data as input. So that would mean that you'd have to specify the character encoding as well, at least for calculation of the authentication tag. JSON defaults to UTF-8 (which is compatible with ASCII for base 64 encoded values) but it also allows UTF-16 and UTF-32. Note that the encoding of the JSON and the encoding for the HMAC input could differ.

Because of these kind of issues, it is infinitely easier to just calculate the value over the binary value. You don't want to end up with the XML-digsig standard. Of course you'd still have to define the character set for the JSON message and base 64 encoding for the values within it, but at least a single bit wrong won't break your implementation.


Explain Fischlin's Fiat-Shamir like transformation I've been trying for a while to understand why this paper is correct:
ftp://ftp.inf.ethz.ch/pub/crypto/publications/Fischl05b.pdf.

The idea is a NIZK-POK where you require the hash of the commit-challenge-response to be small.
This is supposed to force the prover to make multiple hash queries for each commit, which consequently enables an extractor to extract the witness without having to rewind.
But what I can't figure out - is why not just try multiple witnesses/commits , rather than multiple challenges for a given commit?

I think I got it.
The point, in short, is that you require multiple proofs (commit_i,challenge_i,response_i), where each proof's validity depends on all the first messages commit; i.e., on COMMIT=(commit_1,..,commit_k).
So if the probability of a good proof is 1/l,
if you try to get a good sequence (proof_1,..,proof_k) by complete random sampling (from the space of l-tuples of correct proofs), it will take you in expectation 1/l^k.
But if you fix COMMIT, and try different values of challenge_i,response_i,
it will take you in expectation lk tries.
Taking l to be polynomial and k super-constrant, you can get the first to be super polynomial but not the second.


Vigenère, auto-correlation vs Kasiski examination What are the differences between 'Kasiski examination' and 'auto-correlation' ?

In Cryptool site, they state that autocorrelation analysis is more efficient and clearer than the Friedman or Kasiski test. But, they fail to mention how they achieve this or how they differ from Kasiski.

Kasiski's test only considers repeated sequences of characters, under assumption that the text contains repeated words with distance between them being a multiple of key length.

Autocorrelation analysis simply counts matching characters between shifted ciphertexts. Then you have to identify "maxima", which are shift distances with higher match counts than the others. The assumption here is that the text from the language correlates strongly with itself. This is more general than assuming the existence of long repeated sequences.


Security of basic SHA256 MAC in an authenticate-then-encrypt scheme I know the following construct is insecure if the MAC as defined below is appended to the encrypted message in an Encrypt then Authenticate (EtA) scheme.

$k_1$: encryption key
$k_2$: authentication key
$m_1$: plaintext message
$c_1$: encrypted message (AES-CBC with random iv)
$IV$: from PRNG

where $k_1$ and $k_2$ are independent.

$$MAC = SHA256(m_1 || IV || k_2)$$
$$c1 = AES(k_1, IV, m_1)$$
$$SEND(c1 || MAC)$$

MAC is completely insecure because it is not a proper HMAC as defined by $H((k_1 \oplus opad) || H((k_1 \oplus ipad) || m_1))$.  MAC can be easily compromised by an extension attack since the MAC is in the clear.

However, I am trying to determine if the above MAC becomes secure if it is included in the $c_1$ encryption of an Authenticate-then-Encrypt (AtE) scheme.

$$SEND(AES(k_1, IV, m_1 || MAC))$$

MAC is no longer in the clear and should not be vulnerable to the extension attack.  I am aware of other general attacks on AtE schemes but my specific question is whether including a $MAC=SHA256(m_1 || IV || k_2)$ in the encrypted ciphertext is cryptographically secure for message authentication.

ie: Decrypt $c_1$ using $k_1$, then immediately verify decrypted MAC with $k_2$.

This is an academic question since in practice I would use AES-GCM for authenticated encryption.

Unfortunately your question doesn't fully specify the authenticated-encryption mode. In particular, AES is a block cipher, not a mode of operation, and only operates on plaintexts of some fixed length (128 bits for AES). So you need to fix a mode-of-operation for AES, such as CBC mode or CTR mode. (Never use ECB mode.)

Let's assume you used CBC mode. Then the final Authenticate-then-Encrypt mode you outline is indeed more commonly referred to as MAC-then-Encrypt or MAC-Encode-Encrypt. The latter is a bit more accurate, as it captures the fact that often one needs to encode the concatenation of the message and message authentication tag as a plaintext string that is compatible with the encryption mode of operation. For example, CBC mode only accepts plaintexts that are a multiple of the underlying block cipher's block size (for AES this is 128 bits).

In general MAC-Encode-Encrypt is never recommended for use in modern applications. Why? Because it's near impossible to implement correctly. One must first decrypt, then properly decode, and only then can check the MAC. The first two operations are done before checking authenticity and many clever attacks have shown how to confuse decryption implementations. See Lucky 13 for a recent example, and the included references to padding oracle attacks.


Why do we need Diffie Hellman? Diffie–Hellman offers secure key exchange only if sides are authenticated. For authentication, sides are using public/private key. So if side A knows the public key of the side B, then A can simply use that key to encrypt the message (or the new session key).

Why bother to use separate key exchange algorithm?

I assume you're talking about SSL/TLS or a similar protocol. In these protocols there are two reasons to use Diffie-Hellman:

Your certificate only supports signing
Either it is an RSA certificate restricted to signing, or it uses an algorithm that doesn't support encryption, such as DSA or ECDSA.
Forward security - What happens if the server's private key gets leaked somehow?
If you simply encrypted the session key to the server's public key, all past communication with that server can be decrypted. Which is very bad.
If an ephemeral Diffie-Hellman key-exchange was used, a private key leak won't compromize past communications, since the keys used for the key exchange are long gone, and the leaked long term key was only used for authentication and not for confidentiality.
You don't know the public key of the other side
There are situations where you don't know the other side's public key, but you have a different way to authenticate them. In that case you can use anonymous Diffie-Hellman together with that other way. For example TLS supports authentication based on a symmetric shared secret in a way that's secure against MitM.

Some other protocols such as CurveCP use EC Diffie-Hellman for both authentication and key-exchange. In this case they profit from the performance advantage elliptic curves have over RSA.


How to use HMAC-SHA1, HMAC-SHA2 in conjunction with AES I understand how to compute HMAC-SHA1, HMAC-SHA2 etcetera.

Please explain why/how is the resulting HMAC value is used in conjunction with AES for encryption/decryption and signing/verifying.

In particular:

How does HMAC interact with AES for key sizes (AES-128, AES-196 and AES-256)?
Is the calculated MAC encrypted using AES? And if so, why?
How about signing and verifying? How does the AES cipher play a role here?
Is it correct that the AES ciphertext is HMAC-ed for signing and the HMAC is verified?

Is the calculated MAC encrypted using AES? What is the purpose? How
  about signing and verifying? How does AEs Play a role here? Is the
  case here that the encrypted AES is HMACed for signing and the HMAC is
  verified

No, the MAC is not encrypted per se, however, it is calculated in conjunction with a key (independent of the encryption key).

Simply encrypting your data ensures privacy, however, it doesn't ensure integrity (ie, that the ciphertext hasn't been tampered with since it was encrypted). Using a HMAC provides this integrity.

A simple hash function by itself is not sufficient, as an attacker could alter the ciphertext, calculate a new hash, append it to the new ciphertext, and you would be unable to detect any tampering.  A HMAC solves this problem as it uses a key - meaning that an attacker is unable to create a valid HMAC unless they have a valid key (which only you possess).

You should note that if you plan to encrypt-then-HMAC, you not only need to calculate the MAC of the ciphertext, but also the IV ...ie, HMAC((ciphertext+IV), key)

You should also note that independent keys should be used for the encryption (AES, for example) and the authentication (HMAC).  One approach is to use a masterkey, and then derive two separate keys using a KDF.

Of course, using an authenticated encryption mode such as GCM or EAX is less prone to implementation errors (assuming you're using a well-vetted library), and is recommended if you don't have much experience in crypto.


Raw curve25519 public key points I'm trying to understand curve25519, and ECC public points.

I'm playing with Minisign, to better understand the fundamentals of ECC.

Minisign uses curve25519 and outputs public keys as base64 encoded strings in the following format:

base64(<signature_algorithm> || <key_id> || <public_key>)

  signature_algorithm: Ed

  key_id: 8 random bytes

  public_key: Ed25519 public key

As an example, my public key is:

RWRxmbgCt+0wPvdZ0alM7J46oqsOBTtud4E8zRznnCT0q0u7X971eWUN

Decoding this Base64 to Hex we get:

45 64 71 99 b8 02 b7 ed 30 3e f7 59 d1 a9 4c ec 9e 3a a2 ab 0e 05 3b 6e 77 81 3c cd 1c e7 9c 24 f4 ab 4b bb 5f de f5 79 65 0d

This makes sense... 45 64 == Ed

Next eight random bytes... 71 99 b8 02 b7 ed 30 3e

Then, if I'm correct, the public key... f7 59 d1 a9 4c ec 9e 3a a2 ab 0e 05 3b 6e 77 81 3c cd 1c e7 9c 24 f4 ab 4b bb 5f de f5 79 65 0d

Now this is what I'm trying to understand!

The public key is the right size (32 bytes/256 bits), however isn't it supposed to start with 04?

Also is it possible to take the public key and break it into it's X,Y co-ordinates as integers?

Is 16 bytes enough to represent a curve25519 X or Y component?

Thanks for the help.

(minisign author here)

As noted by corpsfini, keys encode the Y coordinate. The X coordinate is recovered using the curve equation: X = sqrt((Y^2 - 1) / (d Y^2 + 1)).

The square root has two solutions, so we need to encode the sign of x as well. Since coordinates only require 255 bits, we have a extra bit, used to encode the sign.

X and Y ∈ [0; 2^255-19[, so 16 bytes wouldn't be enough to encode them.


Which characters to take into account when calculating unicity distance? I need to calculate the unicity distance of a block cipher. Assuming I know that the plaintext is an English message I considered using 53 as the size of the alphabet, since the message could contain lowercase ans uppercase letters from the english alphabet, as well as whitespace.
Would this be the right way to approach this calculation?

Thanks in advance.

The alphabet size you need to consider, when calculating the unicity distance, is the size of the ciphertext alphabet.  This follows from the definition of unicity distance, as the amount of ciphertext needed to rule out all but one of the keys.*

For a classical cipher that only encrypts letters to letters, and ignores spaces and case distinctions, the alphabet size would be 26 (or possibly less, e.g. if I and J are merged together).
For a cipher that uses exactly the alphabet you described (upper- and lowercase letters and spaces) for both plaintext and ciphertext, the alphabet size would be 2 × 26 + 1 = 53.
For a modern cipher that outputs one 8-bit byte for each plaintext character, the alphabet size would be 256.
For a hypothetical cipher that only outputs 7-bit bytes, the alphabet size would be 128.

Note that, in the formula $U = H_k / D$ for the unicity distance, the per-character redundancy $D$ should really be interpreted as the number of bits of information revealed by one additional ciphertext character.

This can be calculated as the number of bits encoded by one ciphertext character (i.e. as log2(alphabet size), if we assume the ciphertext to have no redundancy), minus the number of bits of entropy per plaintext character, assuming that each ciphertext character decrypts to one plaintext character.  For ciphers where this is not always the case, like the VIC cipher or other fractionating ciphers, things get more complicated.

(Another example of a fractionating cipher would be a modern block cipher in a mode like ECB or CBC that always encrypts or decrypts one full block at a time.  For such ciphers, it's arguably more meaningful to calculate the unicity distance in units of blocks rather than characters.  Of course, you can then convert the result back to, say, bytes, and typically get the same result as if you'd assumed a one-byte block size to begin with.  But you still can't really decrypt a partial block with such a cipher — except by brute force iterating over the missing part of the block, which makes your already slow brute force attack even slower.)

It's also worth noting that the whole concept of a constant "plaintext entropy per character" is somewhat nonsensical, since it's not really fixed — typically, the more plaintext you already have, the easier the next character is to predict (and, thus, the less entropy it carries).  The plaintext entropy also depends strongly on the assumed distribution of plaintexts, and, in practice, on how good the attacker is at recognizing valid plaintexts.  Thus, reasonable estimates for the unicity distance of the same cipher can in fact vary widely, depending what assumptions one makes.

*) In fact, this "casual" definition I gave has a subtle error: for most ciphers, there is no amount of ciphertext that can be guaranteed to rule out all keys but the correct one.  Rather, the usual formula for calculating the unicity distance gives approximately the amount of ciphertext needed to reduce the expected number of false positives (i.e. wrong keys that randomly yield a plausible decryption) to one.

This means that, if you have exactly one unicity distance worth of ciphertext, and try to decrypt it with all keys by brute force, you will, on average, end up with two keys that give a plausible plaintext — one correct key, and, on average, one false positive.  To actually be reasonably sure of getting no false positives at all, you'll need more than one unicity distance of ciphertext.


Is there any pseudorandom function that outputs $n$ prime number of ring $Z_{N}$ where $N$ is Paillier public key Let's assume $N$ is Paillier encryption public key, where $N=pq$ and $p,q$ are strong prime numbers.

I have a set of plaintext $p_i$ whose domain is $N$. I want to deterministically generate a series of pseudorandom values $r_i$ that have multiplicative inverse. So $r_i$ should be distributed uniformly random over $N$ or its subfield.

I want to blind each plaintext as $b_i=p_i\cdot r_i \bmod N$. So given $b_i$ a semi-honest adversary cannot learn anything about $p_i$.

Question: Is there any way to construct a pseudorandom function that outputs uniformly random values over $N$ (or its subfield) and has multiplicative inverse with a high probability?

TL;DR: Any (pseudo-) random value from the desired range has a high chance of being invertible.

To understand this, first remember the criterion for a value $x$ to be multiplicatively invertible in $\mathbb Z_n$: $$\gcd(n,x)=1$$

Now remember how many such values exist, exactly: $$\varphi(n)=(p-1)(q-1)=pq-p-q+1$$

Now assume these non-invertible values are distributed somewhat uniformly over the set of all integers smaller than $n$. Then the chance that a value is invertible is exactly
$$\Pr[x\in \mathbb Z_n:\exists x^{-1}]=\frac{\varphi(n)}{n}=\frac{pq-p-q+1}{pq}=1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq}$$

Now remember that $p,q$ are large (otherwise the encryption could be broken), then $1/p,1/q$ and $1/(pq)$ are negligible and thus the probability of an integer being invertible is nearly 1.

As for constructing such values: Just generate bit strings of the appropriate size and discard them until they fit your limitations (e.g. $\leq n$), usually you will have to discard none or one integers this way.


Why do curve25519 implementations only have ge_frombytes_negate_vartime, and not a regular ge_frombytes method? In every implementation I can find, there is ge_frombytes_negate_vartime but not a regular ge_frombytes method.

I'm assuming there is a deep mathematical reason for things being this way that I'm hoping to uncover.

And since there are no ge_neg methods either, what's the most efficient way to negate the point that is read, in order for it to have the correct sign? Do I need to convert to any particular coordinate space and then manipulate one of the coordinates?

Bernstein only wrote the code required for key-generation, key-exchange and signatures, not a general purpose elliptic curve library. So when an operation is not required for those features it will be missing from the library.

Vartime operations are used during verification as verification does not require side channel resistance.


Why is Ring-LWE based homomorphic encryption secure with one sample? Suppose $R=\mathbb{Z}[X]/f(X)$ is a polynomial ring.

Decisional Ring-LWE is hard if one cannot distinguish the following samples:

$(a_i, b_i) \in R^2$ for $i\in [0,k-1]$ (completely random)
$(a_i, b_i=a_is+e_i) \in R^2$ for $i\in [0,k-1]$ ($b_i$ is obtained by multiplication of $a_i$ and secret $s$ masked by some noise)

This requires $k$ samples.
However in homomorphic encryption scheme, key generation of public key requires just one Ring-LWE sample.

Why is this secure?

The security proofs on the papers about (R)LWE use several samples (usually denoted by $m$) because then the results (and the security guarantees) are stronger. And, anyway, they usually give upper bounds to $m$ (as being at most polynomially big in $n$), but not lower bounds.

For both, the decisional and the search version of the problem, giving less samples can only make the problem harder.

To see that, notice that if an attacker can distinguish the two distributions given only one sample, than it can break (R)LWE with multiple samples by just ignoring $m-1$ samples and distinguishing in the way he/she knows with one sample. And this argument works for any number of samples smaller than $m$ (so, we have a reduction from the (R)LWE problem with $m$ samples to the (R)LWE problem with any $m' < m$ samples).

To be more confident about that, take a look at section 4.1.1 of A Decade of Lattice Cryptography, where Chris Peikert explains why we can ignore columns of the SIS problem. It is basically the same argument to your case.


Are there valid attacks on full SHA-1? Google today announced they are sunsetting SHA-1. Its fine by me. But that made me realize I am not keeping up with the research on SHA-1. The Wikipedia page only says Stevens' attack is the most efficient but its also on a reduced round SHA-1 - not the SHA-1 with the full rounds. So is there no theoretical attack on SHA-1 or is the one I referred to above enough for it to be considered vulnerable? Are there others?

The cost of finding collision for SHA-1 is currently estimated as $2^{61}$ SHA-1 calls. To understand how much  (or how little) it is, we could look at Bitcoin mining. Right now (September 2014) the entire mining network computes 200,000,000 giga-double-hashes of SHA-256 per second, or $2^{61}$ hashes in three seconds.


Why $\alpha$ in ElGamal cryptosystem has to be a primitive root? When choosing the public key for ElGamal, $\alpha$ must be chosen as a primitive mod p. What if $\alpha$ is not a primitive root ? How will it influence the encryption and decryption ?

Everything works, except the key and signature space, reduced greatly;

  The result is that the signature space (when the key is used for     signing) or the public key space (when the key is used for encryption)     may be greatly reduced from its expected size of log(p) bits, possibly     down to 1 bit (the worst case if the order of g is 2)1.

It not hard to detect a $g$ is the generator or not.