[2025-09-07] Onions Got Puzzled

🦥 본문

Tor network

정의 및 개념

익명 네트워크. relay라는 일련의 서버들을 통해 라우팅.

Tor network의 onion system은 .onion 주소를 통해 익명성을 유지하고 Tor network를 통해서만 접근 가능.

동작 흐름

1. 서비스 Tor network의 릴레이 중 몇몇을 연결하여 자신이 접속 받을 수 있는 지점인 IP를 생성
2. 서비스 디스크립터에 IP을 포함하여 자신의 정보를 포함시키고 Tor network의 디렉토리 서버에 게시
3. 클라이언트는 접속하려는 서비스를 디렉토리 서버에서 조회
4. 클라이언트는 서비스 디스크립터를 통해 해당 서비스의 IP 목록과 정보들을 획득
5. 클라이언트는 클라이언트와 서비스가 익명으로 만날 RP 선택하고 서킷을 설정
6. 클라이언트가 IP를 통해 해당 RP의 서킷을 설정하자는 intro-request를 보냄
7. intro-request를 받은 서비스는 RP까지 서킷을 설정하고 해당 RP에서 데이터를 주고 받음

Intro-Flooding

정의 및 개념

• 많은 Intro-request를 보내a서 많은 RP에 많은 서킷을 설정하게 하는 DoS 공격 전략.

  Dos : Denial of Service로 정상 사용자들이 서비스를 이용하지 못하게 만드는 공격.

대응 방법 및 한계

• Source-based filtering : 의심되는 source를 밴하거나 스크러빙 서비스를 통한 트래픽 리디렉션

  스크러빙 서비스 : 트래픽을 분석하고 정상적인 요청과 비정상적인 요청 구분

  한계 : 익명성 때문에 다른 두 소스를 구분할 수 없음

• Replication-based 완화 정책 : 복제를 통한 서비스 과잉 공급 방법

  한계 : onion 서비스의 익명성과 탈중앙화으로 인해 힘듦. 수평적 확장 방식 역시 DoS를 공격을 받으면 IP에 접근하는 게 불가하다는 점과 복제의 최대량이 제약된다는 점에서 힘듦.

• Source testing : CAPTCHA와 같은 방식으로 클라이언트를 테스트하여 사람과 봇을 구별

  한계 : RP 서킷이 설립한 후에 CAPTCHA를 해야 하기 때문에 intro-flooding을 막지 못함

→ Tor network의 익명성으로 인해 많은 제약이 발생하여 비효율적이거나 불가능한 방식

Client-puzzle

정의 및 개념

클라이언트는 서버가 제공하는 암호 퍼즐을 풀어야 서비스를 받을 수 있는 방식으로 공격자는 공격을 발생하기 위해서 많은 자원을 써야 하지만 방어자는 최소한의 노력만 하면 되는 proof-of-work 아이디어에서 고안.

특징

각 퍼즐은 특정 파라미터와 선행 계산 공격을 막는 시드를 포함. 시드가 변경되면 이전의 유효한 정답들은 무효화. 퍼즐을 받자마자 클라이언트는 유효한 답을 찾기 위해 반복적으로 암호 작업을 수행, 반면에 서버는 아주 효율적으로, 적은 노력으로 제시된 해답을 증명.

정상 사용자에게 타당하지 않고 사소하지 않은 부담을 준다는 것 때문에 널리 사용되지 않았지만 Tor network에서는 연결 설립하는 데 오래 걸리기 때문에 사소한 부담.

장점

1. ASIC 저항 : Application-Specific Integrated circuits. 퍼즐 해결을 위한 반도체. 일반 사용자와는 불공정한 이점을 갖고 있음.

   새로운 시드를 위한 내부 로직을 랜덤화하는 해시 함수가 있음. ASIC는 특정 연산만을 빠르게 연산하는 고정된 로직을 가지는 데, 내부 로직을 바꿔서 ASIC를 완화함.

