As mentioned in the NodeJS doc, in poll phrase, node will block when appropriate. This post will discuss the block conditions and why this phrase blocks as Node should perfom a non-blocking I/O operations.

There are several logics in libuv core.c

First is the uv_run function, which operates the process of entire event loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

int uv_run(uv_loop_t* loop, uv_run_mode mode) {
  int timeout;
  int r;
  int ran_pending;

  r = uv__loop_alive(loop);
  if (!r)
    uv__update_time(loop);

  while (r != 0 && loop->stop_flag == 0) {
    uv__update_time(loop);
    uv__run_timers(loop);
    ran_pending = uv__run_pending(loop);
    uv__run_idle(loop);
    uv__run_prepare(loop);

    timeout = 0;
    if ((mode == UV_RUN_ONCE && !ran_pending) || mode == UV_RUN_DEFAULT)
      timeout = uv_backend_timeout(loop);

    uv__io_poll(loop, timeout);
    uv__run_check(loop);
    uv__run_closing_handles(loop);

    if (mode == UV_RUN_ONCE) {
      /* UV_RUN_ONCE implies forward progress: at least one callback must have
       * been invoked when it returns. uv__io_poll() can return without doing
       * I/O (meaning: no callbacks) when its timeout expires - which means we
       * have pending timers that satisfy the forward progress constraint.
       *
       * UV_RUN_NOWAIT makes no guarantees about progress so it's omitted from
       * the check.
       */
      uv__update_time(loop);
      uv__run_timers(loop);
    }

    r = uv__loop_alive(loop);
    if (mode == UV_RUN_ONCE || mode == UV_RUN_NOWAIT)
      break;
  }

  /* The if statement lets gcc compile it to a conditional store. Avoids
   * dirtying a cache line.
   */
  if (loop->stop_flag != 0)
    loop->stop_flag = 0;

  return r;
}

Fighting the Landlord AI 基于Minimax和MCTS的两种斗地主算法

Requirement

The system must use CBC mode with PKCS7 for the padding block.

This is a chosen-ciphertext attack, The adversary can submit encrypted messages to the system, and the system will return valid or invalid as response. Assume block size is 8.

Background

Previous posts: The TESLA Broadcast Authentication Protocol, Lamport's Hash

Requirements

A Strong Password-Based Protocols should have these requirements:

• Prevent attackers to eavesdrop the conversation on an authentication exchange
• Prevent attackers to obtain any information by impersonating either endpoint
• Prevent attackers to do off-line attack *
• Attackers should not be able to obtain any further information from observing any number of legitimate exchanges
• Ensure forward secrecy

* An attacker impersonating either endpoint will be able to do a single or small amount of on-line password guess, which is unavoidable. However, multiple guesses should generate alarms to the server.

Strong Password Protocols

Encrypted Key Exchange (EKE)

This is the basic form of strong password protocol.

Premise:
A has a weak password (i.e. A and B share a weak secret W derived from password, usually hash(password)).

Approach:
A -> B: W{g^a mod p}
B -> A: W{g_b mod p}, c1
The key K establishment is based on Diffie-Hellman exchange, so K = g^ab mod p
A -> B: K{c1, c2}
B -> A: K{c2 - 1}
The last two steps is to authenticate between A and B by providing challenges c1 and c2.

Does it prevent off-line attack?
Yes. T can only get Diffle-Hellman messages from off-line guessing, which is impossible to derive K. Also, W{g^a mode p} is just a random number. For any password W’ there exist an r such that W’{r} = W{g^a mod p}

How about Forward Secrecy?
It ensures forward secrecy. a, b, K are only used in this session and will be forgotten later on. If T compromises K, T will not be able to get further information in latter communication.
The only information that will not be forgotten is W. However, T still cannot get K with W.(Unless A or B get compromised and a, b is known by T).

Simple Password Expotential Key Exchange (SPEKE)

Approach:
It uses W in place of g in the Diffle-Hellman exchange:

A -> B: w^a mod p
B -> A: w^b mod p

Where K = w^ab mod p

Password Derived Moduli (PDM)

Approach:
It uses a modulus p which is a function of the password. And uses 2 as the base:

A -> B: 2^a mod p
B -> A: 2^a mod p

Where K = 2^ab mod p

