Linux에서 비밀번호 해싱의 6번째 문자는 무엇입니까? 왜 보통 슬래시입니까?

해시 형식 및 소스

비밀번호 해시의 형식은 SHA-256 기반 해시입니다 $<type>$<salt>$<hash>. <type> 5Salt는 일반적으로 길이가 8자 이상이므로(질문의 예에서는) 여섯 번째 문자가 Salt의 일부입니다.

이 해시는 아마도 다음 버전에 의해 생성되었을 것입니다.그림자 도구 키트(소스 패키지shadow데비안에서는shadow-utilsCentOS에서)

코드가 슬래시 쪽으로 편향된 이유가 정확히 무엇인지 알아내려고 노력 중입니다. (원래 코드를 파헤친 @thrig에게 감사드립니다.)

요약: 좀 웃기긴 하지만 괜찮아요.

---

소금을 생성하는 코드

루프에서 호출되는 함수를 libmisc/salt.c찾습니다 .gensaltl64a

strcat (salt, l64a (random()));
do {
       strcat (salt, l64a (random()));
} while (strlen (salt) < salt_size);

루프는 그것으로부터 임의의 숫자를 가져와 random()문자열의 일부로 변환하고 솔트를 형성하는 문자열에 연결합니다. 충분한 문자가 수집될 때까지 반복합니다.

하지만 일어난 일은 l64a훨씬 더 흥미로웠습니다. 내부 루프는 (에서) 입력 값을 기반으로 random()한 번에 한 문자를 생성합니다 .

for (i = 0; value != 0 && i < 6; i++) {
    digit = value & 0x3f;

    if (digit < 2) {
        *s = digit + '.';
    } else if (digit < 12) {
        *s = digit + '0' - 2;
    } else if (digit < 38) {
        *s = digit + 'A' - 12;
    } else {
        *s = digit + 'a' - 38;
    }

    value >>= 6;
    s++;
}

루프( digit = value & 0x3f)의 첫 번째 줄은 입력 값에서 6비트를 선택하고, 절은 if이러한 값으로 구성된 값을 문자로 변환합니다. ( .0, /1, 02 등)

l64aa를 허용 long하지만 출력 값은 glibc에서 2147483647 또는 2^31 - 1로 보이는 로 random()제한됩니다 . RAND_MAX따라서 전송되는 값 l64a은 31비트 난수입니다. 한 번에 6비트 또는 31비트 값을 사용하면 합리적으로 균등한 간격의 문자 5개와 단 1비트에서 6번째 문자를 얻을 수 있습니다!

그러나 생성된 마지막 문자는 루프에도 조건이 있기 때문에 l64aa가 될 수 없으며 a는 여섯 번째 문자 가 아닌 5개의 문자만 반환됩니다. 따라서 절반의 경우 6번째 문자는 이고 나머지 절반은 5자 이하를 반환합니다. 후자의 경우 후속 문자 도 첫 번째 위치에 슬래시를 생성할 수 있으므로 전체 솔트에서 여섯 번째 문자는 절반 이상 슬래시여야 합니다..value != 0.l64a/l64al64a

코드에는 솔트의 길이(8~16바이트)를 무작위로 지정하는 기능도 있습니다. 슬래시 문자의 동일한 편향은 추가 호출에서도 발생하므로 l64a11번째 및 12번째 문자에도 다른 문자보다 슬래시가 더 자주 사용됩니다. 문제에 제시된 100개의 솔트에는 6번째 위치에 46개의 슬래시가 있고, 11번째 위치와 12번째 위치에 각각 13개와 15개의 슬래시가 있습니다. (솔트의 절반 미만이 11자보다 짧습니다.)

데비안에서

데비안에서는 chpasswd질문에 표시된 직선으로 이것을 재현할 수 없습니다. 그러나 chpasswd -c SHA256동일한 동작을 나타냅니다. 매뉴얼에 따르면 기본 작업( 없이 -c)은 PAM이 해시를 처리하도록 하는 것이므로 데비안의 PAM은 최소한 다른 코드를 사용하여 솔트를 생성합니다. 그러나 나는 어떤 배포판에서도 PAM 코드를 살펴보지 않았습니다.

(이 답변의 이전 버전에서는 이 효과가 데비안에 나타나지 않는다고 명시했습니다. 이는 올바르지 않습니다.)

