The paper introduces the Square Attack, a query-efficient black-box adversarial attack that does not rely on local gradient information, making it less affected by gradient masking. The attack is based on a randomized search scheme that selects localized square-shaped updates at random positions, ensuring that the perturbation is approximately at the boundary of the feasible set at each iteration. This method significantly reduces the number of queries compared to state-of-the-art methods and achieves higher success rates, especially in the untargeted setting. On ImageNet, the Square Attack improves the average query efficiency by a factor of at least 1.8 and up to 3 compared to the recent state-of-the-art $l_2$-attack. The attack is also effective in the black-box setting, outperforming gradient-based white-box attacks on standard benchmarks. The code for the Square Attack is available at https://github.com/max-andr/square-attack.The paper introduces the Square Attack, a query-efficient black-box adversarial attack that does not rely on local gradient information, making it less affected by gradient masking. The attack is based on a randomized search scheme that selects localized square-shaped updates at random positions, ensuring that the perturbation is approximately at the boundary of the feasible set at each iteration. This method significantly reduces the number of queries compared to state-of-the-art methods and achieves higher success rates, especially in the untargeted setting. On ImageNet, the Square Attack improves the average query efficiency by a factor of at least 1.8 and up to 3 compared to the recent state-of-the-art $l_2$-attack. The attack is also effective in the black-box setting, outperforming gradient-based white-box attacks on standard benchmarks. The code for the Square Attack is available at https://github.com/max-andr/square-attack.