Square Attack is a query-efficient black-box adversarial attack that does not rely on local gradient information, making it resistant to gradient masking. It uses a randomized search approach to generate square-shaped perturbations, ensuring that each iteration places the perturbation near the boundary of the feasible set. This method achieves higher success rates and better query efficiency compared to state-of-the-art methods, especially in untargeted settings. On ImageNet, it improves average query efficiency by up to 3 times compared to recent $ l_{\infty} $-attacks. The attack is also effective against white-box models, achieving new state-of-the-art success rates. The algorithm is based on random search, with specific sampling distributions for $ l_{\infty} $ and $ l_{2} $-norms. It uses localized square updates, which are particularly effective for neural networks due to their structure and the nature of $ l_{p} $-balls. The method is validated through extensive experiments on various datasets and models, showing superior performance in terms of success rate and query efficiency. Theoretical analysis supports the effectiveness of the random search approach, and ablation studies confirm the importance of the square-shaped updates and initialization strategy. The Square Attack outperforms other methods in both $ l_{\infty} $ and $ l_{2} $-norm settings, demonstrating its utility in evaluating model robustness without requiring adaptive attacks.Square Attack is a query-efficient black-box adversarial attack that does not rely on local gradient information, making it resistant to gradient masking. It uses a randomized search approach to generate square-shaped perturbations, ensuring that each iteration places the perturbation near the boundary of the feasible set. This method achieves higher success rates and better query efficiency compared to state-of-the-art methods, especially in untargeted settings. On ImageNet, it improves average query efficiency by up to 3 times compared to recent $ l_{\infty} $-attacks. The attack is also effective against white-box models, achieving new state-of-the-art success rates. The algorithm is based on random search, with specific sampling distributions for $ l_{\infty} $ and $ l_{2} $-norms. It uses localized square updates, which are particularly effective for neural networks due to their structure and the nature of $ l_{p} $-balls. The method is validated through extensive experiments on various datasets and models, showing superior performance in terms of success rate and query efficiency. Theoretical analysis supports the effectiveness of the random search approach, and ablation studies confirm the importance of the square-shaped updates and initialization strategy. The Square Attack outperforms other methods in both $ l_{\infty} $ and $ l_{2} $-norm settings, demonstrating its utility in evaluating model robustness without requiring adaptive attacks.