소금의 의미와 요구사항

하지만 그게 중요할까요? @RemcoGerlich가 언급했듯이 이는 코딩 문제일 뿐입니다. 솔트의 일부 비트를 0으로 효과적으로 수정하지만 해당 비트의 출처가 in 에 대한 srandom호출 이므로 이 경우에는 큰 영향을 미치지 않을 것입니다 seedRNG.

srandom (tv.tv_sec ^ tv.tv_usec ^ getpid ());

이는 현재 시간에 RNG를 시드하는 고대 관습의 변형입니다. ( tv_sec그리고 실행 중인 프로세스인 경우 프로세스 ID를 제공하는 tv_usec현재 시간의 초와 마이크로초입니다 getpid().) 시간과 PID는 예측할 수 없는 것이 아니므로 여기서 임의성의 양은 인코딩이 수용할 수 있는 것보다 크지 않을 것입니다.

시간과 PID는 당신이 만들고 싶은 것이 아닙니다열쇠하지만 소금으로는 예측할 수 없습니다. 염류~ 해야 하다단일 계산으로 여러 비밀번호 해시에 대한 무차별 대입 테스트를 방지하는 것은 다르지만~해야 한다또한 예측할 수 없는 대상 사전 계산을 방지하거나 속도를 늦추는데, 이는 비밀번호 해시를 가져오는 데서 실제 비밀번호를 가져오는 데 걸리는 시간을 단축하는 데 사용할 수 있습니다.

사소한 문제가 있더라도 알고리즘이 서로 다른 비밀번호에 대해 동일한 솔트를 생성하지 않는 한 괜찮습니다. 질문의 목록에서 알 수 있듯이 루프에서 수십 개를 생성해도 작동하지 않는 것 같습니다.

또한 문제의 코드는 비밀번호 솔트 생성 이외의 용도로 사용되지 않으므로 다른 곳에서는 문제에 영향을 미치지 않습니다.

소금에 대해서는 다음을 참조하세요.이것은 스택 오버플로에 있습니다그리고보안에 대해. SE.

결론적으로

결론은 시스템에는 문제가 없다는 것입니다. 비밀번호가 양호하고 관련 없는 시스템에서 사용되지 않는지 확인하는 것은 고려할 가치가 있는 것 이상입니다.

매뉴얼에 따르면 이 문자는 salt 의 일부입니다 crypt(3). 솔트의 길이( $5$ID와 뒤에 오는 문자열 $)가 표시된 해시 값에 따라 달라지므로 몇 가지 비밀번호에 대해 해당 특정 열에서 임의의 문자를 선택하는 것이 무엇인지 잘 모르겠습니다.

반면에,/ 예(102개 인스턴스)에서 더 일반적임모두소금의 특정 캐릭터는 다른 가능한 캐릭터(약 18개)에 비해 chpasswd소금의 해당 캐릭터를 선호하는 것 같습니다 .

for x in `seq 1 100000`; do
  echo testacct:asdfasdfasdf | chpasswd -c SHA256
  awk -F: '/testacct/{print $2}' /etc/shadow | awk -F\$ '{print $3}' >> salts
done
perl -nle 'print for m/(.)/g' salts | sort | uniq -c | sort -nr | head -5

RedHat EL 6 시스템에서 실행하면 다음이 나타납니다.

   1006 /
    195 X
    193 U
    193 q
    193 e

예, 의 코드에는 사전 공격을 더 쉽게 만들 수 있는 편향이 있습니다 shadow-utils-4.1.5.1-5.el6./

#include <sys/time.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

// these next two borrowed from libmisc/salt.c of shadow-4.1.5.1 from
// Centos 6.8 RPM at http://vault.centos.org/6.8/os/Source/SPackages/shadow-utils-4.1.5.1-5.el6.src.rpm
char *l64a(long value)
{
    static char buf[8];
    char *s = buf;
    int digit;
    int i;

    if (value < 0) {
        abort();
    }

    for (i = 0; value != 0 && i < 6; i++) {
        digit = value & 0x3f;

        if (digit < 2) {
            *s = digit + '.';
        } else if (digit < 12) {
            *s = digit + '0' - 2;
        } else if (digit < 38) {
            *s = digit + 'A' - 12;
        } else {
            *s = digit + 'a' - 38;
        }

        value >>= 6;
        s++;
    }

    *s = '\0';

    return (buf);
}