2. 메모리 요구사항

   상당한 RAM 작업을 요구. 퍼즐을 목적으로한 특수 하드웨어는 RAM이 제한적. 그렇기 때문에 사용자와 특수 하드웨어 사용자와의 성능 격차를 줄임

3. 선형적 난이도 증가

   전통적인 것은 지수적 증가. 선형적으로 증가하여 난이도를 세밀하게 조정할 수 있음. 불필요한 난이도 증가는 일반 사용자의 불편을 초래하는데, 적당한 난이도 조정으로 일반 사용자는 놔두고 공격에는 대응

동작 흐름

1. 클라이언트가 퍼즐의 난이도를 선택. 기본적으로 서비스에서 제안되는 난이도.
2. 클라이언트가 퍼즐을 풀고 intro-request를 보냄.
3. 서비스는 답이 맞는 지 확인하고 intro-request를 난이도에 따른 우선 순위 큐에 추가
4. 서비스는 요청을 꺼내서 RP에 대한 서킷을 설립

DUA

우선 순위 큐 상태에 기반한 난이도 업데이트 알고리즘. 즉, 혼잡 상태를 감지하여 난이도 조절. 난이도는 업데이트 라운드가 끝날 때마다 주기적으로 갱신. AIMD 방식.

• 알고리즘
  • 난이도 증가 : 평균 난이도와 (기존 제안된 난이도 + 1) 중 큰 값으로 선택
    • 버려진 요청의 난이도가 현재 난이도가 큰 경우
    • 혼잡 상태이고 큐에 더 높은 난이도 요청이 남아 있는 경우
  • 난이도 감소 : 기존 제안된 난이도 x 2/3
    • 요청의 수가 특정 기준치 (16 or 63)보다 낮아지는 경우
  • 난이도 유지
    • 위의 경우가 아닌 나머지의 경우

• 실험 내용 : X축은 사용자 대기 시간. Y축은 서비스를 이용한 클라이언트의 비율

  

  퍼즐 시스템이 공격으로 인한 대기시간을 줄여준다는 점에서 intro-flooding 공격을 완화시킴을 보임

ONIONFLATION

정의 및 개념

난이도를 부풀리는 공격. 공격 트래픽 볼륨과 퍼즐을 풀 때 필요한 리소스를 최소화.

종류

1. END-RUSH ATTACK : 제안된 난이도 이상의 처리되지 않은 요청을 남겨 퍼즐 난이도를 부풀리는 공격(=small burst of intro-reqs)
   • 동작 흐름
     1. 디렉토리 서버에서 디스크립터를 빈번하게 가져와서 다음 업데이트의 타이밍 정보 획득
     2. 높은 난이도의 퍼즐을 푼 요청을 업데이트 주기 막바지에 보냄
     3. 처리되지 않은 높은 난이도의 퍼즐을 푼 요청이 남게 되어 난이도가 부풀려짐
2. Temporary-turmoil : 퍼즐의 난이도를 계산하는 알고리즘을 악용하여 난이도를 부풀리는 공격 (=short burst of intro-reqs)
   • 동작 흐름
     1. 많은 쉬운 intro-reqs를 보냄
     2. 서비스는 혼잡 상태를 감지하여 난이도를 증가시키려고 함
     3. 난이도의 평균은 모든 추가된 난이도의 합 / 처리된 요청의 수로 처리된 요청에 비해 큰 추가된 난이도의 합이 난이도를 부풀림
3. Choking : 앞선 전략들을 통해 공격 후 추가적으로 서비스의 용량을 줄이는 공격
   • 동작 흐름
     1. END-RUSH ATTACK, Temporary-turmoil을 통해 난이도를 부풀림
     2. 제안된 난이도가 Cli-side 최대 난이도를 넘었을 때 RP를 제한
     3. 공격자가 더 높은 난이도의 요청을 보내고 RP를 half open
        • half open : 클라이언트가 RP에서 연결을 끝까지 완료하지 않음
     4. 제한된 RP을 공격자가 일시적으로 붙잡고 있어서 정상적인 요청이 처리되지 못하게 함
