Computing desk
< July 29	<< Jun \| July \| Aug >>	July 31 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 30

Precomputing sums

I have two sorted lists of numbers, A and B, of different sizes. Given a query number y from A, I want to compute the sum of numbers from B that are less than or equal to y. What's the fastest way to precompute this for all x in A? I can do it by iterating over both lists (Python):

result = {}

for y in A:
    result[y] = 0

for x in B:
    for y in A:
        if x <= y:
            result[y] += x

but I feel like there's a better way than O(n^2). 24.255.17.182 (talk) 00:17, 30 July 2016 (UTC)[reply]

I don't know Python but here is quick untested pseudocode:

y = first(A)
sum = 0

for x in B
  if x <= y
    sum += x
  else {
    result[y] = sum
    if A has ended
      exit loop
    else
      y = next(A)
  }

for each remaining y in A
  result[y] = sum

PrimeHunter (talk) 01:01, 30 July 2016 (UTC)[reply]

Well, it had the right idea but may need work on the details. Below is another try. PrimeHunter (talk) 01:59, 30 July 2016 (UTC)[reply]

y = first(A)
sum = 0

for x in B
  while x > y {
    result[y] = sum
    y = next(A)
  }
  sum += x

for each remaining y in A
  result[y] = sum

Thank you, I believe that works perfectly. 24.255.17.182 (talk) 02:04, 30 July 2016 (UTC)[reply]

Can a router log MACs or even wrong passwords of clients trying to connect to it without success?

Can a router log MACs or even wrong passwords of devices trying to connect to it without success?Hofhof (talk) 13:22, 30 July 2016 (UTC)[reply]

No, but it can log estabishing sessions by time. iptables can lock hosts from brute-force attacks from a single host. --Hans Haase (有问题吗) 18:08, 30 July 2016 (UTC)[reply]

Hans, I know that a logbook can log sessions. I just wonder whether routers could log everything else. And if not, why. Alternatively, could a computer being used as a router offer this possibility? Hofhof (talk) 18:13, 30 July 2016 (UTC)[reply]

(edit conflict) You can easily log the claimed MAC, but the device can lie about that (see e.g. [1]); it would not be wise to lock out users based on the MAC address, because a clever attacker will simply wait and see which MAC addresses are in genuine use and claim to originate from these addresses. As for the password, the short answer is "no", if we are talking about a Wi-fi router configured with Wi-Fi_Protected_Access.

The protocol was designed so that neither the client nor the access point has to disclose the password yet prove they possess it. It is obvious why the client should prove it knows it; on the AP side, the intent is to avoid an "evil twin" advertising itself as the AP to recover the password. The result is that (in theory) neither of the two can access a password, even a wrong one.

In practice, there are two ways to connect to a WPA router. One is through a four-way handshake, during which the AP sends a random string ("nonce") to the client and demands that the client encrypts it with the password. If the password is reasonably long/good enough, one cannot recover an unknown password from the result that the client sends.

The other way is to use WPS, which has a well-known vulnerability. It is mostly known for allowing brute-forcing of the PIN by the client (under some assumptions), but it also allows the AP to recover the first half of the entered PIN (and the second half after another try). The following is not too technical and explains the thing well: [2].

So, if we are talking about PIN-connections, the AP can store the first half of the PIN assuming a bit of calculations (bruteforcing in a search space of 10,000). Tigraan^{Click here to contact me} 18:21, 30 July 2016 (UTC)[reply]

So, and back then when WEP was the norm, could an evil twin just pretend to be the AP and capture passwords?

BTW, I think the WPS search space is 11,000. That is, 0000-9999 + 000-999 (one digit is just a control digit).Llaanngg (talk) 18:34, 30 July 2016 (UTC)[reply]

Yes, but WEP was poorly designed and was totally broken in 2001, so you can just sit there and passively capture all traffic without even spoofing an AP. It's effectively equivalent to no encryption. --71.110.8.102 (talk) 04:28, 1 August 2016 (UTC)[reply]

11,000 is for the full PIN, that is the number for online attack of the AP by the client. I mentioned 10,000 as the number for offline attack of the first half by the AP. The AP cannot recover the two halves of the PIN from the client without disclosing one half and the client accepting it, so you cannot log a full (unknown) PIN in a single connection attempt anyways.

The most important thing though is that it is an offline attack. A client that tries to authenticate has no way to detect an evil twin before having released enough info that the evil twin can compute the first half without any further communication. If an AP realizes some client is attacking via WPS brute force, it can rate-limit the number of attempts or lock down WPS entirely so that 11k tries takes a very long time to try; but even 10^7 calculations would not be really that big a hurdle for a rogue AP. Tigraan^{Click here to contact me} 08:18, 1 August 2016 (UTC)[reply]

"…could a computer being used as a router…"? Yes, the IP Stack ist used on several devices. Routers are small computers, often based on Linux. Moving the Log to another computer, not connected to the network, the log can not be maniputated. A serial port used by TTY is a good idea. Setting up Linux as a router. Two NICs are useful, but using VLANs not necessary, Win 10 still is depending on the NIC manufacturer. For Raspberry Pi a router solution is avail, sometimes as Onion Router, the Banana Pi is opimized for use as router. There are ehternet ports only, no calbe or DSL modems, not outdated ISDN or analog phone modem, using PPP to establish a dialup connection. DSL is using PPPoE. Googling for linux as a router gives lots of results. DHCP server and DNS Server are needed to install, Proxy for furter firewall functionality is optional. --Hans Haase (有问题吗) 14:30, 3 August 2016 (UTC)[reply]