Flaws and Attacks

In EKE

If p is only a little more than a power of 2, for example, p = 2^k+i for small i.
Since g^a mod p < p. A eavesdropper can try guessing the password, if the password is correct, the result will definitely less than p, if it is not correct, the result will fall randomly between [0, 2^k+1-1]([0, p+p-1]). The attacker will know the result is incorrect if it is larger than p.
The changes of getting a correctly password will be (2^k+i)/2^b, which is almost 50%.
To eliminate this flaw, we need to choose a p which is a little less than a power of 2.

In SPEKE

The eavesdropper might be able to eliminate some pasword guesses based on seeing w^a mod p. If some of the Ws generated from passwords for use in SPEKE were perfect squares and some not, then if w^a mod p was not a perfect square, the attacker could know none of passwords resulted in Ws that were perfect square could have been A’s password.
To check if a number w=x² mod p is a perfect square mod p, we can do w^(p-1)/2 mod p. If the result is 1 mod p, then it is a perfect square.

To eliminate this problem, we simply need to ensure every w is a perfect square mod p.

Augmented Strong Password Protocols

Goal: If an attacker T compromises B, T cannot succeed with an offline attack

Approach: Avoiding storing W in B’s database but only something derived from W.

Requirement: The password must be strong so that the off-line attack will not succeed.

Augmented PDM

1. B stores A, p, 2^w mod p (p is derived from password)
2. A -> B: 2^a mod p
3. B -> A: 2^b mod p, hash(2^ab mod p, 2^bw mod p)
4. A -> B: hash’(2^ab mod p, 2^bw mod p) (this hash’ is for B to authenticate A)

Note that it is not possible for attacker T to do this:
T impersonate A, sends 2^k mod p to B. T gets 2^b mod p and hash(2^kb mod p, 2^bw mod p) from B, then do offline attacks by trying different w.

Because p is derived from password, so B will recognize it’s not a valid message.

Augmentation Based on RSA Public Keys

1. B stores A, W, {A}(A’s public key), Y=W’{[A]}(A’s private key)
2. A -> B: A, W{g^a mod p}
3. B choose b and challenge c
4. B -> A: W{g^b mod p}, ((g^ab mod p)){Y}
5. A -> B: [hash(g^ab mod p, c)]_sign-A

Note that if T breaks into B, T can get W, but T cannot get W’

Secure Remote Password (SRP)

1. B stores A, g^w mod p
2. A choose a, compute W from password
3. A -> B: A, g^a mod p
4. B choose b, c1 and a 32-bit number u
5. B sends g^b+g^w mod p, u, c1
   (K = g^b(a+uW) mod p)
6. A -> B: K{c1}, c2
7. B -> A: K{c2}

** How is the common key computed on both ends? **
For A: g^b+g^w mod p - g^w mod p = g^b
Then (g^b)^(a+uw) mod p
For B: (g^a)^b*(g^w)^bu mod p

Previous post: Lamport's Hash.

Approach

• Sender A splits time into intervals of equal duration I.
• A forms a one-way chain of self-authenticating values X_n, assign the values sequentially. The one-way chain is used in the reverse order of generation, so any value of a time interval can be used to derive values of previous time intervals.
• A defines a disclosure time for one-way chain values. A will publish the value after the disclosure time. For example, on time interval i, A publish X_n-(i-1).
• A attaches MAC to each packet, and use the key on that time interval to compute MAC: MAC(M_i, X_n-i)(on time i). A also sends the value it can disclose.
• When B receives the packet, it checks that A has not disclose the value X to make sure the key is still secret. Then B buffers the packet.
• B also checks the disclosed value is correct and verify MAC of this packet(base on time interval). If MAC is correct. B accept the packet.

One-Way Chains

Any value of a time interval can be used to derive values of previous time intervals.
So even if some disclosed keys are lost, B can still recover the key chain.

Requirements

• Receivers should be loosely time synchronized with the sender.
• Either receiver or senders must buffer some messages.

Advantages

• Low communication overhead (and for generation and verification of authentication information)
• Limited buffering required for the sender and the receiver, hence timely authentication for each individual packet
• Robustness to packet loss
• Scales to a large number of receivers
• Low authentication delay

Source: The TESLA Broadcast Authentication Protocol