4. Maintenance : 난이도를 부풀리고 난이도를 유지하는 공격
   • 동작 흐름
     1. END-RUSH ATTACK, Temporary-turmoil을 통해 난이도를 부풀림
     2. 0-난이도 요청을 여러 개 보냄
     3. 큐에 기준치의 요청을 남겨 난이도를 유지

→ 라이브 서버에서 해당 공격들 실험 → 엄청난 난이도 상승과 요청 처리 평균 시간이 증가함

대응 방법 및 한계

• DUA 매개 변수 조정
  • 매개 변수 조정 방법
    1. 트리밍과 혼잡 플래그의 극단적인 임계값 설정을 통해 트리밍 빈도를 낮춤.
    2. 업데이트 라운드 시간을 랜덤화
    3. 난이도 조정 빈도를 늘림
    4. 퍼즐 난이도를 증가시키는 새로운 공식 : 추가된 난이도의 합/인큐된 요청의 갯수
    5. 제안된 난이도 상승을 제한

  • 비용 (공격을 저지할만큼 많이 오르지는 않음)

    

    (‡)는 유지 보수 전략의 시간 당 비용, T2는 효과적으로 end-rush를 막아서 추정 비용 생략

    1번째 전략은 공격을 막는 데 충분하지 않음 + 공격자가 난이도 상승 없이 큰 스케일의 DoS 공격을 수행하게 함. → 다른 조정 방안과 결합X. 독립적인 조정 방안으로 사용

    2번째 전략은 end-rush를 효과적으로 막음. the temporary-turmoil은 남아 있음

    3번째 전략은 난이도 유지하는 데 비용을 추가하지만 불충분

    4번째 전략은 the temporary-turmoil 비용을 증가 시키지만 불충분.

    5번째 전략은 난이도를 극단적으로 올리는 데 걸리는 시간이 늘어났지만 불충분.

한계 : 공격자의 비용이 크게 증가하지 않음

• puzzle-auction model : 클라이언트가 독립적으로 이전 요청의 결과를 베이스로 퍼즐 난이도 조절. 요청이 처리되지 않은 경우 클라이언트가 퍼즐 난이도(bids)를 높임
• challenge-response model : 서버가 요청을 받을 때마다 각 클라이언트에게 개별적으로 지정된 난이도의 새로운 퍼즐을 할당. 서버가 완전히 통제 가능

한계 : Tor network는 느리기 때문에 즉각적인 피드백을 제공하지 못함. 익명성 때문에 개별화된 피드백을 주지 못하기 때문에 글로벌 공지를 해야 하지만 real-time broadcast 서비스를 지원하지 않기 때문에 공통된 퍼즐 난이도를 느리고 드물게 공지

상충 관계

inflation과 congestion의 상충 관계. inflation에 저항성이 있다면 congestion에 취약하고 congestion에 저항성이 있으면 inflation에 취약