static void seedRNG(void)
{
    struct timeval tv;
    static int seeded = 0;

    if (0 == seeded) {
        (void) gettimeofday(&tv, NULL);
        srandom(tv.tv_sec ^ tv.tv_usec ^ getpid());
        seeded = 1;
    }
}

int main(void)
{
    seedRNG();
    for (int x = 0; x < 1000; x++) {
        printf("%s\n", l64a(random()));
    }

    exit(0);
}

결과 :

% ./salttest | perl -nle 'print for m/(.)/g' | sort | uniq -c | sort -nr | head -3
 593 /
  96 8
  93 3

그런 다음 최신 동일한 루틴을 사용하십시오.https://github.com/shadow-maint/shadow/blob/master/libmisc/salt.c우리는 편견이 여전히 존재한다는 것을 발견했습니다 /. 그래서 어, 예, 이것은 패치되어야 하는 버그이므로 /이상적으로는 솔트 문자가 동일한 가중치를 가져야 하기 때문에 덜 선호됩니다.

mkpasswd(1)의 프런트엔드일 수 있지만 CentOS의 "shadow-utils" 패키지와 Debian의 "passwd" 패키지의 일부인 를 crypt(3)실행하는 것과는 다릅니다 . chpasswd(1)대신 사과를 사과와 비교해야 합니다. 다음 스크립트를 고려해보세요.

#!/bin/bash

# This repeatedly changes a `saltuser' password
# and grabs the salt out of /etc/shadow.
# Requires root and the existence of `saltuser' user.

if [ $EUID -ne 0 ]; then
    echo "This script requires root access to read /etc/shadow."
    exit 1
fi

grep -q saltuser /etc/passwd

if [ $? -ne 0 ]; then
    echo "This script requires the 'saltuser' to be present."
    exit 2
fi

: > /tmp/salts.txt

for i in {1..1000}; do
    PW=$(tr -cd '[[:print:]]' < /dev/urandom | head -c 64)
    echo "saltuser:${PW}" | chpasswd -c SHA256 -s 0 2> /dev/urandom
    awk -F '$' '/^saltuser/ {print $3}' /etc/shadow >> /tmp/salts.txt
done

while read LINE; do
    # 6th character in the salt
    echo ${LINE:5:1}
done < /tmp/salts.txt | sort | uniq -c | sort -rn

Debian Sid의 출력:

512 /
 14 T
 13 W
 13 v
 13 t
 12 x
 12 m
 12 d
 11 p
 11 L
 11 F
 11 4
 10 s
 10 l
 10 g
 10 f
 10 7
 10 6
  9 Z
  9 w
  9 N
  9 H
  9 G
  9 E
  9 A
  8 Y
  8 X
  8 r
  8 O
  8 j
  8 c
  8 B
  8 b
  8 9
  7 u
  7 R
  7 q
  7 P
  7 M
  7 k
  7 D
  6 z
  6 y
  6 U
  6 S
  6 K
  6 5
  5 V
  5 Q
  5 o
  5 J
  5 I
  5 i
  5 C
  5 a
  5 3
  4 n
  4 h
  4 e
  4 2
  4 0
  4 .
  3 8
  3 1

CentOS 7 출력:

504 /
 13 P
 13 B
 12 s
 12 Z
 11 e
 11 Y
 11 O
 11 L
 11 G
 10 w
 10 u
 10 q
 10 i
 10 h
 10 X
 10 I
 10 E
  9 x
  9 g
  9 f
  9 W
  9 F
  9 C
  9 9
  9 8
  8 v
  8 t
  8 c
  8 b
  8 S
  8 H
  8 D
  8 0
  7 z
  7 y
  7 o
  7 k
  7 U
  7 T
  7 R
  7 M
  7 A
  7 6
  7 4
  7 1
  6 p
  6 d
  6 a
  6 Q
  6 J
  6 5
  6 .
  5 r
  5 m
  5 j
  5 V
  5 3
  5 2
  4 n
  4 l
  4 N
  4 K
  3 7

따라서 이 문제는 CentOS에만 국한된 것이 아니라 두 프로젝트가 모두 상주하는 업스트림에서 발생할 가능성이 높습니다.