• 보안 분석 및 공식

  보안 분석

  low-level을 추상화한 high-level에 초점을 맞춘 추상 모델

  정의 1 : 공격자 A는 인트로 요청 burst를 통해 공격. α는 (공격 기간/라운드 길이)의 비율. Datt[t]는 A가 라운드 t에서 해결하는 퍼즐의 난이도

  정의 2 : 서비스 S는 우선 순위큐에서 디큐 하여 인트로 요청 처리. 최대속도는 초당 µmax. S는 주기적으로 저번 업데이트 큐 상태 기반으로 Dsug를 브로드캐스트. Dsug[t]는 라운드 t의 제안 난이도. 함수 β(α)는 DUA 모델

  \[0 ≤ β(α) = Dsug[t]/ Datt [t −1] ≤ γ\]

  정의 3 : DUA의 혼잡 저항은 다음과 같이 정의

  \[\int_{0}^{1} β(α)\, dα\]

  이 값이 γ에 가까워지면 DUA는 높은 혼잡 저항성을 가짐. α가 0에 가까워지면 S는 제안된 난이도가 증가한다는 것.ㅋㄴ βr−c(α)는 가장 혼잡 저항적인 DUA

  \[\beta_{r-c}(\alpha) = \begin{cases} 0 & (\alpha = 0) \\ \gamma & (\alpha > 0) \end{cases}\]

  정의 4 : DUA의 인플레이션 저항성은 다음과 같음

  \[\int_{0}^{1} \left( \gamma - \beta(\alpha) \right) d\alpha\]

  γ에 가까줘지면 DUA는 높은 인플레 저항성이 있는 것. 아래가 가장 인플레 저항성이 있는 DUA

  \[\beta_{r-i}(\alpha) =\begin{cases}0 & (\alpha < 1) \\\gamma & (\alpha = 1)\end{cases}\]

  가정 : µmax 속도로 공격을 보냄. α 와 Datt 값을 사용하여 공격 강도 조정. β(α)는 단조 증가 α = 0일 때 0에서 시작하여 α = 1 일 때 γ에 도달

  보조 정리

  1. 근본적인 상충 관계 : 완벽한 반비례 관계
  2. 혼잡 저항 DUA의 취약점 : 인플레이션 공격에 취약
  3. 인플레이션 저항 DUA의 취약점

  → 결국 혼잡 공격과 인플레이션 공격에 동시에 저항 불가

해결 알고리즘 및 실험 결과

혼잡 징후 대신 전체적인 요청 처리 속도를 모니터링하여 직관적인 난이도 조절 가능. 목표 요청 처리율과 실제 요청 처리율 사이의 불일치에 의해서 결정

• 알고리즘

    Algorithm 2 New Difficulty Update Algorithm
     parameter:
     µtarget: The target dequeue rate that the service aims to maintain.
     δ: The adjusting parameter, with a default value of 1.
     Suggested puzzle difficulty
     state:
     Dsug[n]: The suggested puzzle difficulty at round n.
     ∑Dhandled[n]: The sum of all puzzle difficulties of handled re
    quests during round n.
     rendhandled[n]: The number of handled requests during round n.
     update:
     at the end of each update round,
     1: µadjust[n] ← rendhandled[n]/Tround×δ where Tround is round duration
     2: Dhandled[n] ← ∑Dhandled[n]/rendhandled[n]
     3: if Dhandled[n] = 0 and µadjust[n] > µtarget then
     4: Dsug[n+1] ←8
     5: else
     6: Dsug[n+1] ← µadjust[n]
     7: end if
  

  1단계 : μ_adjust[n] ← rend_handled[n] / (T_round × δ)

  실제 요청 처리 속도 / 민감도 = 조정된 실제 처리율

  2단계 : D_handled[n] ← ∑D_handled[n] / rend_handled[n]

  평균 퍼즐 난이도

  3단계

  평균 퍼즐 난이도가 0이거나 조정된 실제 처리율이 목표 처리율보다 크다면 다음 라운드의 제안 난이도가 8

  4단계

  아니면 다음 난이도는 = 평균 난이도 x 조정된 실제 처리율 / 목표 처리율

• 결과

  • 난이도를 부풀리는데 비용 상승

  • 짧은 혼잡 공격에 대한 방어 능력 강화

    

  • intro-flooding 방어

    

  • 실험 결과

    END-RUSH ATTACK과 temporary-turmoil를 통한 난이도 부풀리기 실패

    그에 따른 choking과 Maintenance 역시 실패

결론

기존의 DUA와 다른 알고리즘을 사용하여 inflation과 congestion의 상충 관계의 균형점을 찾음.

다른 익명 네트워크에서의 DoS 방어책에도 적용 가능성 연구.

Tor에서 다른 공격 방법과 해결책(ex. IP 스푸핑)과 다른 네트워크에서의 DoS/DDoS에 대해서 공부